【HUST 1024 】拆点+二分枚举可行流

题目链接：http://acm.hust.edu.cn/problem.php?id=1024

题目大意：有n个男孩和n个女孩参加party，现在让你将他们分成n对不同的舞伴（只能男和女），男孩女孩可以和自己喜欢的人，最多和k个自己不喜欢的异性配对，现在问你能跳多少次舞（n对配完一次跳一次舞，每次的舞伴都不能重复）。

解题思路：网络流，关键在于建图。

把男性拆成两个点，分别放置在两个集合内，Xa和Xb，女性拆成两个点，分别放置在Ya和Yb内。Xa到Xb连接一条有向边，权值为k，Yb到Ya连接一条有向边，权值为k。当boy喜欢girl时，Xa和Ya之间连接一条对应的有向边权值为1，当boy不喜欢girl时，Xb和Yb连接一条对应的有向边，权值为1。

最后二分枚举可行解ans，超级源点到Xa的每个点连接一条有向边，权值为ans，Ya内的每个点和超级汇点连接一条有向边，权值也为ans。最后流啊流，最大流满足max_flow==n*ans时，继续二分，直到找到最优解。

这里要注意的是用一个tmp数组保存每条边的起始容量。

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cstring>
  5 using namespace std;
  6 
  7 const int mn=1024;
  8 const int mm=1000000;
  9 const int oo=0x3fffffff;
 10 int node, st, sd, edge;
 11 int flow[mm], reach[mm], next[mm], tmp[mm];
 12 int head[mn], work[mn], dis[mn], que[mn];
 13 int map[110][110];
 14 
 15 void init(int node_, int st_, int sd_)
 16 {
 17     node=node_, st=st_, sd=sd_;
 18     for(int i=0; i<node; i++) head[i]=-1;
 19     edge=0;
 20 }
 21 
 22 void addedge(int u, int v, int c1, int c2)
 23 {
 24     reach[edge]=v, flow[edge]=c1, tmp[edge]=c1, next[edge]=head[u], head[u]=edge++;
 25     reach[edge]=u, flow[edge]=c2, tmp[edge]=c2, next[edge]=head[v], head[v]=edge++;
 26 }
 27 
 28 bool bfs()
 29 {
 30     int u, v, l=0, h=0;
 31     for(int i=0; i<node; i++) dis[i]=-1;
 32     que[l++]=st;
 33     dis[st]=0;
 34     while(l!=h)
 35     {
 36         u=que[h++];
 37         if(h==mn) h=0;
 38         for(int i=head[u]; i>=0; i=next[i])
 39         {
 40             v=reach[i];
 41             if(flow[i]&&dis[v]<0)
 42             {
 43                 dis[v]=dis[u]+1;
 44                 que[l++]=v;
 45                 if(l==mn) l=0;
 46                 if(v==sd) return true;
 47             }
 48         }
 49     }
 50     return false;
 51 }
 52 
 53 int dfs(int u, int exp)
 54 {
 55     if(u==sd) return exp;
 56     for(int &i=work[u]; i>=0; i=next[i])
 57     {
 58         int v=reach[i], tp;
 59         if(flow[i]&&dis[v]==dis[u]+1&&(tp=dfs(v,min(flow[i],exp))>0))
 60         {
 61             flow[i]-=tp;
 62             flow[i^1]+=tp;
 63             return tp;
 64         }
 65     }
 66     return 0;
 67 }
 68 
 69 int Dinic()
 70 {
 71     int max_flow=0, flow;
 72     while(bfs())
 73     {
 74         for(int i=0; i<node; i++) work[i]=head[i];
 75         while(flow=dfs(st,oo)) max_flow+=flow;
 76     }
 77     return max_flow;
 78 }
 79 
 80 void Update(int mid)
 81 {
 82     for(int i=0; i<edge; i++) flow[i]=tmp[i];
 83     for(int i=head[st]; i>=0; i=next[i])
 84     {
 85         flow[i]=mid;
 86         flow[i^1]=0;
 87     }
 88     for(int i=head[sd]; i>=0; i=next[i])
 89     {
 90         flow[i]=0;
 91         flow[i^1]=mid;
 92     }
 93 }
 94 
 95 int main()
 96 {
 97     int T, n, m, k;
 98     cin >> T;
 99     while(T--)
100     {
101         cin >> n >> m >> k;
102         init(4*n+2,0,4*n+1);
103         memset(map,0,sizeof(map));
104         while(m--)
105         {
106             int u, v;
107             scanf("%d%d",&u,&v);
108             map[u][v]=1;
109         }
110         for(int i=1; i<=n; i++)
111             for(int j=1; j<=n; j++)
112             {
113                   if(map[i][j])  addedge(i,3*n+j,1,0);
114                   else addedge(n+i,2*n+j,1,0);
115             }
116         for(int i=1; i<=n; i++)
117         {
118             addedge(st,i,0,0);
119             addedge(3*n+i,sd,0,0);
120             addedge(i,n+i,k,0);
121             addedge(2*n+i,3*n+i,k,0);
122         }
123         int l=0, r=n, mid, ans=0;
124         while(l<=r)
125         {
126             mid=(l+r)>>1;
127             Update(mid);
128             if(Dinic()==n*mid)
129             {
130                 ans=mid;
131                 l=mid+1;
132             }
133             else r=mid-1;
134         }
135         cout << ans <<endl;
136     }
137     return 0;
138 }

【HUST 1024 】 拆点+二分枚举可行流

【HUST 1024 】拆点+二分枚举可行流