bzoj3624:[Apio2008]免费道路

传送门

显然是求生成树
只有两种情况会导致no solution：
1、如何加边图都不连通
2、必须要加的鹅卵石边超过k条
首先可以一遍kruskal判断出必须要加的鹅卵石边是多少：优先加水泥路的边
然后将必须要加的鹅卵石边加上去，再多加几条边使鹅卵石边等于k条，再去加水泥路
最后判断图是否联通就行了（也就是加的边数是否是n-1条）

现在考虑正确性：由于一开始处理出了必须要加的鹅卵石边，所以其他的鹅卵石边和水泥路边都是可以互相替换的，这样就可以保证剩下的边可以随便加了
代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
void read(int &x) {
    char ch; bool ok;
    for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
    for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
const int maxn=1e5+10;
int n,m,k,tot,f[maxn],ans,cnt,h[maxn];
struct oo{int x,y,z;}a[maxn];bool vis[maxn];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
bool cmp(oo a,oo b){return a.z>b.z;}
int main()
{
    read(n),read(m),read(k);
    for(rg int i=1;i<=n;i++)f[i]=i;
    for(rg int i=1;i<=m;i++)read(a[i].x),read(a[i].y),read(a[i].z);
    sort(a+1,a+m+1,cmp);
    for(rg int i=1;i<=m;i++)
        if(find(a[i].x)!=find(a[i].y))
        {
            int x=find(a[i].x),y=find(a[i].y);f[x]=y;
            if(!a[i].z)ans++,vis[i]=1;
        }
    if(ans>k){printf("no solution\n");return 0;}
    for(rg int i=1;i<=n;i++)f[i]=i;
    for(rg int i=m;i;i--)
        if(vis[i]){int x=find(a[i].x),y=find(a[i].y);f[x]=y;}
    for(rg int i=m;i;i--)
        if(find(a[i].x)!=find(a[i].y))
        {
            int x=find(a[i].x),y=find(a[i].y);f[x]=y;
            if(!a[i].z)ans++,vis[i]=1;
            if(ans==k)break;
        }
    for(rg int i=1;i<=m;i++)
        if(find(a[i].x)!=find(a[i].y))
        {
            int x=find(a[i].x),y=find(a[i].y);f[x]=y;
            vis[i]=1;if(!a[i].z)break; 
        }
    for(rg int i=1;i<=m;i++)if(vis[i])tot++;
    if(tot<n-1){printf("no solution\n");return 0;}
    for(rg int i=1;i<=m;i++)if(vis[i])printf("%d %d %d\n",a[i].x,a[i].y,a[i].z);
}

bzoj3624:[Apio2008]免费道路

原文：https://www.cnblogs.com/lcxer/p/10479025.html