P3623 [APIO2008] 免费道路

· · 题解

P3623 [APIO2008] 免费道路

题目翻译：

给定一个无向联通图，图中的边有两种类型1或0，求生成一棵树使得类型为0的边要为k个。

思路：

阅读题目发现，最后的图要是一棵树，使得上面边为0的个数为k,我们可以想到先找到，k个边在找其他边，但又要满足图的联通，那我们运用最小生成树kruskal算法的思想，先将类型为1的边给进行加边，若继续加类型0的边，那这些边就是一定需要的，不管这么搭配，这些边就是必要的。那第二次跑kruskal时就先加剩下需要的类型为0的边，直到数量满足为k时停止，然后加类型为1的边直至联通。

无解判定：

1.若第一次跑kruskal时发现必须的边数超过了k那必然无解
2.若第二次跑完kruskal时发现无法组成一棵树，或总共加入的类型为零的边不及k个，则无解

完整代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int fa[N];
int n,m,k,cnt;
struct edge{
    int u,v,w;
}e[N];
bool cmp1(edge x,edge y){
    return x.w<y.w;
}
bool cmp2(edge x,edge y){
    return x.w>y.w;
}
int find(int x){
    if(fa[x]==x)return x;
    else return fa[x]=find(fa[x]);
}
void kruskal1(){
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    sort(e+1,e+1+m,cmp1);
    for(int i=1;i<=m;i++){
        int u=find(e[i].u);
        int v=find(e[i].v);
        if(u!=v){
            fa[u]=v;
            if(e[i].w==1){
                cnt++;
                e[i].w=3;
            }
        }
    }
    if(cnt>k){
        cout<<"no solution"<<endl;
        exit(0);
    }
}
void kruskal2(){
    int num=0;
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    sort(e+1,e+1+m,cmp2);
    for(int i=1;i<=m;i++){
        int u=find(e[i].u);
        int v=find(e[i].v);
        if(find(u)!=find(v)){
            if(e[i].w==1 && cnt==k){
                continue;
            }
            num++;
            fa[u]=v;
            if(e[i].w==1 && cnt<k){
                e[i].w=3;
                cnt++;
            }
            else if(e[i].w==0){
                e[i].w=-2;
            }
        }
    }
    if(num<n-1 || cnt<k){
        cout<<"no solution"<<endl;
        exit(0);
    }
    for(int i=1;i<=m;i++){
        if(e[i].w==3)cout<<e[i].u<<" "<<e[i].v<<" "<<0<<endl;
        if(e[i].w==-2)cout<<e[i].u<<" "<<e[i].v<<" "<<1<<endl;
    }
}
signed main(){

    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        w=!w;
        e[i]={u,v,w};
    }
    kruskal1();
    kruskal2();
}

最小生成树kruskal讲解