SGU 323 Aviamachinations

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 600000;
 4 class ARC {
 5 public:
 6     int u,v;
 7     ARC(int x = 0,int y = 0) {
 8         u = x;
 9         v = y;
10     }
11 };
12 class ARC1:public ARC {
13 public:
14     int w,id;
15     ARC1(int x = 0,int y = 0,int cw = 0,int cid = 0):ARC(x,y) {
16         w = cw;
17         id = cid;
18     }
19     bool operator<(const ARC1 &t) {
20         return w < t.w;
21     }
22 } g[maxn];
23 class ARC2:public ARC {
24 public:
25     int next;
26     ARC2(int x = 0,int y = 0,int nxt = -1):ARC(x,y) {
27         next = nxt;
28     }
29 } e[maxn];
30 int head[maxn],uf[maxn],tot,n,m,k;
31 void init() {
32     for(int i = 0; i <= n; ++i) uf[i] = i;
33 }
34 int Find(int x) {
35     return uf[x] = x == uf[x]?x:Find(uf[x]);
36 }
37 void add(int u,int v,int x) {
38     e[tot] = ARC2(u,v,head[x]);
39     head[x] = tot++;
40 }
41 vector<int>MST,ans,tans;
42 void Kruskal() {
43     init();
44     MST.clear();
45     sort(g,g+k);
46     for(int i = 0; i < k; ++i) {
47         int x = Find(g[i].u),y = Find(g[i].v);
48         if(x == y) continue;
49         uf[x] = y;
50         MST.push_back(i);
51         if(MST.size() >= n-1) return;
52     }
53 }
54 void solve() {
55     int sum = 0x3f3f3f3f,id,tsum;
56     for(int i = 1; i <= m; ++i) {
57         init();
58         tans.clear();
59         for(int j = head[i]; ~j; j = e[j].next) {
60             int x = Find(e[j].u),y = Find(e[j].v);
61             if(x != y) uf[x] = y;
62         }
63         for(int j = tsum = 0; j < MST.size(); ++j) {
64             int x = Find(g[MST[j]].u),y = Find(g[MST[j]].v);
65             if(x == y) continue;
66             tsum += g[MST[j]].w;
67             uf[x] = y;
68             tans.push_back(MST[j]);
69         }
70         if(tsum < sum) {
71             sum = tsum;
72             id = i;
73             ans.clear();
74             std::copy(tans.begin(),tans.end(),std::back_inserter(ans));
75         }
76     }
77     printf("%d %d %d\n",sum,id,ans.size());
78     bool flag = false;
79     sort(ans.begin(),ans.end());
80     for(int i = 0; i < ans.size(); ++i) {
81         if(flag) putchar(‘ ‘);
82         printf("%d",g[ans[i]].id);
83         flag = true;
84     }
85     putchar(‘\n‘);
86 }
87 int main() {
88     int a,b,c,p;
89     scanf("%d %d %d",&n,&m,&k);
90     memset(head,-1,sizeof(head));
91     for(int i = tot = 0; i < k; ++i) {
92         scanf("%d %d %d %d",&a,&b,&c,&p);
93         g[i] = ARC1(a,b,p,i + 1);
94         add(a,b,c);
95     }
96     Kruskal();
97     solve();
98     return 0;
99 }