【题解】[AHOI2014] 支线剧情 有上下界的网络流 loj – 2226 —quhengyi11

传送门酱：「AHOI2014」支线剧情

题意：给你一张有向图，每次从 $1$号节点开始走，可以在任意节点停止。每走一次的费用是路径上所有边的边权和，求所有边都至少走过一次后的最小花费。

刚开始想这道题的时候坚定地认为这是 NP-Hard, 大概是看算导看蠢了 QAQ

其实如果知道一个东西叫做有上下界的网络流，这题就是一个裸题啦~

有上下界的网络流，顾名思义就是每条弧的流量都有一个上界和一个下界，流过这条弧的流量必须在这个范围之内，否则当前方案为一个不可行流。

那这个题目相当于就是限制了每条弧的流量在 $[1,\infty]$之内，求最小费用流，那我们如何求解呢？

首先我们考虑无源无汇的有上下界的网络流：

容易知道，每条弧的流量下界是必须要流过去的，因此我们可以把它们单独给提出来。

我们称红色的弧为必要弧，即必须要流过的弧，而现在的图就是一个只有上界限制的普通的网络流。因此我们可以在这张图上跑出一个可行流。

注意，别忘了我们还有一个条件，就是每条必要弧必须要流满！

为了让所有必要弧流满，我们可以这样进行构造：
(好吧我承认是有点乱)

Q: 你这样乱构造怎么跟原图等价呢 QAQ？

其实你只需要脑部一条从 $y$到 $x$流量为无穷大的弧，你就会发现其实是和原图一样的。

然后你从 $x$向 $y$跑一个最大流，如果最大流的结果是等于所有必要弧流量之和则说明这张图一定有可行流（即必要弧可以填满）
[$tip:$仔细思考这里为啥是对的]

然后我们就皆大欢喜求出了无源无汇的可行流。

等等，这貌似离我们的目标” 求有源有汇有上下界的最小费用流” 还差好远哎。

其实不远啦，仔细想想，如果有源有汇如何求可行流呀？

其实只要由汇点 $t$向源点 $s$连一条下界为 $0$上界为 $\infty$的边就又是一个无源无汇的图啦，接着上面的方法做就行啦~

那求最小费用流呢？

先用上面的方法判断是否有可行流（当然这题可以保证一定有可行流），当所有必要弧都被填满后，将必要弧的贡献加到答案里面，把必要弧费用全部设为 $0$（即再跑必要弧就没有贡献了），然后跑一遍图中 $x$到 $y$的最小费用流即可。

对于这道题的具体建图过程，显然 $1$是原图的源点，所有除 $1$以外的点都是汇点，因此我们可以建一个超级汇，$2~n$号点都向超级汇点连一条容量无穷大，费用为 $0$的弧，超级汇点向 $1$连一条容量无穷大，费用为 $0$的弧。

然后我们开始建点 $x$和 $y$，如果一个点的出度大于入度，就由它连向 $y$，如果一个点的入度大于出度，就由 $x$连向它，其中流量为入度与出度之差的绝对值。（想想为什么这样做，其实是和上面所说的建图方式是等价的）

然后跑一遍费用流就行啦~

代码：

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define N 10005
#define inf 1023333333
int n, head[N], k, in[N], out[N], x, t, tot, y, ans, que[N + 5], hh, tt, dis[N], pre[N], cap[N];
bool vis[N];
struct edge{
    int to, nxt, w, cap;
}e[N << 3];
inline void addedge (int u, int v, int w, int cap)
{
    e[tot] = (edge) {v, head[u], w, cap};
    head[u] = tot;
    ++tot;  
    e[tot] = (edge) {u, head[v], -w, 0};
    head[v] = tot;
    ++tot;
}
inline bool spfa (int s, int t)
{
    que[1] = s; vis[s] = 1;
    hh = tt = 1;
    fo (i, 1, n + 3)
    {
        dis[i] = inf;
        cap[i] = inf;
    }
    dis[s] = 0;
    while (hh != tt + 1)
    {   
        int u = que[hh];
        for (int i = head[u]; i != -1; i = e[i].nxt)
        {
            int v = e[i].to;
            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)
    {
//      printf("%d <- ", i);
        e[pre[i]].cap -= cap[t];
        e[pre[i] ^ 1].cap += cap[t];
        i = e[pre[i] ^ 1].to;
    }
//  printf("%d\n", i);
    ans += dis[t] * cap[t];
}
inline void costflow (int s, int t)
{
    while (spfa(s, t))
        updata(s, t);
}
int main ()
{
//  freopen("miao.txt", "r", stdin);
    scanf("%d", &n);
    memset(head, -1, sizeof(head));
    fo (i, 1, n)
    {
        scanf("%d", &k);
        fo (j, 1, k)
        {
            scanf("%d %d", &x, &t);
            addedge(i, x, t, inf);
            ++in[x];
            ans += t;//可爱的必要弧当然是先加进答案里面啦
        }
        out[i] = k;
        if (1 < i)
            addedge(i, n + 1, 0, inf);
    }
    addedge(n + 1, 1, 0, inf);
    y = n + 2, x = n + 3;
    fo (i, 1, n)//如果一个点有出度，就由它连向 y，如果一个点有入度，就由 x 连向它 
    {
        if (out[i] < in[i]) addedge(x, i, 0, in[i] - out[i]); else
        if (out[i] > in[i]) addedge(i, y, 0, out[i] - in[i]);
    }
    costflow(x, y);
    printf("%d", ans);
    return 0;
}