bzoj2654 tree

bzoj2654 tree

​​ 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 HINT

原数据出错，现已更新 by liutian,但未重测—2016.6.24

考虑到如果我们人为的去增加白边的权值那么由于kruskal贪心的策略我们的白边数一定是单调的

那么我们不妨每次二分一个答案然后生成下最小生成树 统计一下白边的数量

但是有一些小细节的地方 比如我二分Mid的时候生成树中的白边数大于等于我需要的need然而

再次二分到mid+1的时候发现又小于我的need了 这种情况乍一看是无解 ，我确实也想了很久

网上题解说这种情况是因为有许许多多的相同权值的白边和黑边出现 ，但是按照kruskal我排序的时候我黑白边的选取可是随机的啊，后来仔细想想，我每次排序的时候强制白边在前面不就好了啊

这种情况，我们应该在树中白边大于等于我们需要的白边时就进行统计 因为保证存在数据 所以多余的白边一定可以用黑边替代掉的

#include#include#define N 55000#define M 110000using namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f; }struct node{ int x,y,z,c;}data[M];int fa[N],ans1,n,m,need,need1,ans,cnt;inline bool cmp(node a ,node b){return a.z==b.z?a.c>1; for (int i=1;i<=n;++i) fa[i]=i;ans1=0;cnt=0;need1=0; for (int i=1;i<=m;++i) if (!data[i].c) data[i].z+=mid;sort(data+1,data+m+1,cmp); for (int i=1;i<=m;++i){ int xx=find(data[i].x),yy=find(data[i].y); if (xx!=yy){ ++cnt;fa[xx]=yy;ans1+=data[i].z;if (!data[i].c) need1++; if (cnt==n-1) break; } } if (need1>=need) ans=ans1-need*mid,l=mid+1;else r=mid-1; for (int i=1;i<=m;++i) if (!data[i].c) data[i].z-=mid; } printf("%d\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。