#1199
Metrou
Această problemă este dedicată celor care așteaptă metroul cu cea mai mare ardoare: locuitorii din Drumul Taberei.
Se dă planul unei rețele de metrou cu N
stații și M
tuneluri bidirecționale între stații. Două stații de metrou se numesc vecine dacă există un tunel între ele în acest plan. Fiecare stație i
are asociat un profit p[i]
dat.
Henry a fost recent promovat dintr-un post de angajat al departamentului de curățenie pe postul de project manager al firmei. Deoarece nu există fonduri pentru construirea întregii rețele de metrou, Henry trebuie să aleagă o submulțime de stații care vor fi construite, astfel încât oricare două stații alese să nu fie vecine în planul inițial. Pentru a-și păstra poziția în companie, suma profiturilor stațiilor alese în această submulțime trebuie să fie maximă.
Dându-se N
, M
, profiturile aduse de fiecare din cele N
stații și planul inițial al rețelei, să se determine suma maximă a profiturilor stațiilor pe care le poate alege Henry astfel încât oricare două stații alese să nu fie vecine în planul inițial.
ONI 2015, Clasele XI-XII
Problema | Metrou | Operații I/O |
metrou.in /metrou.out
|
---|---|---|---|
Limita timp | 0.5 secunde | Limita memorie |
Total: 64 MB
/
Stivă 16 MB
|
Id soluție | #46823636 | Utilizator | |
Fișier | metrou.cpp | Dimensiune | 6.25 KB |
Data încărcării | 23 Noiembrie 2023, 19:31 | Scor / rezultat | Eroare de compilare |
metrou.cpp:46:1: warning: missing terminating " character [enabled by default] "); ^ metrou.cpp:46:1: error: missing terminating " character metrou.cpp:289:12: warning: missing terminating " character [enabled by default] printf("%d ^ metrou.cpp:289:5: error: missing terminating " character printf("%d ^ metrou.cpp:290:1: warning: missing terminating " character [enabled by default] ", solve()); ^ metrou.cpp:290:1: error: missing terminating " character metrou.cpp: In function 'void newChain(int)': metrou.cpp:77:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int j=0; j<v[i].size(); ++j) ^ metrou.cpp:107:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int j=0; j<v[x].size(); ++j) ^ metrou.cpp: In function 'int solveChain()': metrou.cpp:167:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int i=0; i<v[x].size(); ++i) ^ metrou.cpp: In function 'int solve()': metrou.cpp:209:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int j=0; j<v[i].size(); ++j) ^ metrou.cpp:230:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int j=0; j<v[nod].size(); ++j) ^ metrou.cpp: In function 'int main()': metrou.cpp:292:5: error: expected primary-expression before 'return' return 0; ^ metrou.cpp:273:37: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result] freopen("metrou.in", "r", stdin); ^ metrou.cpp:274:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result] freopen("metrou.out", "w", stdout); ^ metrou.cpp:276:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &n, &m); ^ metrou.cpp:278:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &p[i]); ^ metrou.cpp:282:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &a, &b); ^
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema Metrou face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.