?id=3624 (题目链接)
题意给出一张无向图，其中有0类边和1类边。问能否构成正好有K条0类边的生成树，并输出方案。
Solution先将所有1类边加入生成树，然后再加入0类边，那么现在加入的0类边就是必须加入的0类边，将它们打上标记。然后再将并查集初始化，，继续加0类边直到数量达到K，最后加1类边。
代码// bzoj3624 #include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<cmath> #define LL long long #define inf 2147483640 #define Pi acos(-1.0) #define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); using namespace std; const int maxn=20010,maxm=100010; struct edge {int u,v,w;}e[2][maxm],ans[maxm]; int n,m,K,M[2],fa[maxn]; int find(int x) { return fa[x]==x ? x : fa[x]=find(fa[x]); } int main() { scanf("%d%d%d",&n,&m,&K); for (int u,v,w,i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); e[w][++M[w]]=(edge){u,v,w}; } int cnt=0,s=0; for (int i=1;i<=n;i++) fa[i]=i; for (int i=1;i<=M[1];i++) { int r1=find(e[1][i].u),r2=find(e[1][i].v); if (r1!=r2) cnt++,fa[r1]=r2; } if (cnt<n-1) { for (int i=1;i<=M[0];i++) { int r1=find(e[0][i].u),r2=find(e[0][i].v); if (r1!=r2) ans[++s]=e[0][i],cnt++,fa[r1]=r2; } if (cnt<n-1 || s>K) {puts("no solution");return 0;} } for (int i=1;i<=n;i++) fa[i]=i; for (int i=1;i<=s;i++) fa[find(ans[i].u)]=find(ans[i].v); for (int i=1;i<=M[0];i++) { if (s==K) break; int r1=find(e[0][i].u),r2=find(e[0][i].v); if (r1!=r2) ans[++s]=e[0][i],fa[r1]=r2; } if (s<K) {puts("no solution");return 0;} for (int i=1;i<=M[1];i++) { int r1=find(e[1][i].u),r2=find(e[1][i].v); if (r1!=r2) ans[++s]=e[1][i],fa[r1]=r2; } for (int i=1;i<=s;i++) printf("%d %d %d\n",ans[i].u,ans[i].v,ans[i].w); return 0; }
【bzoj3624】Apio2008—免费道路