/* user: php link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1541 */ #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #include<string> #include<stack> #include<queue> #include<map> #include<sstream> #include<utility> #define FOR(i, s, e) for(int i=s; i<e; i++) #define loop(i, n) for(int i=0; i<n; i++) #define getint(n) scanf("%d", &n) #define pb(a) push_back(a) #define ll long long #define dd double #define SZ(a) int(a.size()) #define read() freopen("input.txt", "r", stdin) #define write() freopen("output.txt", "w", stdout) #define mem(a, v) memset(a, v, sizeof(a)) #define all(v) v.begin(), v.end() #define pi acos(-1.0) #define INF 1<<29 #define mod abs #define pf printf #define sf scanf #define mp make_pair #define paii pair<int, int> #define padd pair<dd, dd> #define pall pair<ll, ll> #define fr first #define sc second #define FEM edges[i].sc.fr #define SEM edges[i].sc.sc using namespace std; #define MAXX 102 int N, M; vector<pair<int, paii> > edges; vector<int>graph[MAXX]; int best, secondBest; bool secondBestDone; int parent[MAXX]; int cost[MAXX][MAXX]; int dir[MAXX]; int find(int u) { if(parent[u] == u) return u; return parent[u] = find(parent[u]); } void bfs(int source, int target) { bool visited[MAXX]; mem(visited, false); visited = 1; queue<int>Q; Q.push(source); while(!Q.empty()) { int u = Q.front(); Q.pop(); loop(i, SZ(graph[u])) { int v = graph[u][i]; if(!visited[v]) { visited[v] = 1; dir[v] = u; if(target == v) { return; } Q.push(v); } } } } int cleanAndAdd(int source, int destination) { int maxValue = -INF; while(source != destination) { //cout<<"visiting " << cost[dir]<<" cost"<<endl; maxValue = max(maxValue, cost[dir] ); source = dir; } //cout<<"maxValue " <<maxValue<<endl; return maxValue; } void MST() { best = 0; secondBestDone = false; secondBest = INF; int p, q; loop(i, SZ(edges)) { p = find(FEM); q = find(SEM); if(p != q) { graph[ FEM ].pb(SEM); graph[ SEM ].pb(FEM); cost[SEM][FEM] = cost[FEM][SEM] = edges[i].fr; parent[p] = q; best += edges[i].fr; } else { if(!secondBestDone) { bfs(FEM, SEM); secondBest = min(secondBest, - cleanAndAdd(SEM, FEM) + edges[i].fr ); if(secondBest == 0) secondBestDone = 1; } } } } int main() { //read(); int p, q, w; int kases; getint(kases); while(kases--) { getint(N); getint(M); edges.clear(); loop(i, M) { getint(p); getint(q); getint(w); edges.pb(mp(w, mp(p, q))); } sort(all(edges)); for(int i=1; i<=N; i++) parent[i] = i, graph[i].clear(); MST(); secondBest += best; cout<<best<<" "<<secondBest<<endl; } return 0; }
Category Archives: Kruskal
(UVa)10397 – Connect the Campus
0/* user: php link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1338 */ #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #include<string> #include<stack> #include<queue> #include<map> #include<sstream> #include<utility> #define FOR(i, s, e) for(int i=s; i<e; i++) #define loop(i, n) for(int i=0; i<n; i++) #define getint(n) scanf("%d", &n) #define pb(a) push_back(a) #define ll long long #define dd double #define SZ(a) int(a.size()) #define read() freopen("input.txt", "r", stdin) #define write() freopen("output.txt", "w", stdout) #define mem(a, v) memset(a, v, sizeof(a)) #define all(v) v.begin(), v.end() #define pi acos(-1.0) #define INF 1<<29 #define mod abs #define pf printf #define sf scanf #define mp make_pair #define paii pair<int, int> #define padd pair<dd, dd> #define pall pair<ll, ll> #define fr first #define sc second using namespace std; #define MAXX 752 vector<paii> nodes; vector<pair<double, paii> > edges; int N, M; int parent[MAXX]; int find(int u) { if(parent[u] == u) return u; return parent[u] = find(parent[u]); } double sqr(int a) { return a*a; } int main() { int p, q; while(getint(N) == 1) { nodes.clear(); edges.clear(); loop(i, N) { getint(p); getint(q); nodes.pb(mp(p, q)); parent[i] = i; } getint(M); loop(i, M) { getint(p); getint(q); p--; q--; parent[ find(p) ] = find(q); } loop(i, N) { FOR(j, i+1, N) { if(find(i) != find(j)) { edges.pb( mp( sqrt( sqr(nodes[i].fr - nodes[j].fr) + sqr(nodes[i].sc - nodes[j].sc) ) , mp(i, j))); } } } double result = 0; sort(all(edges)); loop(i, SZ(edges)) { p = find(edges[i].sc.fr); q = find(edges[i].sc.sc); if( p != q) { parent[p] = q; result += edges[i].fr; } } pf("%.2lf\n", result); } return 0; }
(UVa) 10099 – The Tourist Guide
0/* user: php link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1040 */ #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #include<string> #include<stack> #include<queue> #include<map> #include<sstream> #include<utility> #define FOR(i, s, e) for(int i=s; i<e; i++) #define loop(i, n) for(int i=0; i<n; i++) #define getint(n) scanf("%d", &n) #define pb(a) push_back(a) #define ll long long #define dd double #define SZ(a) int(a.size()) #define read() freopen("input.txt", "r", stdin) #define write() freopen("output.txt", "w", stdout) #define mem(a, v) memset(a, v, sizeof(a)) #define all(v) v.begin(), v.end() #define pi acos(-1.0) #define INF 1<<29 #define mod abs #define pf printf #define sf scanf #define mp make_pair #define paii pair<int, int> #define padd pair<dd, dd> #define pall pair<ll, ll> #define sc second #define fr first using namespace std; #define MAXX 102 int N, R; int parent[MAXX]; vector<pair<int, paii> >edges; int source, destination, T; int find(int u) { if(parent[u] == u) return u; return parent[u] = find(parent[u]); } int MST() { for(int i=1; i<=N; i++) parent[i] = i; int p, q; loop(i, SZ(edges)) { p = find(edges[i].sc.fr); q = find(edges[i].sc.sc); if(p != q) { parent[p] = q; } if(find(source) == find(destination)) { edges[i].fr--; return ceil((double)T/(double)edges[i].fr); } } } int main() { int p, q, w; int kaseno = 0; while(1) { getint(N); getint(R); if(N == 0 && R == 0) break; edges.clear(); loop(i, R) { getint(p); getint(q); getint(w); edges.pb( mp(w, mp(p, q))); } sort(all(edges)); reverse(all(edges)); getint(source); getint(destination); getint(T); pf("Scenario #%d\nMinimum Number of Trips = %d\n\n", ++kaseno, MST()); } return 0; }
(UVa) 10048 – Audiophobia
0/* user: php link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=989 */ #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #include<string> #include<stack> #include<queue> #include<map> #include<sstream> #include<utility> #define FOR(i, s, e) for(int i=s; i<e; i++) #define loop(i, n) for(int i=0; i<n; i++) #define getint(n) scanf("%d", &n) #define pb(a) push_back(a) #define ll long long #define dd double #define SZ(a) int(a.size()) #define read() freopen("input.txt", "r", stdin) #define write() freopen("output.txt", "w", stdout) #define mem(a, v) memset(a, v, sizeof(a)) #define all(v) v.begin(), v.end() #define pi acos(-1.0) #define INF 1<<29 #define mod abs #define pf printf #define sf scanf #define mp make_pair #define paii pair<int, int> #define padd pair<dd, dd> #define pall pair<ll, ll> #define get(a, b, c) getint(a); getint(b); getint(c) #define sc second #define fr first using namespace std; #define MAXX 101 int C, S, Q; vector< pair<int, paii> >edges; vector<int> nodes[MAXX]; int cost[MAXX][MAXX]; int parent[MAXX]; int find(int u) { if(parent[u] == u) return u; return parent[u] = find(parent[u]); } void MST() { sort(all(edges)); int p, q; loop(i, SZ(edges)) { p = find( edges[i].sc.fr ); q = find( edges[i].sc.sc ); if(p != q) { parent[p] = q; nodes[p].pb(q); nodes[q].pb(p); cost[p][q] = edges[i].fr; cost[q][p] = edges[i].fr; } } } int dir[MAXX]; void bfs(int start, int end) { int ret = -INF; bool visited[MAXX]; mem(visited, 0); visited[start] = 1; queue<int> Q; Q.push(start); while( !Q.empty() ) { int u = Q.front(); loop(i, SZ(nodes[u])) { int v = nodes[u][i]; if( !visited[v] ) { visited[v] = 1; dir[v] = u; if(v == end) return; Q.push(v); } } Q.pop(); } } int main() { //read(); int p, q, w; int kaseno = 0; while(1) { get(C, S, Q); if(C == 0 && S == 0 && Q == 0) break; edges.clear(); for(int i=1; i<=C; i++) nodes[i].clear(), parent[i] = i; loop(i, S) { get(p, q, w); edges.pb( mp(w, mp(p, q) ) ); } MST(); if(kaseno) pf("\n"); pf("Case #%d\n", ++kaseno); loop(i, Q) { getint(p); getint(q); if( find(p) != find(q) ) { pf("no path\n"); } else { int ret = -INF; bfs(q, p); while(p != q) { ret = max(ret, cost[p][ dir[p]] ); p = dir[p]; } pf("%d\n", ret); } } } return 0; }
(UVa) 10147 – Highways
0/* user: php time: 0.444 sec link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1088 */ #include<iostream> #include<vector> #include<cstdio> #include<cmath> #include<algorithm> #define getint(n) scanf("%d", &n) #define loop(i, n) for(int i=0; i<n; i++) using namespace std; long long square(int a) { return (long long)a * (long long)a; } struct plot{ int x, y; }; plot point[751]; struct distances{ int from, to; double dist; void push(int a, int b) { from = a; to = b; dist = sqrt(square(point[a].x - point[b].x) + square(point[a].y - point[b].y)); } }; int parent[751]; distances di[281250]; int find(int townID) { if(parent[townID] == townID) { return townID; } return parent[townID] = find(parent[townID]); } bool comp(distances a, distances b) { return a.dist < b.dist; } int main() { int kases, towns, x, y, existingHighWays, p; bool all_connected; getint(kases); while(kases--) { all_connected = true; getint(towns); loop(t, towns) { getint(x); getint(y); point[t].x = x; point[t].y = y; } loop(i, 751) { parent[i] = i; } getint(existingHighWays); loop(t, existingHighWays) { getint(x); //x'th highway and y'th highway are connected getint(y); x = find(x-1); y = find(y-1); parent[x] = y; } p = 0; loop(i, towns) { for(int j=i+1; j<towns; j++) { if(find(i) != find(j)) {//they are not yet connected some how di[p++].push(i, j); } } } sort(di, di + p, comp); loop(i, p) { x = find(di[i].from); y = find(di[i].to); if(x != y) { all_connected = false; parent[x] = y; printf("%d %d\n", di[i].from+1, di[i].to+1); } } if(all_connected) { printf("No new highways need\n"); } if(kases) printf("\n"); } return 0; }
(UVa) 544 – Heavy Cargo
0/* user: php time: 0.040 sec link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=485 */ #include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<string> #include<map> #define getint(a) scanf("%d", &a) #define loop(i, n) for(int i=0; i<n; i++) using namespace std; map<string, string> parent; struct DATA{ string u, v; int weight; }; bool comp(DATA a, DATA b) { return a.weight > b.weight; } string find(string str) { if(parent[str] == "") { return str; } return parent[str] = find(parent[str]); } int main() { int number_of_cities, number_of_roads; string city1, city2; int weight; DATA edge; int minValue; int kaseno = 0; string u, v; vector<DATA> edgelist; while(true) { getint(number_of_cities); getint(number_of_roads); if(number_of_cities == 0 && number_of_roads == 0) break; parent.clear(); edgelist.clear(); loop(t, number_of_roads) { cin>>city1>>city2>>weight; edge.u = city1; edge.v = city2; edge.weight = weight; edgelist.push_back(edge); } cin>>city1>>city2; sort(edgelist.begin(), edgelist.end(), comp); minValue = 1000000; loop(i, number_of_roads) { u = find(edgelist[i].u); v = find(edgelist[i].v); if(u != v) { parent[u] = v; if(minValue > edgelist[i].weight ) { minValue = edgelist[i].weight; } } if(find(city1) == find(city2)) { break; } } printf("Scenario #%d\n", ++kaseno); printf("%d tons\n\n", minValue); } return 0; }