首页 > 代码库 > HDU 3081 Marriage Match II
HDU 3081 Marriage Match II
http://acm.hdu.edu.cn/showproblem.php?pid=3081
题意：有2N个孩子，其中有N个女生，N个男生，每一个女生可以找一个没有争吵过得男生组成一个家庭，并且可以和与她关系好的女生互换男生。问能交换多少次。
题解：最少交换0次，最多交换2*N次。需要用并查集处理好女生直接的关系。然后二分，建立网络流。
建边：源点和女生建边，容量为mid；女生和可以交换的男生建边，容量为1；男生和汇点建边，容量为mid。
可行条件：如果最大流==N*mid，表示可以交换这么多次。
但是不知道为什么在unite()之后还要找一下每一个点的par？？为什么？？？
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <cmath> 6 #include <string> 7 #include <vector> 8 #include <list> 9 #include <map> 10 #include <queue> 11 #include <stack> 12 #include <bitset> 13 #include <algorithm> 14 #include <numeric> 15 #include <functional> 16 #include <set> 17 #include <fstream> 18 19 using namespace std; 20 21 const int INF=0xfffffff; 22 23 const int maxn=510; 24 const int maxm=50010; 25 26 struct edge{ 27 int to,next,cap; 28 }G[maxm]; 29 struct node{ 30 int girl,boy; 31 }friend1[maxm]; 32 int judge[maxn][maxn]; 33 int head[maxn],idx,sum; 34 int level[maxn]; 35 int gap[maxn]; 36 int par[maxn]; 37 int rankh[maxn]; 38 int N,M,F; 39 int s,t; 40 41 void add_edge(int from,int to,int cap) 42 { 43 G[idx].to=to; 44 G[idx].cap=cap; 45 G[idx].next=head[from]; 46 head[from]=idx++; 47 48 G[idx].to=from; 49 G[idx].cap=0; 50 G[idx].next=head[to]; 51 head[to]=idx++; 52 } 53 54 int dfs(int pos,int cost,int cnt) 55 { 56 if(pos==t) 57 { 58 return cost; 59 } 60 int minh=cnt-1; 61 int lv=cost; 62 int d; 63 for(int j=head[pos];j!=-1;j=G[j].next) 64 { 65 int v=G[j].to,cap=G[j].cap; 66 if(cap>0) 67 { 68 if(level[v]+1==level[pos]) 69 { 70 if(lv<G[j].cap) d=lv; 71 else d=G[j].cap; 72 73 d=dfs(v,d,cnt); 74 G[j].cap-=d; 75 G[j^1].cap+=d; 76 lv-=d; 77 if(level[s]>=cnt) return cost-lv; 78 if(lv==0) break; 79 } 80 if(level[v]<minh) minh=level[v]; 81 } 82 } 83 if(lv==cost) 84 { 85 --gap[level[pos]]; 86 if(gap[level[pos]]==0) level[s]=cnt; 87 level[pos]=minh+1; 88 ++gap[level[pos]]; 89 } 90 91 return cost-lv; 92 } 93 94 int sap(int s,int t,int cnt) 95 { 96 int flow=0; 97 gap[s]=cnt; 98 while(level[s]<cnt) 99 {100 flow+=dfs(s,INF,cnt);101 }102 //printf("...%d\n",flow);103 return flow;104 }105 106 void initu(int n)107 {108 for(int i=0;i<=n;i++)109 {110 par[i]=i;111 rankh[i]=0;112 }113 }114 115 int find(int x)116 {117 if(par[x]==x){118 return x;119 }120 else{121 return par[x]=find(par[x]);122 }123 }124 125 void unite(int x,int y)126 {127 x=find(x);128 y=find(y);129 if(x==y) return;130 if(rankh[x]<rankh[y]){131 par[x]=y;132 rankh[y]+=rankh[x];133 }134 else{135 par[y]=x;136 // rankh[x]++;137 rankh[x]+=rankh[y];138 }139 }140 141 void build(int cap)142 {143 s=0;144 t=2*N+1;145 idx=0;146 memset(gap,0,sizeof(gap));147 memset(level,0,sizeof(level));148 memset(head,-1,sizeof(head));149 memset(judge,0,sizeof(judge));150 for(int i=1;i<=N;i++)151 {152 add_edge(s,i,cap);153 add_edge(N+i,t,cap);154 }155 for(int i=1;i<=M;i++)156 {157 int x=friend1[i].girl;158 int y=friend1[i].boy;159 for(int j=1;j<=N;j++)160 {161 if(par[x]==par[j]&&!judge[j][y]){162 add_edge(j,N+y,1);163 judge[j][y]=1;164 }165 }166 }167 }168 169 int main()170 {171 //freopen("/Users/apple/Desktop/暑假/26.1/26.1/in","r",stdin);172 int T;173 scanf("%d",&T);174 while(T--)175 {176 scanf("%d%d%d",&N,&M,&F);177 for(int i=1;i<=M;i++)178 scanf("%d%d",&friend1[i].girl,&friend1[i].boy);179 initu(2*N);180 for(int i=0;i<F;i++)181 {182 int x,y;183 scanf("%d%d",&x,&y);184 unite(x,y);185 }186 // for(int i=1;i<=2*N;i++)187 // {188 // //par[i]=find(i);189 // printf("%d %d\n",i,par[i]);190 // }191 for(int i=1;i<=2*N;i++)192 {193 par[i]=find(i);194 //printf("%d %d\n",i,par[i]);195 }196 // for(int i=1;i<=2*N;i++)197 // {198 // //par[i]=find(i);199 // printf("----%d %d\n",i,par[i]);200 // }201 int low=0;202 int high=N;203 int res=0;204 while(low<=high)205 {206 int mid=(low+high)/2;207 build(mid);208 if(sap(s,t,t+1)==N*mid)209 {210 low=mid+1;211 res=mid;212 }213 else214 high=mid-1;215 }216 printf("%d\n",res);217 }218 return 0;219 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。