最大流

参考资料

浅谈图论模型的建立与应用 - 黄源河

例1机器人放置

神题
看ppt吧……
一个x,y匹配确定一个机器人的位置

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define file(x) "placetherobots."#x
const int N = 55, V = N*N, E = V*N << 1, INF = 0x3f3f3f3f;
struct EDGE{int u, v, c, f;}st[E];
int n, m, s, t, hed[V], nxt[E], sz = 1, lv[V];
char mm[N][N];
struct P{int i, s, t;
    inline bool in(int x) {return s <= x && x <= t;}
};
std::vector<P> x, y;
inline void _add(int u, int v, int c) {
    st[++sz] = (EDGE){u, v, c, 0};
    nxt[sz] = hed[u], hed[u] = sz;
}
inline void add(int u, int v, int c) {_add(u, v, c), _add(v, u, 0);}
std::queue<int> q;
inline bool bfs() {
    memset(lv, 0, sizeof(lv));
    lv[s] = 1, q.push(s);
    while (!q.empty()) {
        int u = q.front();q.pop();
        for (int e = hed[u], v; v = st[e].v; e = nxt[e]) if (st[e].c > st[e].f && !lv[v]) {
            lv[v] = lv[u] + 1;
            q.push(v);
        }
    }
    return lv[t];
}
int dfs(int u, int a) {
    if (u == t) return a;
    int flow = 0, f;
    for (int e= hed[u], v; v= st[e].v; e = nxt[e])
        if (lv[v] == lv[u] + 1 && st[e].c > st[e].f && (f = dfs(v, std::min(a, st[e].c - st[e].f)))) {
            flow += f, a -= f;
            st[e].f += f, st[e^1].f -= f;
            if (!a) break;
        }
    return flow;
}
int main() {
    freopen(file(in), "r", stdin);
    freopen(file(out), "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%s", mm[i] + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) if (mm[i][j] == '*' || mm[i][j] == 'o') {
            bool f = mm[i][j] == 'o';
            int s = j;
            while (j + 1 <= m && (mm[i][j + 1] == '*' || mm[i][j + 1] == 'o')) {
                if (mm[i][++j] == 'o') f = 1;
            }
            if (f) x.push_back((P){i, s, j});
        }
    }
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) if (mm[i][j] == '*' || mm[i][j] == 'o') {
            bool f = mm[i][j] == 'o';
            int s = i;
            while (i + 1 <= n && (mm[i + 1][j] == '*' || mm[i + 1][j] == 'o')) {
                if (mm[++i][j] == 'o') f = 1;
            }
            if (f) y.push_back((P){j, s, i});
        }
    }
    for (int i = 0; i < x.size(); i++) for (int j = 0; j < y.size(); j++)
        if (x[i].in(y[j].i) && y[j].in(x[i].i))
            if (mm[x[i].i][y[j].i] == 'o') add(i + 1, x.size() + 1 + j, 1);
    s = x.size() + y.size() + 1;
    t = s + 1;
    for (int i = 0; i < x.size(); i++) add(s, i + 1, 1);
    for (int i = 0; i < y.size(); i++) add(i + x.size() + 1, t, 1);
    int flow = 0;
    while (bfs()) flow += dfs(s, INF);
    printf("%d\n", flow);
}

网络流24题

没什么说的。写写还是好的。

最小割

最大流 = 最小割

从二分图最大独立集讲起

做网络流24题的时候你应该已经遇到过了。
我们来快速回顾一下。

定义

二分图:顶点可以被分为两个集合,设为A,B。则A集合的点之间没有边,B集合亦然。
独立集:这样一个点集,它的点之间没有连边。

目标:我们想在二分图中取出一个最大的独立集(即点数最大,此时可以认为所有点权均为1)。

解决

建图
建立附加源s,附加汇t。
s->集合A中点,容量为1。
集合B中点->t,容量为1。
对于原图中的边,把它的方向定从A集合的点连到B集合的点,加到新图中,容量为$infty$。

答案
总点数-最大流。

分析

一个最小割对应一个最优选取方案。
证明:
对于原图中的边$(u,v),u\in A, v\in B$
在新图中构成$s\rightarrow u \rightarrow v \rightarrow v$这条路径。
最小割一定是切断这条路径的。问题在于切断哪条边。
$(u,v)$这条边的容量是 $\infty$, 一定不会在最小割中。
并且剩下的两条边不会同时割掉。割掉其中一条边时已经可以破坏这条路经,再割一条边一定不是最小割。
现在我们有 $(s,u),(v,t)$ 一定会且只会被割掉一条边。

然后来构造方案。
我们认为割掉一个点与源汇的边就是不选取这个点。
最小割最小化了我们不选取的点数。
也就是最大化了我们选取的点数。
证毕。

扩展

每个点带权。
将原来建图和源汇的边的容量改为该点点权。其他不变。

What happens now?

浅析一类最小割问题 - 彭天翼
这个论文不好找。需要的给我发邮件要。

一些想法

你现在应该已经有些心得了。
如何考虑建图的正确性呢?主要是建立割和方案的对应关系。
一般很好把合法方案对应到最小割。
但是我们还需要保证最小割不会对应非法方案。

  • 非法情况导致连通
  • 非法清空导致非最小割(多割了边,即去掉这条割边仍然满足不连通的条件)

Problem Set

我跟着黄学长博客刷的。感觉还行。
经典题双核cpu(cogs上有),文理分科,切糕。

上下界

搜了一些东西,感觉还是 Menci 讲的清楚。当然一如既往的不能学她的实现。
可以先看 Fancy 的博客中的无源汇可行流。她直接叙述建图方式,来的比较快。你能秒出来正确性就别浪费时间看长篇大论了。所谓“优化”其实比不优化还好写。所以建议直接写优化的版本。
接下来看 Menci这篇文章 的无源汇可行流后的部分,条理比较清楚。代码近似于伪代码帮助理解。不过前面可能有点罗嗦?

Prob Hint
2502 清理雪道 有源汇最小流的模板题,不过还是有必要写一写的
3698 XWW的难题 有源汇最大流。和 poj budget 建图思路一样。用源汇限制行列和。思路还是很妙的。和poj那个题大概写一个就好了。

费用流

AHOI2014 支线剧情 最小费用可行流

源是1,新建一个汇把所有点连过去,容量inf,费用为0。
在这个图上求一个最小费用可行流。
和不带权的可行流差不多:
对于(u,v,w,lower,upper),建 (u, T, w, lower), (S, v, 0, lower), (u, v, w, upper - lower)
然后(t, s, inf),和可行流一样。
跑S-T最小费用最大流就是一个可行流了。可行流费用就是答案。

//第一次写,代码很烂
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#define fore for (int e = hed[u], v; (v = st[e].v); e = nxt[e])
const int V = 400, E = V*50*4, INF = 0x3f3f3f3f;
int n, hed[V], nxt[E], sz = 1, s, t, ans, necc, p[V], a[V], dis[V];
struct EDGE{int u, v, c, w, f;}st[E];
inline void _add(int u, int v, int w, int c) {
    st[++sz] = (EDGE){u, v, c, w, 0};
    nxt[sz] = hed[u], hed[u] = sz;
}
inline void add(int u, int v, int w, int c) {_add(u, v, w, c), _add(v, u, -w, 0);}
std::queue<int> q;
bool inq[V];
inline bool spfa(int& flow, int& cost) {
    memset(dis, 0x3f, sizeof(dis));
    q.push(s);
    inq[s] = 1, dis[s] = 0, a[s] = INF;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = 0;
        fore if (st[e].c > st[e].f && dis[v] > dis[u] + st[e].w) {
            dis[v] = dis[u] + st[e].w;
            a[v] = std::min(a[u], st[e].c - st[e].f);
            p[v] = e;
            if (!inq[v]) q.push(v), inq[v] = 1;
        }
    }
    if (dis[t] == INF) return 0;
    for (int e = p[t]; e; e = p[st[e].u]) {
        flow += a[t], cost += a[t]*st[e].w;
        st[e].f += a[t], st[e^1].f -= a[t];
    }
    return 1;
}
int main() {
//    freopen("input", "r", stdin);
    scanf("%d", &n);
    int s = 1, t = n + 1, S = t + 1, T = S + 1;
    for (int i = 1; i <= n; i++) {
        int k; scanf("%d", &k);
        add(i, t, 0, 1e9);
        for (int j = 1; j <= k; j++) {
            int x, y;
            scanf("%d%d", &x, &y);
            add(i, x, y, 1e9);
            add(i, T, y, 1);
            add(S, x, 0, 1);
        }
    }
    add(t, s, 0, 1e9);
    int cost = 0, flow = 0;
    ::s = S, ::t = T;
    while (spfa(flow, cost)) ;
    printf("%d\n", cost);
}