首页 > 代码库 > 【Kruskal+贪心思想】BZOJ3624-[Apio2008]免费道路
【Kruskal+贪心思想】BZOJ3624-[Apio2008]免费道路
国庆万岁！！！！！
【题目大意】
给定一张无向图，有两种边的类型为0和1。求一个最小生成树使得边0有k条。
【思路】
跑两次Kruskal。
第一次的时候优先选择边1，然后判断有哪些边0还不能连通，那么这些边0是必须要选取的。如果必须要选的边0大于k，那么直接输出无解。
第二次的时候先合并那么必须要选取的边0，然后在剩下的边0中左右还没有连通的里选取。如果把所有都选上了之后边0的数量还是没有到k，那么直接输出无解。
截下来按照普通Kruskal的方法把边1合并掉。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<vector> 6 using namespace std; 7 const int MAXN=20000+50; 8 const int MAXM=100000+50; 9 struct Edge 10 { 11 int u,v; 12 }edge[MAXM]; 13 int n,m,k; 14 int vis[MAXM]; 15 int L,R; 16 int fa[MAXN],h[MAXN]; 17 vector<int> mustchoose; 18 19 void initset(){for (int i=1;i<=n;i++) fa[i]=i,h[i]=1;} 20 21 int find(int x) 22 { 23 int r=x; 24 while (fa[r]!=r) r=fa[r]; 25 while (fa[x]!=r) 26 { 27 int tmp=fa[x]; 28 fa[x]=r; 29 x=fa[x]; 30 } 31 return r; 32 } 33 34 void unionset(int a,int b) 35 { 36 if (h[a]>=h[b]) 37 { 38 fa[b]=a; 39 if (h[a]==h[b]) h[a]++; 40 } 41 else fa[a]=b; 42 } 43 44 void init() 45 { 46 scanf("%d%d%d",&n,&m,&k); 47 L=0,R=m+1; 48 for (int i=1;i<=m;i++) 49 { 50 int u,v,c; 51 scanf("%d%d%d",&u,&v,&c); 52 if (c) edge[++L]=(Edge){u,v}; 53 else edge[--R]=(Edge){u,v}; 54 } 55 } 56 57 void solve() 58 { 59 int t=0; 60 initset(); 61 for (int i=1;i<=m;i++) 62 { 63 int fa=find(edge[i].u),fb=find(edge[i].v); 64 if (fa!=fb) 65 { 66 unionset(fa,fb); 67 if (i>=R) 68 { 69 vis[i]=1; 70 t++; 71 mustchoose.push_back(i); 72 } 73 } 74 } 75 if (t>k) 76 { 77 puts("no solution"); 78 return; 79 } 80 // 找出必须要选择的鹅卵石路 81 82 initset(); 83 for (int i=0;i<mustchoose.size();i++) 84 { 85 int fa=find(edge[mustchoose[i]].u),fb=find(edge[mustchoose[i]].v); 86 unionset(fa,fb); 87 } 88 for (int i=R;i<=m;i++) 89 if (t<k && !vis[i]) 90 { 91 int fa=find(edge[i].u),fb=find(edge[i].v); 92 if (fa!=fb) 93 { 94 unionset(fa,fb); 95 vis[i]=1; 96 t++; 97 } 98 } 99 if (t<k)100 {101 puts("no solution");102 return;103 }104 //先选择必须要的鹅卵石路，然后再用其他鹅卵石路填充105 106 for (int i=1;i<=L;i++)107 {108 int fa=find(edge[i].u),fb=find(edge[i].v);109 if (fa!=fb)110 {111 unionset(fa,fb);112 vis[i]=1;113 }114 } 115 for (int i=1;i<=L;i++) if (vis[i]) printf("%d %d %d\n",edge[i].u,edge[i].v,1);116 for (int i=R;i<=m;i++) if (vis[i]) printf("%d %d %d\n",edge[i].u,edge[i].v,0);117 }118 119 int main()120 {121 init();122 solve();123 }
【Kruskal+贪心思想】BZOJ3624-[Apio2008]免费道路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。