HDOJ 3081 - Marriage Match II 并查集+构图最大流...

发布时间:2016-12-9 10:06:36 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDOJ 3081 - Marriage Match II 并查集+构图最大流...",主要涉及到HDOJ 3081 - Marriage Match II 并查集+构图最大流...方面的内容,对于HDOJ 3081 - Marriage Match II 并查集+构图最大流...感兴趣的同学可以参考一下。

                题意:                          有N个女孩和N个男孩玩过家家...某些女孩之间存在朋友关系..并且朋友关系可以传递.比如a和b是朋友..b和c是朋友...那么a,c就会是朋友...一个女生会选一个男生做男友必须这个男生至少和她朋友圈包括自己的某个女孩从没吵过架...每一轮进行一次配对...每轮必须每对都不同..问最多可以配对多少轮...                 题解:                          女孩间的朋友关系用并查集维护..二分轮数..设当前枚举的轮数为M.构图..超级源点向每个女孩做边容量为M..每个女孩向可以配对的男孩做边容量为1..每个男孩向超级汇点做边...容量为M..跑最大流..若MaxFlow==N*M则说明是可以到达该轮数的..                          据说还可以直接用匈牙利搞..每次找到最大匹配后把匹配的边删去..继续做..做了多少次找不到最大匹配等于N了就说明轮数找到了... Program: #include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #include<math.h> #include<queue> #define MAXN 2005 #define MAXM 20000005 #define oo 1000000007 #define ll long long using namespace std; struct Dinic { struct node { int x,y,c,next; }line[MAXM]; int Lnum,_next[MAXN],dis[MAXN],dp[MAXN]; bool inqueue[MAXN]; void initial(int n) { for (int i=0;i<=n;i++) _next[i]=-1; Lnum=-1; } void addline(int x,int y,int c) { line[++Lnum].next=_next[x],_next[x]=Lnum; line[Lnum].x=x,line[Lnum].y=y,line[Lnum].c=c; line[++Lnum].next=_next[y],_next[y]=Lnum; line[Lnum].x=y,line[Lnum].y=x,line[Lnum].c=0; } bool BFS(int s,int e) { queue<int> Q; while (!Q.empty()) Q.pop(); memset(dis,0,sizeof(dis)); dis[s]=1,Q.push(s); while (!Q.empty()) { int h,k; h=Q.front(),Q.pop(); if (h==e) return dis[e]; for (k=_next[h];k!=-1;k=line[k].next) if (line[k].c && !dis[line[k].y]) dis[line[k].y]=dis[h]+1,Q.push(line[k].y); } return false; } int dfs(int x,int flow,int e) { if (x==e) return flow; int temp,cost=0; for (int k=_next[x];k!=-1;k=line[k].next) if (line[k].c && dis[line[k].y]==dis[x]+1) { temp=dfs(line[k].y,min(flow-cost,line[k].c),e); if (temp) { line[k].c-=temp,line[k^1].c+=temp; cost+=temp; if (flow==cost) return cost; }else dis[line[k].y]=-1; } return cost; } int MaxFlow(int s,int e) { int MaxFlow=0; while (BFS(s,e)) MaxFlow+=dfs(s,oo,e); return MaxFlow; } }T; int father[105]; bool g[105][105]; int getfather(int x) { if (father[x]==x) return x; return father[x]=getfather(father[x]); } bool judge(int n,int M) { int i,j,s,e; s=n*2+5,e=s+1,T.initial(e); for (i=1;i<=n;i++) T.addline(s,i,M),T.addline(i+n,e,M); for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (g[father[i]][j]) T.addline(i,j+n,1); return T.MaxFlow(s,e)==n*M; } int main() { int C,cases,n,m,f,i,x,y; scanf("%d",&C); for (cases=1;cases<=C;cases++) { scanf("%d%d%d",&n,&m,&f); memset(g,false,sizeof(g)); while (m--) { scanf("%d%d",&x,&y); g[x][y]=true; } for (i=1;i<=n;i++) father[i]=i; while (f--) { scanf("%d%d",&x,&y),x=getfather(x),y=getfather(y); father[x]=y; for (i=1;i<=n;i++) g[y][i]=g[y][i]|g[x][i]; } for (i=1;i<=n;i++) getfather(i); int l=0,r=oo,mid; while (r-l>1) { mid=l+r>>1; if (judge(n,mid)) l=mid; else r=mid; } printf("%d\n",l); } return 0; }

上一篇:第十四章 其它特色
下一篇:找出数组中重复次数最多的数

相关文章

相关评论