Advertisement
TLE

UVA - 11733 - Airports

TLE
Nov 12th, 2014
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.94 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pf(x) printf("%d",x)
  6. #define pfd(x,y) printf("%d %d",x,y)
  7. #define pfl(x) printf("%ld",x)
  8. #define nl printf("\n")
  9.  
  10. #define cs(x) printf("Case %d: ",x)
  11. #define csn(x) printf("Case %d:\n",x)
  12.  
  13. #define all(x) x.begin(),x.end()
  14. #define Find(x,n) find(all(x),n)
  15. #define pi acos(-1.0)
  16. #define i64 long long
  17. #define pb(x) push_back(x)
  18. #define mset(x,v) memset(x,v,sizeof(x))
  19. #define sc(n) scanf("%d",&n)
  20. #define scl(n) scanf("%ld",&n)
  21. #define scll(n) scanf("%lld",&n)
  22. #define scd(n,m) scanf("%d %d",&n,&m)
  23. #define sct(n,m,w) scanf("%d %d %d",&n,&m,&w)
  24. #define scdl(n,m) scanf("%ld %ld",&n,&m)
  25. #define scdll(n,m) scanf("%lld %lld",&n,&m)
  26. #define filein freopen("in.txt","r",stdin)
  27. #define fileout freopen("my.txt","w",stdout)
  28. #define FOR(i,n) for(int i=0;i<n; i++)
  29. #define inf 100000000
  30. #define MAX 200010
  31.  
  32.  
  33. bool isUpper(char ch){ if( ch>='A' && ch<='Z' ) return true; return false; }
  34. bool isLower(char ch){ if( ch>='a' && ch<='z') return true; return false;}
  35. bool isLetter(char ch){ if( ch>='A' && ch<='Z' || ch>='a' && ch<='z') return true; return false; }
  36. bool isDigit(char ch){ if( ch>='0' && ch<='9') return true; return false; }
  37. char toLower(char ch){ if (isUpper(ch)) return (ch+32); return ch; }
  38. char toUpper(char ch){ if (isLower(ch)) return (ch-32); return ch; }
  39.  
  40. template<class T>bool isEven(T a){ return (a%2==0);}
  41. template<class T>T sq(T a){ return a*a; }
  42. template<class T>T gcd(T a,T b){ return b==0 ? a : gcd(b,a%b); }
  43. template<class T>T lcm(T a,T b){ return (a/gcd(a,b))*b; }
  44. template<class T>bool isPrime(T n){ for(T i=2; i*i<=n; i++){ if(n%i==0) return false; } return true; }
  45. template<class T>T Pow(T n,T p) { T res=n; for(T i=1;i<p; i++){ res *= n; } return res; }
  46. template<class T>T Max(T n,T p) { if(n>=p) return n; return p; }
  47.  
  48. struct node
  49. {
  50.     int u,v,w;
  51.     bool operator < ( const node& p) const { return w < p.w; }
  52. };
  53.  
  54. vector<node>g;
  55. int par[MAX];
  56. int ports;
  57.  
  58. int parent(int x){
  59.     return (par[x]==x) ? x : par[x]=parent(par[x]);
  60. }
  61.  
  62. int mst(int n,int a){
  63.     for(int j=1;j<=n;j++) par[j]=j;
  64.     int sz=(int)g.size();
  65.     int res=0;
  66.     for(int i=0;i<sz;i++){
  67.         int u=g[i].u;
  68.         int v=g[i].v;
  69.         int pu=parent(u);
  70.         int pv=parent(v);
  71.         if(pu!=pv){
  72.             if(g[i].w<a){
  73.                 ports--;
  74.                 par[pu]=pv;
  75.                 res += g[i].w;
  76.             }
  77.         }
  78.     }
  79.     return res;
  80. }
  81.  
  82. int main()
  83. {
  84.    filein;
  85.  
  86.     int t;
  87.     sc(t);
  88.     for(int T=1;T<=t; T++){
  89.         int n,m,a;
  90.         scd(n,m);
  91.         sc(a);
  92.         node N;
  93.         for(int i=0;i<m;i++){
  94.             int u,v,w;
  95.             scanf("%d %d %d",&u,&v,&w);
  96.             N.u = u;
  97.             N.v = v;
  98.             N.w = w;
  99.             g.pb(N);
  100.         }
  101.         sort(all(g));
  102.         ports=n;
  103.         int res = mst(n,a);
  104.         printf("Case #%d: %d %d\n",T,(res+ports*a),ports);
  105.         g.clear();
  106.     }
  107.     return 0;
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement