题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3624
题意：求一个恰好用 k 条给定边集（记为黑边）中的点的生成树。
有趣的构造题，先不用黑边搞生成树，找出必选的黑边。然后重来，先连必选的黑边，然后随便连满黑边，再连白边，不影响连通性。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
#include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iomanip> #define N 20010 #define M 100010 using namespace std; 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 f[N]; int n,m,k,x,y,tot; int u[M],v[M]; bool type[M],pd[M]; int find(int x) {return f[x]==x?x:f[x]=find(f[x]);} int main() { n=read(),m=read(),k=read(); for(int i=1;i<=m;i++) { u[i]=read(),v[i]=read(),type[i]=read(); tot+=type[i]^1; } if(tot<k) { puts("no solution"); return 0; } for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++) { if(type[i]) { x=u[i],y=v[i]; if(find(x)!=find(y)) f[find(x)]=find(y); } } for(int i=1;i<=m;i++) { if(!type[i]) { x=u[i],y=v[i]; if(find(x)!=find(y)) { f[find(x)]=find(y); pd[i]=1; k--; } } } if(k<0) { printf("no solution\n"); return 0; } for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++) { if(pd[i]) { x=u[i],y=v[i]; f[find(x)]=find(y); } } for(int i=1;i<=m;i++) { if(!type[i]&&k) { x=u[i],y=v[i]; if(find(x)!=find(y)) { f[find(x)]=find(y); pd[i]=1; k--; } } } if(k) { puts("no solution"); return 0; } for(int i=1;i<=m;i++) { if(type[i]) { x=u[i],y=v[i]; if(find(x)!=find(y)) { f[find(x)]=find(y); pd[i]=1; } } } for(int i=1;i<=m;i++) { if(pd[i]) printf("%d %d %d\n",u[i],v[i],type[i]); } return 0; } |
Comments | NOTHING