JZOJ 3993 Magic

我的极少数网络流题解（？

首先考虑将问题转化为最大权闭合子图模型。
由于要求最小化费用，不妨考虑最大化可以从初始的 n∑i=1wi 中除去的费用。

对原图中的每个点，建一个点权为 −bi 的点，代表将这个点的 ai 变为 0。
将原图中每个点的所有出边按照出点的权升序，那么显然是除去一个后缀才有效果，将这些边一一建点，点权为出点的 ai 的差，并向下一条边对应的点连边。
当然，这些点还要向出点对应的点连边。
用初始的 ∑i=1wi 减去最大权闭合子图的点权和，即是答案。

关于最大权闭合子图，有十分经典的最小割模型转化，此处不再赘述。

代码：

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3;
const int M = 5e4;
int n,m,s,t,tot;
int a[N + 5],b[N + 5];
int ans;
vector<int> e[N + 5];
inline bool cmp(int x,int y)
{
    return a[x] < a[y];
}
namespace Dinic
{
    const int N = 1e5;
    const int M = 2e5;
    int n;
    int to[(M << 1) + 5],val[(M << 1) + 5],pre[(M << 1) + 5],first[N + 5],cur[N + 5],edge_tot;
    inline int init()
    {
        memset(first,-1,sizeof first);
        return 0;
    }
    int Init = init();
    inline void add_edge(int u,int v,int w)
    {
        int &tot = edge_tot;
        to[tot] = v,val[tot] = w,pre[tot] = first[u],first[u] = tot++;
    }
    inline void add(int u,int v,int w)
    {
        add_edge(u,v,w),add_edge(v,u,0);
    }
    int head,tail,q[N + 5],dep[N + 5],vis[N + 5];
    int bfs()
    {
        head = tail = 0;
        memset(vis,0,sizeof vis);
        memset(dep,0x3f,sizeof dep);
        dep[s] = 0,vis[s] = 1,q[++tail] = s;
        while(head < tail)
        {
            int p = q[++head];
            vis[p] = 0;
            for(register int i = first[p];~i;i = pre[i])
                if(val[i] && dep[to[i]] > dep[p] + 1)
                {
                    dep[to[i]] = dep[p] + 1;
                    if(!vis[to[i]])
                        vis[to[i]] = 1,q[++tail] = to[i];
                }
        }
        return dep[t] ^ 0x3f3f3f3f;
    }
    int maxflow;
    int dfs(int p,int flow)
    {
        if(p == t)
            return (maxflow += flow,flow);
        int ret = 0,used = 0;
        for(register int &i = cur[p];~i;i = pre[i])
            if(val[i] && dep[to[i]] == dep[p] + 1 && (ret = dfs(to[i],min(flow - used,val[i]))))
            {
                used += ret,val[i] -= ret,val[i ^ 1] += ret;
                if(used >= flow)
                    break;
            }
        return used;
    }
    int dinic()
    {
        while(bfs())
            memcpy(cur,first,sizeof cur),dfs(s,0x3f3f3f3f);
        return maxflow;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i);
    for(register int i = 1;i <= n;++i)
        scanf("%d",b + i);
    int u,v;
    for(register int i = 1;i <= m;++i)
        scanf("%d%d",&u,&v),e[u].push_back(v);
    Dinic::n = n + m + 2,s = n + m + 1,t = n + m + 2;
    for(register int i = 1;i <= n;++i)
    {
        sort(e[i].begin(),e[i].end(),cmp);
        for(register int j = 0;j < e[i].size();++j)
            Dinic::add(s,n + ++tot,a[e[i][j]] - (j ? a[e[i][j - 1]] : 0)),j + 1 < e[i].size() && (Dinic::add(n + tot,n + tot + 1,0x3f3f3f3f),1),Dinic::add(n + tot,e[i][j],0x3f3f3f3f);
        Dinic::add(i,t,b[i]);
    }
    ans = Dinic::dinic();
    printf("%d\n",ans);
}