首页 > 代码库 > [Apio2008]免费道路[Kruscal]
[Apio2008]免费道路[Kruscal]
3624: [Apio2008]免费道路
Time Limit: 2 Sec Memory Limit: 128 MBSec Special JudgeSubmit: 1292 Solved: 518
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
5 7 2
1 3 0
4 5 1
3 2 0
5 3 1
4 3 0
1 2 1
4 2 1
1 3 0
4 5 1
3 2 0
5 3 1
4 3 0
1 2 1
4 2 1
Sample Output
3 2 0
4 3 0
5 3 1
1 2 1
4 3 0
5 3 1
1 2 1
HINT
Source
自己的第一次思路：
小数据枚举k条鹅卵石路，大数据随机找k条鹅卵石路，跟剩下的水泥路构树，如果可以构成树，则此方案可行。
随机化的阈值我设置的是20.
然后就砍到72分。
#include<cmath>#include<ctime>#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int N=2e4+5;const int M=1e5+5;struct edge{int u,v,w,id;}e[M],z[M];int n,m,num0,K,tot,cct,fa[N],ans[M];int a[200];bool vis[200];inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}inline bool cmp(const edge &a,const edge &b){ return a.id<b.id;}inline bool cmp2(const edge &a,const edge &b){ return a.w<b.w;}int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]);}inline void pre(){ tot=0;ans[0]=0; for(int i=1;i<=n;i++) fa[i]=i; random_shuffle(e+1,e+num0+1); for(int i=1,x,y;i<=num0;i++){ x=find(e[i].u);y=find(e[i].v); if(x!=y){ fa[y]=x;ans[++ans[0]]=i; if(++tot==K) break; } }}inline void ord(){ tot=0;ans[0]=0; for(int i=1;i<=n;i++) fa[i]=i; for(int i=1,x,y;i<=K;i++){ x=find(e[a[i]].u);y=find(e[a[i]].v); if(x!=y){ fa[y]=x;ans[++ans[0]]=a[i]; if(++tot==K) break; } }}inline void work(){ for(int i=num0+1,x,y;i<=m;i++){ x=find(e[i].u);y=find(e[i].v); if(x!=y){ fa[y]=x;ans[++ans[0]]=i; if(++tot==n-1) break; } }}inline void print(){ for(int i=1;i<=ans[0];i++) z[i]=e[ans[i]]; sort(z+1,z+ans[0]+1,cmp); for(int i=1;i<=ans[0];i++) printf("%d %d %d\n",z[i].u,z[i].v,z[i].w);}void dfs(int x){ if(x>K){ ord();work(); if(tot==n-1){print();exit(0);} return ; } for(int i=a[x-1]+1;i<=num0;i++){ if(!vis[i]){ vis[i]=1; a[x]=i; if(num0-i<K-x) break; dfs(x+1); vis[i]=0; a[x]=0; } }}int main(){// freopen("sh.txt","r",stdin); srand(time(0)); n=read();m=read();K=read(); for(int i=1;i<=m;i++){ e[i].u=read(),e[i].v=read(),e[i].w=read(),e[i].id=i; if(!e[i].w) num0++; } sort(e+1,e+m+1,cmp2); if(K<=10){dfs(1);puts("no solution");return 0;} while(1){ pre(); if(tot!=n-1) work(); if(tot==n-1){print();return 0;} if(++cct==20) break; } puts("no solution");// cnt=ans[0];ans[0]=0;// for(int i=1;i<=ans[0];i++) printf("%d %d %d\n",e[ans[i]].u,e[ans[i]].v,e[ans[i]].w); /*for(int i=1;i<=cnt;i++) z[i]=e[ans[i]]; sort(z+1,z+cnt+1,cmp2); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1,tot=0,x,y;i<=cnt;i++){ x=find(z[i].u);y=find(z[i].v); if(x!=y){ fa[y]=x;ans[++ans[0]]=i; if(++tot==n-1) break; } }*/ /*cnt=ans[0];ans[0]=0; for(int i=1;i<=cnt;i++) e[i]=z[ans[i]]; sort(e+1,e+cnt+1,cmp);*/// for(int i=1;i<=cnt;i++) printf("%d %d %d\n",e[i].u,e[i].v,e[i].w); return 0;}
自己的第二次思路：（后悔当时为什么没有多想想）
2次kruscal解决。
第一次kruscal：首先考虑把所有水泥路连上。如果构不成树，则需要用鹅卵石路填边，这些鹅卵石路是必须要的鹅卵石路（如果必须要的鹅卵石路的数量>K直接无解）；剩下的鹅卵石路都是不必要的。
第二次kruscal：先把上一次找到的必须要的鹅卵石路填上，此时的鹅卵石路不一定恰有K条，可能比K条少，于是考虑优先连不必要的鹅卵石路，直到凑满K条为止，然后剩下的边随便找几条水泥路连起来就好（special judge告诉我们输出任意解均可）
#include<cstdio>#include<iostream>#include<algorithm>using namespace std;const int N=4e4+5;const int M=2e5+5;struct edge{int u,v,w,tag;}e[M];int n,m,K,tot,fa[N];inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]);}inline void ReadData(){ n=read();m=read();K=read(); for(int i=1;i<=m;i++) e[i].u=read(),e[i].v=read(),e[i].w=read(),e[i].tag=0;}inline void Kruscal1(){ int cct=0; for(int i=1;i<=n;i++) fa[i]=i; for(int i=1,x,y;i<=m;i++) if(e[i].w){//先铺水泥路 x=find(e[i].u);y=find(e[i].v); if(x!=y){ fa[y]=x; if(++cct==n-1) break; } } if(cct==n-1) return ; for(int i=1,x,y;i<=m;i++) if(!e[i].w){ x=find(e[i].u);y=find(e[i].v); if(x!=y){ fa[y]=x;tot++;e[i].tag=1;//必要鹅卵石 if(++cct==n-1) break; } }}inline void Kruscal2(){ int cct=0; for(int i=1;i<=n;i++) fa[i]=i; for(int i=1,x,y;i<=m;i++) if(e[i].tag){//整理找出的必要鹅卵石 x=find(e[i].u);y=find(e[i].v); if(x!=y){ fa[y]=x; if(++cct==n-1) break; } } for(int i=1,x,y;i<=m;i++) if(!e[i].w){ x=find(e[i].u);y=find(e[i].v); if(x!=y){ fa[y]=x;++cct;e[i].tag=1;//不必要鹅卵石补齐K条 if(++tot==K) break; } } if(tot!=K){puts("no solution");exit(0);} for(int i=1,x,y;i<=m;i++) if(e[i].w){//水泥路补齐n-1条 x=find(e[i].u);y=find(e[i].v); if(x!=y){ fa[y]=x;e[i].tag=1; if(++cct==n-1) break; } }}inline void WriteAns(){ for(int i=1;i<=m;i++) if(e[i].tag) printf("%d %d %d\n",e[i].u,e[i].v,e[i].w);} int main(){ ReadData(); Kruscal1(); Kruscal2(); WriteAns(); return 0;}
[Apio2008]免费道路[Kruscal]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。