BZOJ 3624 Apio2008 免费道路

3624: [Apio2008]免费道路

Time Limit: 2 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 1709  Solved: 694
[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

Sample Output

3 2 0
4 3 0
5 3 1

模拟+并查集

最后如果有解的话，那么所有的道路会构成一棵树

首先确定哪些鹅卵石路必须选，然后判断是否大于k，如果大于则是no solution

然后包含必须选的鹅卵石路选择k条，最后确定水泥路

还有如果鹅卵石路本来就小于k的话也是no solution

#include <bits/stdc++.h>
#define ll long long
#define inf 100000000
using namespace std;
inline int read(){
    int x=0;int f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int MAXN=1e6+10;
int f[MAXN];
int u[MAXN],v[MAXN],c[MAXN],n,m,au[MAXN],ac[MAXN],num[3],av[MAXN],top,ans,vis[MAXN];
inline int find(int xx){
    return xx==f[xx]?xx:f[xx]=find(f[xx]);
}
inline void solve(int ine,int mx){
    for(int i=1;i<=m;i++){
        if(c[i]==ine&&num[ine]<mx){
            int fx=find(u[i]);int fy=find(v[i]);
            if(fx!=fy){
                vis[i]=1;f[fx]=fy;num[ine]++;
                au[++top]=u[i];av[top]=v[i];ac[top]=c[i];
            }
        }
    }
}
int main(){
    //freopen("All.in","r",stdin);
    //freopen("zh.out","w",stdout);
    n=read();m=read();int k=read();
    for(int i=1;i<=m;i++){
        u[i]=read();v[i]=read();c[i]=read();
    }
    for(int i=1;i<=n;i++) f[i]=i;
    solve(1,inf);solve(0,inf);
    if(num[1]+num[0]!=n-1||num[0]>k){
        cout<<"no solution"<<endl;
        return 0;
    }
    top=0;num[0]=num[1]=0;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++){
        if(vis[i]&&c[i]==0){
            int fx=find(u[i]);
            int fy=find(v[i]);
            if(fx!=fy){
                au[++top]=u[i];av[top]=v[i];ac[top]=c[i];
                num[0]++;f[fx]=fy;
            }
        }
    }
    solve(0,k);solve(1,inf);
    if(num[0]<k){
        cout<<"no solution"<<endl;
        return 0;
    }
    for(int i=1;i<=top;i++){
        printf("%d %d %d
",au[i],av[i],ac[i]);
    }
    return 0;
}