圆桌问题【网络流24题】

思路

　　题目已经给出了暗示

　　即题目中给出了一个二分图

　　显然，可以把人和桌子作为二分图的两个阵营

　　由于题目中给出的限制：每个单位的人都必须坐在不同的桌子上

　　所以把单位向每个桌子连一条流量为1的边

　　由S向单位连单位人数的边　

　　由桌子向T连桌子容量的边　　

　　然后跑一次最大流，最后枚举每个单位的邻接边，通过判断残量网络上的值可以求出这个人去了哪张桌子

　　朴素的Dinic会T最后一个点

　　考虑当前弧优化来优化朴素Dinic算法，只需要70ms即可跑完

CODE

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 const int inf = 0x3f3f3f3f;
 10 
 11 template<class T>inline void read(T &res)
 12 {
 13     char c;T flag=1;
 14     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 15     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 16 }
 17 
 18 namespace _buff {
 19     const size_t BUFF = 1 << 19;
 20     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 21     char getc() {
 22         if (ib == ie) {
 23             ib = ibuf;
 24             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 25         }
 26         return ib == ie ? -1 : *ib++;
 27     }
 28 }
 29 
 30 int qread() {
 31     using namespace _buff;
 32     int ret = 0;
 33     bool pos = true;
 34     char c = getc();
 35     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 36         assert(~c);
 37     }
 38     if (c == '-') {
 39         pos = false;
 40         c = getc();
 41     }
 42     for (; c >= '0' && c <= '9'; c = getc()) {
 43         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 44     }
 45     return pos ? ret : -ret;
 46 }
 47 
 48 const int maxn = 5e4 + 7;
 49 
 50 int s, t, cnt = 1;
 51 int head[maxn << 1], edge[maxn << 1], nxt[maxn << 1], vis[maxn << 1];
 52 int w[maxn << 1];//残量网络
 53 int rev[maxn << 1];
 54 int depth[maxn << 1];//图层
 55 int n, m;
 56 int cur[maxn << 1];//当前弧优化
 57 
 58 void BuildGraph(int u, int v, int cap) {
 59     ++cnt;
 60     edge[cnt] = v;
 61     nxt[cnt] = head[u];
 62     rev[cnt] = cnt + 1;
 63     w[cnt] = cap;
 64     head[u] = cnt;
 65 
 66     ++cnt;
 67     edge[cnt] = u;
 68     nxt[cnt] = head[v];
 69     w[cnt] = 0;
 70     rev[cnt] = cnt - 1;
 71     head[v] = cnt;
 72 }
 73 
 74 bool bfs(int x) {
 75     queue<int> q;
 76     for ( int i = 0; i <= t; ++i ) {
 77         cur[i] = head[i];
 78     }
 79     while(!q.empty()) {
 80         q.pop();
 81     }
 82     memset(depth, 63, sizeof(depth));
 83     depth[s] = 0;
 84     q.push(s);
 85     do {
 86         int u = q.front();
 87         q.pop();
 88         for ( int i = head[u]; i; i = nxt[i] ) {
 89             int v = edge[i];
 90             if(w[i] > 0 && depth[u] + 1 < depth[v]) {
 91                 depth[v] = depth[u] + 1;
 92                 q.push(v);
 93                 if(v == t) {
 94                     return true;
 95                 }
 96             }
 97         }
 98     } while (!q.empty());
 99     if(depth[t] < inf)
100         return true;
101     return false;
102 }
103 
104 int dfs(int u, int dist) {
105     if(!dist || u == t) {
106         return dist;
107     }
108     int flow = 0, f;
109     for ( int i = cur[u]; i; i = nxt[i] ) {
110         cur[u] = 1;
111         int v = edge[i];
112         if(depth[v] == depth[u] + 1 && (f = dfs(v, min(dist, w[i])))) {
113             flow += f;
114             dist -= f;
115             w[i] -= f;
116             w[i ^ 1] += f;
117             if(!dist)
118                 break;
119         }
120     }
121     return flow;
122 }
123 
124 int pp[maxn];
125 int table[maxn];
126 int sum = 0;
127 
128 int main()
129 {
130     //freopen("data.txt", "r", stdin);
131     read(m); read(n);
132     for ( int i = 1; i <= m; ++i ) {
133         read(pp[i]);
134         sum += pp[i];
135     }
136     for ( int i = 1; i <= n; ++i ) {
137         read(table[i]);
138     }
139     s = 0, t = n + m + 1;
140     for ( int i = 1; i <= m; ++i ) {
141         BuildGraph(s, i, pp[i]);
142         for ( int j = 1; j <= n; ++j ) {
143             BuildGraph(i, j + m, 1);
144         }
145     }
146     for ( int i = 1; i <= n; ++i ) {
147         //printf("table[%d]:%d\n",i, table[i]);
148         BuildGraph(i + m, t, table[i]);
149     }   
150     //dbg(sum);
151     int ans = 0;
152     while(bfs(s)) {
153         ans += dfs(0, 0x7f7f7f7f);
154     }
155     //dbg(ans);
156     if(sum != ans) {
157         puts("0");
158     }
159     else {
160         cout << 1 << endl;
161         for ( int i = 1; i <= m; ++i ) {
162             for ( int j = head[i]; j; j = nxt[j] ) {
163                 int to = edge[j];
164                 if(to != t && !w[j]) {
165                     printf("%d ",to - m);
166                     //printf("cap[%d]:%d\n",j, w[j]);
167                 }
168             }
169             puts("");
170         }
171     }
172     return 0;
173 }