首页 > 代码库 > bzoj 3624: [Apio2008]免费道路 生成树的构造

bzoj 3624: [Apio2008]免费道路 生成树的构造

2024-07-29 04:44:52   219人阅读

3624: [Apio2008]免费道路

Time Limit: 2 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 111  Solved: 49
[Submit][Status]

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
1 2 1
 
　　还是看的网上的标程。。。。。
　　这道题的做法是先1边优先，做生成树，如果0边个数大于k无解，否则随便假如能加的0边补足k条，剩下由1边补足。
　　这个怎么证明呢？我们考虑第一遍找出的0边最少的生成树，当我们随机加入一条0边，保证不存在0边环，那么我们都能删去一个1边，这个由第一颗生成树尽量加入1边的性质可得，那么以上的做法就可以理解了。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<vector>using namespace std;#define MAXN 1000010struct edge{        int x,y;};vector<edge> v0,v1;bool vis0[MAXN],vis1[MAXN];int uf[MAXN];int get_fa(int now){        return (uf[now]==now)?now:uf[now]=get_fa(uf[now]);}bool comb(int x,int y){        x=get_fa(x);        y=get_fa(y);        if (x==y)return 0;        uf[x]=y;        return 1;}int main(){        freopen("input.txt","r",stdin);        int n,m,i,j,k,x,y,z;        int cnt=0;;        int tot=0;        scanf("%d%d%d",&n,&m,&k);        edge et;        for (i=0;i<=n;i++)                uf[i]=i;        for (i=0;i<m;i++)        {                scanf("%d%d%d",&et.x,&et.y,&z);                if (z)                        v1.push_back(et);                else                        v0.push_back(et);        }        for (i=0;i<v1.size();i++)        {                comb(v1[i].x,v1[i].y);        }        for (i=0;i<v0.size();i++)        {                vis0[i]=comb(v0[i].x,v0[i].y);                cnt+=vis0[i];        }        if (cnt>k)        {                printf("no sulotion\n");                return 0;        }        for (i=0;i<=n;i++)                uf[i]=i;        for (i=0;i<v0.size();i++)        {                if (vis0[i])                        comb(v0[i].x,v0[i].y);        }        for (i=0;i<v0.size();i++)        {                if (cnt==k)break;                if (vis0[i])continue;                vis0[i]=comb(v0[i].x,v0[i].y);                cnt+=vis0[i];        }        for (i=0;i<v1.size();i++)        {                vis1[i]=comb(v1[i].x,v1[i].y);        }        for (i=0;i<v0.size();i++)                if (vis0[i])                        tot++;        for (i=0;i<v1.size();i++)                if (vis1[i])                        tot++;        if (cnt!=k || tot!=n-1)        {                printf("no solution\n");                return 0;        }        for (i=0;i<v0.size();i++)                if (vis0[i])                        printf("%d %d %d\n",v0[i].x,v0[i].y,0);        for (i=0;i<v1.size();i++)                if (vis1[i])                        printf("%d %d %d\n",v1[i].x,v1[i].y,1);}

 

 

bzoj 3624: [Apio2008]免费道路 生成树的构造


联系
我们