bzoj3624(铺黑白路)(并查集维护)

题意网上自己随便找,绝对是找的到的。

题解:(白边表示鹅卵石路,黑边表示水泥路)这道题的解法,先考虑将黑边所有都先连起来,组成一个又一个的联通块,然后用白边去连,

如果可以联通的话,就用白边去代替黑边,必要的白边(就是维护联通性的白边必须要先保证),然后再去代替,直到k条边满足,不满足则输出NO

然后就再用黑边去连,记录,反正是Special Judge所以顺序没有关系,就好了。

 #include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; typedef long long ll;
const int INF=1e9+,NN=,MM=; int n,m,K,top;
int fa[NN];
int u[MM],v[MM],c[MM];
int au[NN],av[NN],ac[NN];
bool mark[MM];
int num[]; int find(int num)
{
if (fa[num]==num) return num;
else fa[num]=find(fa[num]);
return fa[num];
}
void solve(bool typ,int up)
{
for(int i=;i<=m;i++)
if(c[i]==typ&&num[typ]<up)
{
int p=find(u[i]),q=find(v[i]);
if(p!=q)
{
fa[p]=q;
au[++top]=u[i],av[top]=v[i],ac[top]=c[i];
mark[i]=;
num[typ]++;
}
}
}
void init()
{
memset(mark,,sizeof(mark));
scanf("%d%d%d",&n,&m,&K);
for(int i=;i<=m;i++)
scanf("%d%d%d",&u[i],&v[i],&c[i]);
for(int i=;i<=n;i++)
fa[i]=i;
}
int main()
{
init(); num[]=num[]=;
solve(,INF),solve(,INF);
if(num[]+num[]!=n-||num[]>K)
{
puts("no solution\n");
return ;
}//及如果需要>k条鹅卵石路将各个块连起来,或者需要多余n-1条边 top=num[]=num[]=;//然后用鹅卵石重新铺
for(int i=;i<=n;i++)
fa[i]=i;
for(int i=;i<=m;i++)
if(c[i]==&&mark[i])
{
int p=find(u[i]),q=find(v[i]);
if(p!=q)
{
num[]++;fa[p]=q;
au[++top]=u[i];av[top]=v[i];ac[top]=c[i];
}
}//必要的先铺满
solve(,K),solve(,INF);//然后再不必要鹅卵石的取铺,然后再用水泥路取铺就可以了。
if(num[]<K)
{
puts("no solution");
return ;
}
for(int i=;i<=top;i++)
printf("%d %d %d\n",au[i],av[i],ac[i]);
}
上一篇:杭电60题--part 1 HDU1003 Max Sum(DP 动态规划)


下一篇:Merge branch 'master' of xxx error