royalsflush

Bring Your Own Horse AC - Live Archive 4296

Sep 9th, 2012
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.79 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <string.h>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. #define MAXV 3010
  8. #define MAXE 100010
  9.  
  10. struct edge {
  11.     int a,b;
  12.     int w;
  13.  
  14.     edge(int pa=0, int pb=0, int pw=0) :
  15.         a(pa), b(pb), w(pw) {}
  16.     bool operator<(const edge& e) const {
  17.         return this->w<e.w;
  18.     }
  19. };
  20.  
  21. int rank[MAXV];
  22. int rep[MAXV];
  23. edge ls[MAXE];
  24. int n,m;
  25.  
  26. vector<edge> adj[MAXV];
  27.  
  28. int find(int a) {
  29.     if (a!=rep[a])
  30.         rep[a]=find(rep[a]);
  31.     return rep[a];
  32. }
  33.  
  34. bool unio(int a, int b) {
  35.     a=find(a), b=find(b);
  36.     if (a==b)  
  37.         return false;
  38.  
  39.     if (rank[a]>=rank[b]) {
  40.         rep[b]=a;
  41.         if (rank[a]==rank[b]) rank[a]++;
  42.     }
  43.     else rep[a]=b;
  44.    
  45.     return true;
  46. }
  47.  
  48. void kruskal() {
  49.     memset(rank,0,sizeof(rank));
  50.     sort(ls,ls+m); 
  51.  
  52.     for (int i=0; i<n; i++)
  53.         rep[i]=i;
  54.  
  55.     for (int i=0; i<m; i++)
  56.         if (unio(ls[i].a, ls[i].b)) {
  57.             adj[ls[i].a].push_back(ls[i]);
  58.             swap(ls[i].a,ls[i].b);
  59.             adj[ls[i].a].push_back(ls[i]);
  60.         }
  61. }
  62.  
  63. int t, _42=1;
  64. int maxEdge[MAXV][MAXV];
  65.  
  66. void dfs(int u, int src) {
  67.     for (int i=0; i<(int)adj[u].size(); i++)
  68.         if (maxEdge[src][adj[u][i].b]==-1) {
  69.             maxEdge[src][adj[u][i].b]=max(maxEdge[src][u],
  70.                 adj[u][i].w);
  71.             dfs(adj[u][i].b, src);
  72.         }
  73. }
  74.  
  75. int main() {
  76.     scanf("%d", &t);
  77.  
  78.     while (t--) {
  79.         scanf("%d %d", &n,&m);
  80.        
  81.         for (int i=0; i<m; i++) {
  82.             int a,b,l;
  83.             scanf("%d %d %d", &a,&b,&l);
  84.             ls[i] = edge(--a, --b, l);
  85.         }
  86.  
  87.         for (int i=0; i<n; i++)
  88.             adj[i].clear();
  89.         kruskal();
  90.    
  91.         memset(maxEdge,-1,sizeof(maxEdge));
  92.         for (int i=0; i<n; i++)
  93.             maxEdge[i][i]=0;
  94.    
  95.         int q;
  96.         scanf("%d", &q);
  97.  
  98.         printf("Case %d\n", _42++);
  99.  
  100.         for (int i=0; i<q; i++) {
  101.             int s,d;
  102.             scanf("%d %d", &s,&d);
  103.             if (maxEdge[--s][--d]==-1) dfs(s,s);
  104.             printf("%d\n", maxEdge[s][d]);
  105.         }
  106.        
  107.         printf("\n");
  108.     }
  109.    
  110.     return 0;
  111. }
Add Comment
Please, Sign In to add comment