fork download
copy 
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<vector>
  4. #include<utility>
  5. #include<algorithm>
  6. using namespace std;
  7.  
  8. #define SIZE 10004
  9. #define INF 2147483647
  10.  
  11. typedef pair<int, int> ii;
  12. typedef pair<int, ii> Iii;
  13.  
  14. struct Edge
  15. {
  16.     int u, v, nr, d;
  17. } E[SIZE];
  18.  
  19. struct DisjointSet
  20. {
  21.     int root, rank;
  22. } S[SIZE];
  23.  
  24. int NR[SIZE], D[SIZE];
  25. vector<Iii> T[SIZE];
  26.  
  27. bool compare(const Edge &lhs, const Edge &rhs)
  28. {
  29.     return lhs.nr!=rhs.nr ? (lhs.nr>rhs.nr) : (lhs.d<rhs.d);
  30. }
  31.  
  32. void initialize_sets(int n)
  33. {
  34.     for(int i = 1; i<=n; ++i)
  35.         S[i].root = i, S[i].rank = 0;
  36. }
  37.  
  38. int find_set(int u)
  39. {
  40.     return S[u].root==u ? u : (S[u].root = find_set(S[u].root));
  41. }
  42.  
  43. void union_sets(int s1, int s2)
  44. {
  45.     if(S[s1].rank<S[s2].rank)
  46.         S[s1].root = s2;
  47.     else if(S[s1].rank>S[s2].rank)
  48.         S[s2].root = s1;
  49.     else
  50.         S[s2].root = s1, S[s1].rank++;
  51. }
  52.  
  53. void MST(int n, int m)
  54. {
  55.     int s1, s2, i;
  56.  
  57.     sort(E, E+m, compare);
  58.     initialize_sets(n);
  59.  
  60.     for(i = 0; i<m && n>1; ++i)
  61.     {
  62.         s1 = find_set(E[i].u), s2 = find_set(E[i].v);
  63.         if(s1!=s2)
  64.             union_sets(s1, s2), n--,
  65.             T[E[i].u].push_back(Iii(E[i].v, ii(E[i].nr, E[i].d))),
  66.             T[E[i].v].push_back(Iii(E[i].u, ii(E[i].nr, E[i].d)));
  67.     }
  68. }
  69.  
  70. void DFS(int u, int parent, int nr, int d)
  71. {
  72.     NR[u] = nr, D[u] = d;
  73.  
  74.     for(vector<Iii>::iterator p = T[u].begin(); p!=T[u].end(); ++p)
  75.         if(p->first!=parent)
  76.             DFS(p->first, u, min(nr, p->second.first), d+p->second.second);
  77. }
  78.  
  79. void solve(int n, int m, int k)
  80. {
  81.     int maxNR, minD = INF, i;
  82.  
  83.     for(i = 1; i<=n; ++i)
  84.         T[i].clear();
  85.  
  86.     memset(NR+1, 0, n*sizeof(int));
  87.  
  88.     MST(n, m);
  89.     DFS(n, -1, INF, 0);
  90.  
  91.     maxNR = *max_element(NR+1, NR+1+k);
  92.     for(i = 1; i<=k; ++i)
  93.         if(NR[i]==maxNR && minD>D[i])
  94.             minD = D[i];
  95.  
  96.     for(i = 1; i<=k; ++i)
  97.         if(NR[i]==maxNR && D[i]==minD)
  98.             printf(" %d", i);
  99.     putchar('\n');
  100. }
  101.  
  102. int main()
  103. {
  104.     int test, t = 1, n, m, k, i;
  105.  
  106.     for(scanf("%d", &test); t<=test; ++t)
  107.     {
  108.         scanf("%d %d %d", &n, &k, &m);
  109.         for(i = 0; i<m; ++i)
  110.             scanf("%d %d %d %d", &E[i].u, &E[i].v, &E[i].d, &E[i].nr);
  111.  
  112.         printf("Case #%d:", t);
  113.         solve(n, m, k);
  114.     }
  115.  
  116.     return 0;
  117. }
Success #stdin #stdout 0s 3528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HvlzXr
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

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!