「BZOJ2654」tree
Description
给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。
题目保证有解。
Input
第一行V,E,need分别表示点数，边数和需要的白色边数。
接下来E行
每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。
Output
一行表示所求生成树的边权和。
Sample Input
2 2 1
0 1 1 1
0 1 2 0
0 1 1 1
0 1 2 0
Sample Output
2
HINT
数据规模和约定
0:V<=10
1,2,3:V<=15
0,..,19:V<=50000,E<=100000
所有数据边权为[1,100]中的正整数。
题解
给白色边都加上一个值，做mst会使得选取的白边数量减少，所以可以二分它
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include<iostream> #include<set> #include<map> #include<cstdio> #include<cstring> #include<cstdlib> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<cmath> #define inf 1000000000 #define pa pair<int,int> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,cnt,tot,ned; int sumv; int u[100005],v[100005],w[100005],c[100005]; int fa[100005]; struct edge{ int u,v,w,c; }e[100005]; bool operator<(edge a,edge b) { return a.w==b.w?a.c<b.c:a.w<b.w; } 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() { n=read();m=read();ned=read(); for(int i=1;i<=m;i++) { u[i]=read(),v[i]=read(),w[i]=read(),c[i]=read(); u[i]++;v[i]++; } int l=-105,r=105; while(l<=r) { int mid=(l+r)>>1; if(check(mid))l=mid+1,sumv=tot-ned*mid; else r=mid-1; } printf("%d",sumv); return 0; } |
计数器 9322833
OI 课件=>
OI 课件=>
弱弱的问一下 为什么边排序时为什么一定要白前黑后 黑白无序可以吗
无序的话二分会出问题吧
是的 没排序会wa 求解释
原来你还在线啊 orz
我要计算当前至多能取多少白边，当然要把白边放前面。由于保证有解，在cnt>=need且cnt取最小值的方案下，一定能有黑边把多余的白边代替掉
我的做法也许比较奇怪？
你看zky是这样做的：考虑把白色边权加上一个值x,那么最小生成树中的白色边数量的可行最大值g(x)与可行最小值f(x)随x增大而减小,然后就可以二分一个x使得need∈[f(x),g(x)]