做法1:上下界最小流
- 先来一发上下界最小流,思路比较暴力,就是把行和列看作n+mn+mn+m个点,(i,j)(i,j)(i,j)如果能占领就从第iii行向第jjj列连一条边,上界为1下界为0;然后从sss向每一行连边,上下界就是题目要求的范围;同理从每一列向ttt连边,上下界为题目需要的.做上下界最小流就行了.
- 不会的去这里liu_runda的博客
- Upd:Upd:Upd:这道题跟 BZOJ502BZOJ502BZOJ502 清理雪道 不完全一样,还需要加上从sss连出去的边的下界之和.因为第一次最大流求的是附加流的值,还需要加上下界的值才是对的
而在 BZOJ502BZOJ502BZOJ502 清理雪道中,从sss连出去的边下界都是000(或者说没有下界),所以不用加
CODE
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<typename T>inline void read(T &num) {
char ch; int flg=1;
while((ch=getchar())<'0'||ch>'9')if(ch=='-')flg=-flg;
for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());
num*=flg;
}
const int MAXN = 205;
const int MAXM = 50005;
const int inf = 1e9;
struct edge { int to, nxt, c, w, C; }e[MAXM];
int n, m, k, S, T, s, t, ss, tt, sz, cnt, fir[MAXN], info[MAXN];
inline void add(int u, int v, int cc) {
e[cnt] = (edge){ v, fir[u], cc }, fir[u] = cnt++;
e[cnt] = (edge){ u, fir[v], 0 }, fir[v] = cnt++;
}
int h[MAXN], gap[MAXN];
int aug(int u, int Max) {
if(u == T) return Max;
int flow = 0, delta, v;
for(int i = info[u]; ~i; i = e[i].nxt)
if(e[i].c && h[v=e[i].to]+1 == h[u]) {
delta = aug(v, min(Max-flow, e[i].c));
e[i].c -= delta, e[i^1].c += delta; info[u] = i;
if((flow+=delta) == Max || h[S] == sz) return flow;
}
if(!(--gap[h[u]])) h[S] = sz;
++gap[++h[u]]; info[u] = fir[u];
return flow;
}
inline int sap() {
memset(h, 0, sizeof h);
memset(gap, 0, sizeof gap);
memcpy(info, fir, sizeof fir);
int flow = 0;
while(h[S] < sz)
flow += aug(S, inf);
return flow;
}
inline void del(int u) {
for(int i = fir[u]; ~i; i = e[i].nxt) e[i].c = e[i^1].c = 0;
}
int L[105], C[105], g[105][105], sumL[105], sumC[105], deg[MAXN];
int main () {
memset(fir, -1, sizeof fir);
read(n), read(m), read(k); int flow0 = 0;
for(int i = 1; i <= n; ++i) read(L[i]), flow0 += L[i]; ///!!!加上下界!!!
for(int i = 1; i <= m; ++i) read(C[i]);
int x, y;
while(k--)
read(x), read(y), g[x][y] = 1, ++sumL[x], ++sumC[y];
s = 0; t = n+m+1; ss = T+1; tt = ss+1;
for(int i = 1; i <= n; ++i) {
if(sumL[i]+L[i] > m) return puts("JIONG!"), 0;
deg[s] -= L[i], deg[i] += L[i];
if(m-sumL[i]-L[i]) add(s, i, m-sumL[i]-L[i]);
}
for(int i = 1; i <= m; ++i) {
if(sumC[i]+C[i] > n) return puts("JIONG!"), 0;
deg[n+i] -= C[i], deg[t] += C[i];
if(n-sumC[i]-C[i]) add(n+i, t, n-sumC[i]-C[i]);
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
if(!g[i][j]) add(i, n+j, 1);
for(int i = s; i <= t; ++i)
if(deg[i] < 0) add(i, tt, -deg[i]);
else if(deg[i] > 0) add(ss, i, deg[i]);
add(t, s, inf); //形成循环流
S = ss, T = sz = tt;
sap();
flow0 += e[cnt-1].c; //加上附加流
e[cnt-1].c = e[cnt-2].c = 0;
del(ss), del(tt); //删去超级源点和汇点
S = t, T = s, sz = T; //因为是求最小流,所以从t->s流
printf("%d\n", flow0-sap());
}
做法2:直接最大流
题解摘自<<网络流的一些建模方法 姜志豪>>
- 这样简单多了…
- 注意一行(一列)的士兵多于了L[i](C[i])L[i](C[i])L[i](C[i])个时,是不会被算做贡献是2的士兵的,这样就保证了答案的正确性
CODE
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<typename T>inline void read(T &num) {
char ch; int flg=1;
while((ch=getchar())<'0'||ch>'9')if(ch=='-')flg=-flg;
for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());
num*=flg;
}
const int MAXN = 205;
const int MAXM = 50005;
const int inf = 1e9;
struct edge { int to, nxt, c, w, C; }e[MAXM];
int n, m, k, S, T, sz, cnt, fir[MAXN], info[MAXN];
inline void add(int u, int v, int cc) {
e[cnt] = (edge){ v, fir[u], cc }, fir[u] = cnt++;
e[cnt] = (edge){ u, fir[v], 0 }, fir[v] = cnt++;
}
int h[MAXN], gap[MAXN];
int aug(int u, int Max) {
if(u == T) return Max;
int flow = 0, delta, v;
for(int i = info[u]; ~i; i = e[i].nxt)
if(e[i].c && h[v=e[i].to]+1 == h[u]) {
delta = aug(v, min(Max-flow, e[i].c));
e[i].c -= delta, e[i^1].c += delta; info[u] = i;
if((flow+=delta) == Max || h[S] == sz) return flow;
}
if(!(--gap[h[u]])) h[S] = sz;
++gap[++h[u]]; info[u] = fir[u];
return flow;
}
inline int sap() {
memset(h, 0, sizeof h);
memset(gap, 0, sizeof gap);
memcpy(info, fir, sizeof fir);
int flow = 0;
while(h[S] < sz)
flow += aug(S, inf);
return flow;
}
int L[105], C[105], g[105][105], sumL[105], sumC[105];
int main () {
memset(fir, -1, sizeof fir);
read(n), read(m), read(k);
int sum = 0; S = 0, T = sz = n+m+1;
for(int i = 1; i <= n; ++i) read(L[i]), sum += L[i], add(S, i, L[i]);
for(int i = 1; i <= m; ++i) read(C[i]), sum += C[i], add(n+i, T, C[i]);
int x, y;
while(k--) {
read(x), read(y), g[x][y] = 1, ++sumL[x], ++sumC[y];
if(sumL[x] + L[x] > m || sumC[y] + C[y] > n) return printf("JIONG!"), 0;
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
if(!g[i][j]) add(i, n+j, 1);
printf("%d\n", sum-sap());
}