A kommunikációs hálózat tartalmazza a számítógépeket és az azok közötti kétirányú kapcsolatokat. Mindegyik kapcsolathoz sávszélesség tartozik. Bármely, két gépet összekötő hálózatrész sávszélessége alatt az egyes vezetékszakaszok sávszélességének minimumát értjük. Ha két gép között több úton is létesíthető kapcsolat, akkor az összeközzetés sávszélessége ezek közül a maximuma. A teljes hálózat sávszélessége alatt az alkotó gépek közötti sávszélességek minimumát értjük.Feladat:
Írj programot, amely beolvassa a hálózat adatait, majd meghatározza a sávszélességét.Bemenet:A bemenet néhány esetet tartalmaz, az esetszámot (T) a NET.IN állomány első sora adja meg. Minden teszteset első sora két egészet, az N és M értékét tartalmazza. N a gépek száma (2<=N<=5000), az M értéke pedig a kapcsolatok számát adja meg (1<=M<=10000). A gépeket 1-től N-ig számozzuk. A következő M sor mindegyike 3 egészet foglal magában, az X, Y és B számokat, (1<=X, Y<=N, X<>Y) ahol X és Y az a két gép, amelyet összekötünk, a B pedig a közöttük lévő sávszélesség. Lehetséges több kapcsolat két gép között.Kimenet:A kimenetnek tesztesetenként egy sort kell tartalmaznia, soronként egy egész számmal, amely a hálózat sávszélességét adja meg. Ha a hálózat nem összefüggő, akkor sávszélessége 0.Példa:
net.in net.out 2
5 6
1 2 12
2 3 23
3 4 34
4 1 41
2 5 25
3 5 5
4 3
1 2 1
3 4 3
1 2 223
0
Egy iskolai számítógépteremben a munkaállomások hosszú sorban helyezkednek el. Elhatározták, közülük pontosan M darabból átjárót készítenek, amely közvetlenül kapcsolódik az Internet gerincvezetékre. A többi munkaállomást a hozzá legközelebb eső átjáróhoz kapcsolják. A hatékonyság érdekében az átjárókat úgy kell megválasztani, hogy a munkaállomás - legközelebbi átjáró távolságok legnagyobbika a lehető legkisebb legyen. A munkaállomásokat egy egyenes mentén képzeljük el, pozíciójukat így egyetlen koordinátával megadhatjuk. Két munkaállomás távolsága az őket jellemző koordináták különbségének abszolútértéke.Feladat:
Készíts programot, amely megadja az munkaállomás-átjáró távolságok maximumát és az átjáróként használt munkaállomások pozícióját.Bemenet:A bemeneti állomány néhány tesztadatsort tartalmaz. Az állomány első sorában lévő (T) egész szám a tesztesetek számát adja meg. Minden tesztesethez két sor tartozik. Az első sorban két egész szám, az N és az M található. Az N (1<=N<=100) a munkaállomások, M (1<=M<=N) pedig az átjárók számát adja meg. Az adott tesztesethez tartozó következő sorban N darab pozitív egész szám van, növekvő sorrendben, megadva a munkaállomások pozícióját. A pozíciót megadó X koordináta a [0;30000] intervallumban van.Kimenet:A kimeneti állomány tesztesetenként két sort tartalmaz. Az első sor egyetlen egész szám, a D, amely a munkaállomás - legközelebbi átjáró távolságok legnagyobbika az ideális elrendezés esetén. A második sor pontosan M darab egészet, az átjárók pozícióját tartalmazza. Ha több lehetséges pozíciósor van, a kimeneti állományba csak az egyiket kell írni.Példa:
gate.in gate.out 2
6 2
1 3 7 10 15 17
4 4
1 3 5 75
3 15
0
1 3 5 7
Egy város úthálózata kereszteződésekből és ezeket a kereszteződéseket összekötő egyirányú utcákból (élekből) áll. Minden utca pontosan két különböző kereszteződést kapcsol össze. Minden kereszteződéspárt legfeljebb egy egyirányú utca kapcsol össze. Az úthálózatnak megvan az a tulajdonsága, hogy minden kereszteződés minden másikból elérhető a fenti egyirányú utcákon. A városi tanács elhatározta, hogy az utcákat felújítja, s emiatt az éppen javítottat lezárja. Egyszerre csak egyet! A javítási munkák azokkal az utcákkal kezdődnek, amelyek lezárásával az úthálózat összefüggősége megmarad.Feladat:
Írj programot, amely az úthálózat adatainak beolvasását követően megadja, hogy mely utcák zárhatók le az összefüggőség megtartása mellett.Bemenet:A bemeneti állomány több tesztesetet tartalmazhat, amelyek számát az állomány első sorába írt egész szám határozza meg. A tesztesetek első sora két egészet, az N és az M értékét tartalmazza. Az N (3<=N<=500) a kereszteződések számát, az M (3<=M<=50000) az utcák számát szabja meg. A kereszteződéseket 1-től N-ig sorszámozzuk, így kerülnek azonosításra. A következő M sor az X és az Y (1<=X, Y<=N) egészeket tartalmazza, amelyek az X-ből Y-ba vezető egyirányú utcát határozzák meg.Kimenet:A kimeneti állomány minden tesztesetre azokat az utakat tartalmazza, amelyek az összefüggőség megsértése nélkül lezárhatók. Minden sor egy utat tartalmaz. Ha nincs ilyen út, akkor egy üres sort kell ideírni. Minden tesztesetre adott válasz a 0 0 párral zárul.Példa:
roads.in roads.out 2
4 6
1 2
2 3
3 4
2 4
3 1
4 1
4 4
1 2
2 3
3 4
4 12 4
3 4
3 1
0 00 0