首页 > 代码库 > 【bzoj2654】 tree
【bzoj2654】 tree
http://www.lydsy.com/JudgeOnline/problem.php?id=2654 (题目链接)
今天考试题,以为是神题不可做,直接放弃了。。没想到这么水。。
题意:给你一个无向带权连通图,每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。题目保证有解。
solution
我们考虑把白边的权值增加,因为无论白边的权值增加多少,最小生成树中的白边不会改变。所以我们二分每次把所有白边的权值增加多少,按边权大小排序后克鲁斯卡尔看选出的白边是否大于need。统计答案。
代码:
// bzoj2654#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=1000010;struct edge { int u,v,w,c; friend bool operator < (const edge &a,const edge &b) { return a.w==b.w?a.c<b.c:a.w<b.w; }}e[maxn];LL fa[maxn],u[maxn],v[maxn],w[maxn],c[maxn],tot,cnt,n,m,ned,sumv;int find(int x) { return x==fa[x]?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++) { e[i].u=u[i],e[i].v=v[i],e[i].w=w[i],e[i].c=c[i]; if (!c[i]) e[i].w+=x; } sort(e+1,e+m+1); for (int i=1;i<=m;i++) { int p=find(e[i].u),q=find(e[i].v); if (p!=q) { fa[p]=q; tot+=e[i].w; if (!e[i].c) cnt++; } } return cnt>=ned;}int main() { scanf("%lld%lld%lld",&n,&m,&ned); for (int i=1;i<=m;i++) { scanf("%lld%lld%lld%lld",&u[i],&v[i],&w[i],&c[i]); u[i]++;v[i]++; } int l=-10005,r=10005; while (l<=r) { int mid=(l+r)>>1; if (check(mid)) l=mid+1,sumv=tot-ned*mid; else r=mid-1; } printf("%lld",sumv); return 0;}
【bzoj2654】 tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。