注意
这题需要注意的有几点。
- 首先板子要快，尽量使用带当前弧优化的dinic，这样跑起来不会超时。
- 使用弧优化的时候，如果源点设置成0，记得将cur数组从0开始更新，因为有的板子并不是。
- 其次这题是多组样例输入，所以每次需要清空head数组，pre数组，deep数组，vis数组等等，以及建图之前将cnt设置为0。
题意
有n个女孩和n个男孩，给出哪些女孩和哪些男孩从未发生冲突，以及女孩之间的朋友关系，朋友关系是传递的。
每次所有女孩都选择不同一个男孩作为自己的伴侣，问能选择几轮？
女孩选择男孩的条件是，女孩从未和该男孩发生冲突，或者她的朋友从未和该男孩发生冲突。
思路
- 用并查集将女孩分组，同一个组内的女孩，共享他们喜欢的男孩。
- 然后就是二分图匹配，建立源点和汇点，源点连接女孩，汇点连接男孩（以下简称源点汇点路径），女孩喜欢男孩，就建一条边。
如果源点汇点路径权值为1，那么这个最大流跑出来就是女孩和男孩的最大匹配方案数。 - 这题问的是每次每位女孩都选择不同的男孩，并且每位女孩都要有人能匹配，所以，我们二分源点汇点路径的权值大小。
易知，如果源点汇点路径权值 k <= ans ,那么最大流 maxflow==n*k 。
因为每个人跑都是满流，所以此时可以尝试将k增加，如果不等于，说明k值过大，应将k值减小。
AC 31ms
#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=210;
const int maxm=21000;
bool bridge[maxn][maxn];
int pre[maxn];
struct Edge {
int from,to,cap,flow;
};
struct Dinic {
Edge edge[maxm];
int next[maxm];
int head[maxn];
int deep[maxn];
int cur[maxn];
int vis[maxn];
int n,m,s,t,cnt=0;
void init_point(int nn,int mm ,int ss,int tt) {
n=nn;
m=mm;
s=ss;
t=tt;
}
void init() {
memset(head,-1,sizeof(head));
cnt=0;
}
void addEdge(int u,int v,int w) {
edge[cnt].cap=w;
edge[cnt].flow=0;
edge[cnt].from=u;
edge[cnt].to=v;
next[cnt]=head[u];
head[u]=cnt++;
edge[cnt].cap=0;
edge[cnt].flow=0;
edge[cnt].from=v;
edge[cnt].to=u;
next[cnt]=head[v];
head[v]=cnt++;
}
void build(int value) {
init();
for (int i=1;i<=n;i++) {
addEdge(s,i,value);
}
for (int i=n+1;i<=2*n;i++) {
addEdge(i,t,value);
}
for (int i=1;i<=n;i++) {
for (int j=n+1;j<=2*n;j++) {
if (bridge[i][j]) {
addEdge(i,j,1);
}
}
}
// for (int i=0;i<=n;i++) {
// printf("%d:",i);
// for (int j=head[i];j!=-1;j=next[j]) {
// printf("%d %d %d ",edge[j].to,edge[j].cap,edge[j].flow);
// }
// printf("
");
// }
}
bool bfs() {
memset(vis,0,sizeof(vis));
memset(deep,0,sizeof(deep));
queue<int> q;
deep[s]=0;
vis[s]=true;
q.push(s);
while (!q.empty()) {
int u=q.front();
q.pop();
for (int i=head[u];i!=-1;i=next[i]) {
Edge &e=edge[i];
if (!vis[e.to]&&e.cap>e.flow) {
deep[e.to]=deep[u]+1;
vis[e.to]=true;
q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int u,int in) {
if (u==t||in==0) {
return in;
}
int out=0,f;
for (int& i=cur[u];i!=-1;i=next[i]) {
int v=edge[i].to;
if (deep[v]==deep[u]+1&&(f=dfs(v,min(in,edge[i].cap-edge[i].flow)))>0) {
edge[i].flow+=f;
edge[i^1].flow-=f;
out+=f;
in-=f;
if (in==0) {
break;
}
}
}
return out;
}
int maxflow() {
int ans=0;
while (bfs()) {
for (int i=0;i<=2*n+1;i++) {
cur[i]=head[i];
}
ans+=dfs(s,INF);
}
return ans;
}
}DC;
int findset(int x)
{
if (x==pre[x]) {
return x;
}
return pre[x]=findset(pre[x]);
}
void unions(int a,int b)
{
int x=findset(a);
int y=findset(b);
if (x!=y) {
pre[x]=y;
}
}
int main()
{
int T,f,n,m,x,y;
scanf("%d",&T);
while (T--) {
scanf("%d%d%d",&n,&m,&f);
DC.init_point(n,m,0,2*n+1);
memset(bridge,0,sizeof(bridge));
for (int i=0;i<maxn;i++) {
pre[i]=i;
}
for (int i=0;i<m;i++) {
scanf("%d%d",&x,&y);
bridge[x][y+n]=true;
}
for (int i=0;i<f;i++) {
scanf("%d%d",&x,&y);
unions(x,y);
}
for (int i=1;i<=n;i++) {
for (int j=i+1;j<=n;j++) {
if (findset(i)==findset(j)) {
for (int k=n+1;k<=2*n;k++) {
if (bridge[i][k]||bridge[j][k]) {
bridge[i][k]=bridge[j][k]=true;
}
}
}
}
}
int l=0,r=100,ans,mid;
while (l<=r) {
mid=(l+r)>>1;
DC.build(mid);
if (DC.maxflow()==n*mid) {
ans=mid;
l=mid+1;
}
else {
r=mid-1;
}
}
printf("%d
",ans);
}
return 0;
}