P2619 [国家集训队2]Tree I
题意
题目描述
给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有\(need\)条白色边的生成树。
题目保证有解。
输入输出格式
输入格式：
第一行\(V,E,need\)分别表示点数，边数和需要的白色边数。
接下来\(E\)行
每行\(s,t,c,col\)表示这边的端点(点从\(0\)开始标号)，边权，颜色(\(0\)白色\(1\)黑色)。
输出格式：
一行表示所求生成树的边权和。
输入输出样例
输入样例#1：
2 2 1
0 1 1 1
0 1 2 0输出样例#1：
2说明
\(0:V<=10\)
\(1,2,3:V<=15\)
\(0,..,19:V<=50000,E<=100000\)
所有数据边权为\([1,100]\)中的正整数。
\(By\ WJMZBMR\)
思路
\(WQS\)二分真的强。
定义一个东西\(delta\)，把它加在所有白边的边权上。对原图直接跑最小生成树，如果白边少了，就调小\(delta\)；反之，则调大\(delta\)。最后得到答案。
证明并不会，只会感性理解（毕竟我是蒟蒻）。安利一篇博客好了：关于WQS二分算法以及其一个细节证明 --Creeper_LKF。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e4+4,MAXM=1e5+5;
int n,m,ned,ans,tot,fa[MAXN];
struct Edge
{int u,v,d,col;bool operator < (const Edge &sjf) const{if(d!=sjf.d) return d<sjf.d;return col<sjf.col;}
}edge[MAXM];
int read()
{int re=0;char ch=getchar();while(!isdigit(ch)) ch=getchar();while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();return re;
}
int fd(int x)
{int r=x;while(r!=fa[r]) r=fa[r];int i=x,j;while(i!=r) j=fa[i],fa[i]=r,i=j;return r;
}
bool check(int lzq)
{for(int i=0;i<m;i++) if(!edge[i].col) edge[i].d+=lzq;for(int i=0;i<n;i++) fa[i]=i;int white=0,cnt=1;tot=0;sort(edge,edge+m);for(int i=0;i<m;i++){int x=edge[i].u,y=edge[i].v;if(fd(x)==fd(y)) continue;fa[fd(x)]=fd(y),cnt++,tot+=edge[i].d,white+=(!edge[i].col);if(cnt==n) break;}for(int i=0;i<m;i++) if(!edge[i].col) edge[i].d-=lzq;return white>=ned;
}
int main()
{n=read(),m=read(),ned=read();for(int i=0;i<m;i++) edge[i].u=read(),edge[i].v=read(),edge[i].d=read(),edge[i].col=read();int L=-15000,R=15000;while(L<=R){int M=(L+R)>>1;if(check(M)) L=M+1,ans=tot-M*ned;else R=M-1;}printf("%d",ans);return 0;
}
