Advertisement
lmarioza

uri 1956

Aug 31st, 2017
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.67 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. #define mp make_pair
  5. #define pb push_back
  6. #define INF 0x3f3f3f3f
  7. #define LINF 0x3f3f3f3f3f3f3f3fLL
  8.  
  9. using namespace std;
  10. typedef long long ll;
  11. typedef vector<int> vi;
  12. typedef set<int> si;
  13. typedef pair<int,int> ii;
  14. typedef vector<ii> vii;
  15. typedef map<string,int> msi;
  16. typedef map<int,int> mi;
  17.  
  18. class UnionFind{
  19. public:
  20. vector<int>p,rank;
  21. UnionFind(int n){
  22. p.resize(n);
  23. rank.assign(n,0);
  24. for(int i=0;i<n;i++){
  25. p[i]=i;
  26. }
  27. }
  28. int findSet(int i){
  29. if(p[i] == i) return i;
  30. return (p[i] = findSet(p[i]));
  31. }
  32. bool isSameSet(int i,int j){
  33. return findSet(i) == findSet(j);
  34. }
  35. void unionSet(int i, int j){
  36. if(isSameSet(i,j)) return;
  37. int x = findSet(i);
  38. int y = findSet(j);
  39. if(rank[x] > rank[y]){
  40. p[y] = x;
  41. return;
  42. }
  43. p[x] = y;
  44. if(rank[x] == rank[y]) rank[y]++;
  45. }
  46. };
  47.  
  48. struct aresta
  49. {
  50. int a,b,c;
  51. aresta(int x,int y,int z){
  52. a = x;
  53. b = y;
  54. c = z;
  55. }
  56. bool operator<(const aresta o) const{
  57. return c < o.c;
  58. }
  59. };
  60.  
  61. int main(){
  62. while(!cin.eof()){
  63. int n;
  64. cin >> n;
  65. //cout <<"-" <<n<<endl;
  66. vector<aresta> a;
  67. UnionFind uf(n+1);
  68. for(int i =1;i<n;i++){
  69. int k;
  70. cin >> k;
  71. //cout << k;
  72. while(k--){
  73. int j,c;
  74. cin >> j>>c;
  75. //cout << " "<< j<< " "<<c;
  76. a.pb(aresta(i,j,c));
  77. }
  78. //cout << '\n';
  79. }
  80. sort(a.begin(),a.end());
  81. ll custo =0;
  82. for(int i=0;i<a.size();i++){
  83. if(!uf.isSameSet(a[i].a,a[i].b)){
  84. uf.unionSet(a[i].a,a[i].b);
  85. custo+=a[i].c;
  86. }
  87. }
  88. map<int,int> cont;
  89. for(int i=1;i<=n;i++){
  90. cont[uf.p[i]]++;
  91. }
  92. cout<< cont.size() << ' '<<custo<<'\n';
  93. }
  94. return 0;
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement