首页 > 代码库 > HDU 3277 Marriage Match III
HDU 3277 Marriage Match III
http://acm.hdu.edu.cn/showproblem.php?pid=3277
题意：有2N个孩子，其中有N个女生，N个男生，每一个女生可以找一个没有争吵过得男生组成一个家庭，并且可以和与她关系好的女生互换男生。与
HDU 3081 Marriage Match II
不同的是，女生交换朋友的时候也不能和争吵过得男生组成家庭。
问能交换多少次。
题解：与3081那道题主要不同的地方是多了拆点。
建边：将女生拆点为女生1，女生2。源点和女生1建边，边权依旧是mid；男生和汇点建边，边权是mid；女生1和女生2建边，边权是K；如果女生和男生可以组成家庭，女生1和男生建 边，边权为1，否则女生2和男生建边，边权为2。
T了很多发……优化了并查集的判断。抄了别人的ISAP的板子http://www.350351.com/bianchengyuyan/Cyuyan/318117.html
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 const int maxm=10000010; 23 const int maxn=260; 24 25 struct edge{ 26 int u,v,cap,next; 27 }G[maxm]; 28 struct node{ 29 int girl,boy; 30 }friend1[maxm]; 31 int judge[maxn][maxn]; 32 int idx; 33 int head[maxn*maxn],level[maxn*maxn]; 34 int num[maxn*maxn]; 35 int cur[maxn*maxn]; 36 int pre[maxn*maxn]; 37 int s,t,tt; 38 int par[maxn*maxn]; 39 int rankh[maxn*maxn]; 40 int N,M,K,F; 41 42 void init(int n) 43 { 44 for(int i=0;i<=n;i++) 45 { 46 par[i]=i; 47 } 48 } 49 50 int find(int x) 51 { 52 if(par[x]==x){ 53 return x; 54 }else{ 55 return par[x]=find(par[x]); 56 } 57 } 58 59 void unite(int x,int y) 60 { 61 x=find(x); 62 y=find(y); 63 if(x==y) return; 64 else{ 65 par[x]=y; 66 } 67 } 68 69 void build(int u,int v,int cap) 70 { 71 G[idx].v=v; 72 G[idx].cap=cap; 73 G[idx].next=head[u]; 74 head[u]=idx++; 75 } 76 77 void add_edge(int u,int v,int cap) 78 { 79 build(u,v,cap); 80 build(v,u,0); 81 } 82 83 84 void bfs() 85 { 86 memset(level,-1,sizeof(level)); 87 memset(num,0,sizeof(num)); 88 queue<int>q; 89 q.push(t); 90 level[t]=0; 91 num[0]=1; 92 while(!q.empty()) 93 { 94 int u=q.front(); 95 q.pop(); 96 for(int i=head[u];i!=-1;i=G[i].next) 97 { 98 int v=G[i].v; 99 if(level[v]==-1)100 {101 level[v]=level[u]+1;102 num[level[v]]++;103 q.push(v);104 }105 }106 }107 }108 109 int ISAP()110 {111 memcpy(cur,head,sizeof(cur));112 bfs();113 int flow=0;114 int u=pre[s]=s;115 while(level[s]<tt)116 {117 if(u==t){118 int f=INF,pos;119 for(int i=s;i!=t;i=G[cur[i]].v)120 {121 if(f>G[cur[i]].cap){122 f=G[cur[i]].cap;123 pos=i;124 }125 }126 for(int i=s;i!=t;i=G[cur[i]].v)127 {128 G[cur[i]].cap-=f;129 G[cur[i]^1].cap+=f;130 }131 flow+=f;132 u=pos;133 }134 int i;135 for(i=cur[u];i!=-1;i=G[i].next)136 {137 if(level[G[i].v]+1==level[u]&&G[i].cap) break;138 }139 if(i!=-1){140 cur[u]=i;141 pre[G[i].v]=u;142 u=G[i].v;143 }144 else{145 if(--num[level[u]]==0) break;146 int mind=tt;147 for(int i=head[u];i!=-1;i=G[i].next)148 {149 if(mind>level[G[i].v]&&G[i].cap){150 mind=level[G[i].v];151 cur[u]=i;152 }153 }154 level[u]=mind+1;155 num[level[u]]++;156 u=pre[u];157 }158 }159 return flow;160 }161 162 void build_graph(int cap)163 {164 memset(head,-1,sizeof(head));165 idx=0;166 for(int i=1;i<=N;i++)167 {168 for(int j=1;j<=N;j++)169 {170 if(judge[find(i)][j]){171 add_edge(i,2*N+j,1);172 }173 else{174 add_edge(N+i,2*N+j,1);175 }176 }177 }178 for(int i=1;i<=N;i++)179 {180 add_edge(s,i,cap);//源点-女生(1~N)181 add_edge(2*N+i,t,cap);//男生-汇点(2*N+1~3*N)182 add_edge(i,N+i,K);//女生1-女生2183 }184 }185 186 int main()187 {188 // freopen("/Users/apple/Desktop/暑假/27(2)/27(2)/in","r",stdin);189 int T;190 scanf("%d",&T);191 while(T--)192 {193 scanf("%d%d%d%d",&N,&M,&K,&F);194 s=0;195 t=3*N+1;196 tt=t+1;197 memset(judge,0,sizeof(judge));198 199 for(int i=0;i<M;i++)200 scanf("%d%d",&friend1[i].girl,&friend1[i].boy);201 202 init(3*N);203 204 for(int i=0;i<F;i++)205 {206 int g1,g2;207 scanf("%d%d",&g1,&g2);208 unite(g1,g2);209 }210 for(int i=0;i<M;i++)211 {212 int x=friend1[i].girl,y=friend1[i].boy;213 judge[find(x)][y]=1;214 }215 216 int low=0;217 int high=N;218 int res=0;219 while(low<=high)220 {221 int mid=(low+high)/2;222 build_graph(mid);223 if(ISAP()>=N*mid) {224 res=mid;225 low=mid+1;226 }227 else{228 high=mid-1;229 }230 }231 printf("%d\n",res);232 }233 234 return 0;235 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。