首页 > 代码库 > 【bzoj2654】tree

【bzoj2654】tree

2024-09-16 09:58:04   215人阅读

 

Description

给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。
题目保证有解。

 

Input

第一行V,E,need分别表示点数，边数和需要的白色边数。
接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。

 

Output

一行表示所求生成树的边权和。
V<=50000,E<=100000,所有数据边权为[1,100]中的正整数。

 

 

Sample Input

2 2 1
0 1 1 1
0 1 2 0

Sample Output

2
 
这题挺有趣的
我们先不考虑白边的限制，那么就是一个最小生成树。
那么我们考虑限制白边数量为一，我们对执行最小生成树的方案做修改：把白边的边权增加。这样就会尽量少地添加白边。
然后我们考虑增加白边的数量，二分即可。
技术分享
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>using namespace std;const int N=100050;struct Edge{    int from,to,val,col;}edge[N];int from[N],to[N],val[N],col[N];int fa[N];int n,m,Need,ans,tot,cnt;inline void read(int &s){    int flag=1;s=0;char ch=getchar();    while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)flag=-1;ch=getchar();}    while(ch>=‘0‘ && ch<=‘9‘){s=s*10+ch-‘0‘;ch=getchar();}    s*=flag;}inline bool operator < (const Edge &a,const Edge &b){return a.val==b.val ? a.col<b.col : a.val<b.val;}int find(int x){return x==fa[x] ? fa[x] : fa[x]=find(fa[x]);}bool check(int x){    tot=cnt=0;    for(int i=1;i<=n;++i)fa[i]=i;    for(int i=1;i<=m;++i){        edge[i].from=from[i];edge[i].to=to[i];edge[i].val=val[i];edge[i].col=col[i];        if(!col[i])edge[i].val+=x;    }    sort(edge+1,edge+m+1);    for(int i=1;i<=m;++i){        int fx=find(edge[i].from),fy=find(edge[i].to);        if(fx!=fy){            fa[fx]=fy;            tot+=edge[i].val;            if(!edge[i].col)++cnt;        }    }    return cnt>=Need;}int main(){    read(n);read(m);read(Need);    for(int i=1;i<=m;++i){        read(from[i]);read(to[i]);read(val[i]);read(col[i]);        ++from[i];++to[i];    }    int l=-105,r=105;    while(l<=r){        int mid=(l+r)>>1;        if(check(mid))l=mid+1,ans=tot-Need*mid;        else r=mid-1;    }    printf("%d\n",ans);    return 0;}
bzoj2654

 

【bzoj2654】tree


联系
我们