3624: [Apio2008]免费道路
标签：struct puts pre git int 两种 for code lin
3624: [Apio2008]免费道路
https://www.lydsy.com/JudgeOnline/problem.php?id=3624
题意：
一张无向图，每种边有两种类型0和1。求一个最小生成树使得有k条0边。
分析：
为了满足有k条0边的限制，先考虑0边哪些必选，如果所有1边都加入后，还有0边可以使得图不连通，那么这些0边必须选。
把必须选的加上然后再加到k，然后再加1边。中间判一下是否必选的大于k，0边是否大于等于k。
代码：
1 #include 2 using namespace std;
3 typedef long long LL;
4
5 inline int read() {
6 int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch==‘-‘)f=-1;
7 for(;isdigit(ch);ch=getchar())x=x*10+ch-‘0‘;return x*f;
8 }
9
10 const int N = 20010;
11 const int M = 100010;
12
13 struct Edge{
14 int u,v;
15 Edge() {}
16 Edge(int a,int b) {u = a, v = b;}
17 }e[M];
18 int fa[N], q[M];
19 bool vis[M];
20
21 int find(int x) {
22 return x == fa[x] ? x : fa[x] = find(fa[x]);
23 }
24
25 int main () {
26
27 int n = read(), m = read(), k = read();
28
29 int B = 0, W = m + 1;
30 for (int i=1; ii) {
31 int u = read(), v = read(), c = read();
32 if (c == 1) e[++B] = Edge(u,v);
33 else e[--W] = Edge(u,v);
34 }
35
36 for (int i=1; i i;
37
38 int tot = 0;
39 for (int i=1; ii) {
40 int u = find(e[i].u), v = find(e[i].v);
41 if (u == v) continue;
42 fa[u] = v;
43 if (i > B) vis[i] = true, q[++tot] = i;
44 }
45
46 if (tot > k) {
47 puts("no solution");
48 return 0;
49 }
50
51 for (int i=1; i i;
52
53 for (int i=1; ii)
54 fa[find(e[q[i]].u)] = find(e[q[i]].v);
55
56 for (int i=W; ii) {
57 if (tot == k) break;
58 int u = find(e[i].u), v = find(e[i].v);
59 if (u == v) continue;
60 fa[u] = v;
61 tot ++;
62 vis[i] = true;
63 }
64
65 if (tot k) {
66 puts("no solution");
67 return 0;
68 }
69
70 for (int i=1; ii) {
71 int u = find(e[i].u), v = find(e[i].v);
72 if (u == v) continue;
73 fa[u] = v;
74 vis[i] = true;
75 }
76
77 for (int i=1; ii)
78 if (vis[i]) printf("%d %d %d\n", e[i].u, e[i].v, i1:0);
79
80 return 0;
81 }
3624: [Apio2008]免费道路
标签：struct puts pre git int 两种 for code lin
原文地址：https://www.cnblogs.com/mjtcn/p/9357005.html
评论