【算法】流量平衡等式建图 ——quhengyi11

寒假来我们学校讲课的人讲到的黑科技= =

首先先说一个定理

在一张网络流图中，一个可行流，除了原点 $s$和汇点 $t$，所有点的入流和出流是一样的 (显然)

流量平衡等式就是基于这个的呢

首先我们先看一道例题：志愿者招募

为了简化模型，我们将上面这题描述成下面这样：

总共有 $n$天，对于第 $i$天，我们有 $k$种人工作，第 $j$种人来了 $b_j$个，这一天至少需要 $a_i$个人。

我们有

$$\sum_{j=1}^k b_j \geq a_i$$

列出 $n$个这样的式子之后，我们需要最小化

$$\sum_{i=1}^m b_ic_i$$

你会发现你把它化归成了线性规划问题。但是你会发现一种人可能会涵盖 $n$天，这样线性规划成本就很大，我们继续说我们的方法。

按照套路，我们设 $d_i\geq 0$，然后将不等式化成等式

$$\sum_{j=1}^k b_j – a_i – d_i=0$$

你大概可以脑补到我说的流量平衡等式是啥了，将每个等式看成一个点，将里面的正数设为流入边，将负数设为流出边，然后通过控制流的费用来算对 $b_ic_i$的贡献。

然而你这里一个 $b_i$会在很多个等式里被算呀，你怎么设边的费用呢？

于是我们选择差分，将两边补两个 $0=0$的，等式每个等式和上面一个等式做差，我们就会得到 $n+1$条等式，然后你会发现每一个数都会被加一次和减一次 (因为 $b_i$是连续的所以这是显然成立的，如果 $b_i$不连续这个方法就 $gg$了)，然后就按上面说的方法建边就好了。

我们来结合一个具体的栗子：

第一种人 $b_1$个，单个人工资 $c_1=3$，能在 $1$到 $3$天工作

第二种人 $b_2$个，单个人工资 $c_2=2$，能在 $2$到 $3$天工作

第三种人 $b_3$个，单个人工资 $c_3=2$，能在 $1$到 $2$天工作

$a_1=5,a_2=4,a_3=3$

我们可以列出以下式子

$$0=0$$

$$b_1+b_3-d_1-a_1=0$$

$$b_1+b_2+b_3-d_2-a_2=0$$

$$b_1+b_2-d_3-a_3=0$$

$$0=0$$

差分

$$b_1+b_3-d_1-a_1=0$$

$$b_2+d_1-d_2+a_1-a_2=0$$

$$-b_3+d_2-d_3+a_2-a_3=0$$

$$-b_1-b_2+d_3+a_3=0$$

我们设流入边为负，流出边为正

因为 $b$是有费用的，看 $b_1$对等式的贡献我们就可以流一条 $1->4$的边，费用为 $c_1$，流量为 $\infty$。其它 $b$类似

对于 $a$，我们记每个式子里 $a$的部分为 $\Delta a_i$，如果 $\Delta a_i<0$就相当于是从源点向这个式子所代表的点连接一条费用为 $0$流量为 $-\Delta a_i$的边，否则就是从这个式子的点流向汇点连一条费用为 $0$流量为 $\Delta a_i$的边。

对于 $d$，它没有费用，我们用相似的建法，我们看 $d_2$就是从第三条式子所代表的点连向第二条式子所代表的点，流量为 $\infty$，费用为 $0$

然后建图跑就行了。

(我草稿本上有一个很可爱的图可惜学校没有手机拍不下来)(鸽子说: 回家再拍)

代码懒得给了

下面我们看一道更好玩的题:River Problem

这题看起来好麻烦呀要差分的话还要搞前缀和，因为在树上没准还要搞个 $lca$？

$qhy$作为老年退役猫咪刚开始是这样想的呢

但是她很容易的就发现，你这样做 $b_i$不止一次会出现在某个点所代表式子里呀，然后就咕咕咕了。

其实这题我感觉并不能列出具体的式子，你可以想象一下，对于每一条被污染的边 $(u,v)$，我们连一条 $(s,v)$和 $(u,t)$流量为污染值费用为 $0$，一个清洁剂 $(u,v,l,c)$就相当于连一条 $(v,u)$流量为 $l$费用为 $c$的边，相当于你在那条 $path$上做了差分，并且这样拆成单条 $path$的搞法也没错的呢（意会一下就相当于将一个点拆了好几个点，然后分别放在不同的 $path$上，一个点有几个式子，把这些式子合起来也满足性质）

代码

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define edge(i, u) for (int i = head[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)
#define N 10005
#define inf 1023333333
int n, m, head[N], tot = 1, ans, que[N + 5], hh, tt, dis[N], pre[N], cap[N], a[N];
bool vis[N];
int sum;
struct edge{
    int to, nxt, w, cap;
}e[N << 3];
inline void addedge (int u, int v, int w, int cap)
{
//    printf("u = %d  v = %d   w = %d   cap = %d \n", u, v, w, cap);
    e[++tot] = (edge) {v, head[u], w, cap};
    head[u] = tot;
    e[++tot] = (edge) {u, head[v], -w, 0};
    head[v] = tot;
}
inline bool spfa (int s, int t)
{
    que[1] = s; vis[s] = 1;
    hh = tt = 1;
    fo (i, 0, n + 3)
    {
        dis[i] = inf;
        cap[i] = inf;
    }
    dis[s] = 0;
    while (hh != tt + 1)
    {   
        int u = que[hh];
        edge (i, u)
            if (e[i].cap && dis[u] + e[i].w < dis[v])
            {
                pre[v] = i;
                dis[v] = dis[u] + e[i].w;
                cap[v] = std::min(cap[u], e[i].cap);
                if (!vis[v])
                {
                    vis[v] = 1;
                    tt++;
                    if (tt == N) tt -= N;
                    que[tt] = v;
                }
            }
        vis[u] = 0;
        hh++;
        if (hh == N) hh -= N;
    }
    return dis[t] != inf;
}
inline void updata (int s, int t)
{
    int i = t;
    while (i != s)
    {
        e[pre[i]].cap -= cap[t];
        e[pre[i] ^ 1].cap += cap[t];
        i = e[pre[i] ^ 1].to;
    }
    ans += dis[t] * cap[t];
    sum += cap[t];
}
inline void costflow (int s, int t)
{
    while (spfa(s, t))
        updata(s, t);
}
int main ()
{
    int T;
    scanf("%d", &T);
    fo (qwq, 1, T)
    {
        memset(e, 0, sizeof e); tot = 1;
        memset(head, 0, sizeof head);
        ans = sum = 0;
        int psum = 0;
        printf("Case #%d: ", qwq);
        scanf("%d", &n);
        int s = 0, t = n + 1;
        fo (i, 2, n)
        {
            int u, v, p;
            scanf("%d %d %d", &u, &v, &p);
            addedge(u, v, 0, inf);
            addedge(u, t, 0, p);
            addedge(s, v, 0, p);
            psum += p;
        }
        scanf("%d", &m);
        fo (i, 1, m)
        {
            int u, v, cap, c;
            scanf("%d %d %d %d", &u, &v, &cap, &c);
            addedge(v, u, c, cap);
        }
        costflow(s, t);
        if (sum != psum)
            printf("-1\n");
        else
            printf("%d\n", ans);
    }
    return 0;
}