fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. #include <map>
  5. #include <set>
  6. #include <queue>
  7. #include <stack>
  8. #include <string>
  9. #include <cstring>
  10. #include <cmath>
  11. #include <climits>
  12. #include <algorithm>
  13. #include <cstdio>
  14. #include <ctime>
  15. #include <fstream>
  16. #include <sstream>
  17. using namespace std;
  18.  
  19. typedef unsigned long long ULL;
  20. typedef long long LL;
  21.  
  22. #define REP(i,n)      FOR(i,0,n)
  23. #define FOR(i,a,b)    for(int i = a; i < b; i++)
  24. #define ROF(i,a,b)    for(int i=a;i>b;i--)
  25. #define min(a,b)      (a<b?a:b)
  26. #define max(a,b)      (a>b?a:b)
  27. #define GI 		      ({int t;scanf("%d",&t);t;})
  28. #define GL 		      ({LL t;scanf("%lld",&t);t;})
  29. #define GD 		      ({double t;scanf("%lf",&t);t;})
  30. #define pb 	          push_back
  31. #define mp 	          make_pair
  32. #define fii 	      freopen("input.txt","r",stdin)
  33. #define fio 	      freopen("output.txt","w",stdout)
  34. #define MOD 	      1000000007
  35. #define INF	          (int)1e9
  36. #define EPS	          1e-9
  37. #define TR(a,it)      for (typeof((a).begin()) it = (a).begin(); it != (a).end(); ++it)
  38.  
  39. struct Edge
  40. {
  41.        int a, b;
  42.        int weight;
  43.        int chef;        /// 0 for chef
  44.  
  45.        bool operator < (const Edge &other) const {
  46.             if (chef != other.chef)         /// sort by chef edges first
  47.                 return chef < other.chef;
  48.             if (chef == 1)                  /// if non-chef edges sort by decreasing order of wt
  49.                 return weight < other.weight;
  50.             if (chef == 0)                  /// if chef edges sort by increasing order of wt
  51.                 return weight > other.weight;
  52.        }
  53.  
  54.        Edge(int _a = 0, int _b = 0, int _weight = 0, int _chef = 0) {
  55.             a = _a, b = _b, weight = _weight, chef = _chef;
  56.        }
  57. };
  58.  
  59. int parent[5005];
  60.  
  61. int find_set(int i)
  62. {
  63.     if (parent[i] == i) return i;
  64. 	return parent[i] = find_set(parent[i]);
  65. }
  66.  
  67. void union_set(int i, int j)
  68. {
  69.      parent[i] = j;
  70. }
  71.  
  72. int main()
  73. {
  74. 	//fii; fio;
  75. 	int testCases, t = 0, n, m1, m2, p, q, wt;
  76. 	scanf("%d", &testCases);
  77. 	while (testCases--) {
  78. 	    vector<Edge> edges;
  79.         vector<int> MSTedges;
  80.  
  81. 		scanf("%d %d %d", &n, &m1, &m2);
  82.  
  83. 		for (int i=0; i<m1; i++) {
  84.             scanf("%d %d %d", &p, &q, &wt);
  85.             edges.pb(Edge(p, q, wt, 1));
  86. 		}
  87.  
  88. 		for (int i=0; i<m2; i++) {
  89.             scanf("%d %d %d", &p, &q, &wt);
  90.             edges.pb(Edge(p, q, wt, 0));
  91.         }
  92.  
  93.         sort(edges.begin(), edges.end());
  94.  
  95.         //printf("Number of edges : %d\n", edges.size());
  96.         /*printf("Edges:\n");
  97.         for (int i=0; i<edges.size(); i++)
  98.             printf("%d %d %d %d\n", edges[i].a, edges[i].b, edges[i].weight, edges[i].chef);
  99.         */
  100.  
  101.         for (int i=0; i<n; i++)
  102.             parent[i] = i;
  103.  
  104.         int x, y;
  105.         for (int i=0; i < edges.size(); i++) {
  106.           if ( (x = find_set(edges[i].a)) != (y = find_set(edges[i].b)) ) {
  107.               MSTedges.pb(i);
  108.               union_set(x, y);
  109.           }
  110.         }
  111.  
  112.         LL chef_money = 0, others_money = 0;
  113.  
  114.         for (int i=0; i<MSTedges.size(); i++) {
  115.             int idx = MSTedges[i];
  116.             if (edges[idx].chef == 0)
  117.                 chef_money += edges[i].weight;
  118.             else
  119.                 others_money += edges[i].weight;
  120.         }
  121.  
  122.         if ((int)MSTedges.size() != (n-1))
  123.             printf("Impossible\n");
  124.         else
  125.             printf("%lld %lld\n", chef_money, chef_money + others_money);
  126. 	}
  127.  
  128. 	return 0;
  129. }
  130.  
Success #stdin #stdout 0.02s 2836KB
comments (?)
stdin
copy 
2
3 2 1
0 1 5
1 2 4
0 1 10
3 1 1
0 1 1
0 1 3
stdout
copy 
10 14
Impossible
https://ideone.com/Sq4pQ
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!