题解：P11879 速成之道

· · 题解

思路：

一眼网络流，但是需要一些神奇的建边方式。

我们考虑建立超级源点和超级汇点，并把每个点拆分为 x1,x2，分别表示两种情况。

我们让超级源点像每个 x1 建一条容量为 A_x 的单向边，反边正常建为 0 就行。

随后，我们从 x1 向 x2 建一条容量为 B_x 的单向边，反边正常建为 0。

考虑对于每一条限制，让 x_2 向 y_1 建边，边权正无穷，以表明约束关系。反边照旧。

最后，我们考虑让 q_2 直接连向汇点，边权设为正无穷。

不难发现，我们这种建边方式满足了我们需要达成的限制，通过观察和模拟，也不难发现我们要求的答案就是最小割。

按最大流最小割定理，把最大流一求，输出即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int Maxn=1e12; 

struct node{
    int nex,to,val;
}e[1000005];
int tot=1;
int he[1000005];

inline void add(int x,int y,int w){
    e[++tot].nex=he[x];
    e[tot].to=y;
    e[tot].val=w;
    he[x]=tot;
}

int a[1000005];
int p[1000005];

int q;

int ans;

int dis[1000005];
int now[1000005];
int s,t;

inline int bfs(){
    for (int i=1;i<=2*n+2;i++){
        dis[i]=Maxn;
    }
    queue<int>q;
    q.push(s);
    dis[s]=0;
    now[s]=he[s];
    while(q.size()){
        int x=q.front();
        q.pop();
        for (int i=he[x];i;i=e[i].nex){
            int v=e[i].to;
            if (e[i].val>0 && dis[v]==Maxn){
                q.push(v);
                now[v]=he[v];
                dis[v]=dis[x]+1;
                if (v==t){
                    return 1;
                }
            }
        }
    } 
    return 0;
}

inline int dfs(int x,int sum){
    if (x==t){
        return sum;
    }
    int res=0;
    for (int i=now[x];i && sum;i=e[i].nex){
        now[x]=i;
        int v=e[i].to;
        if (e[i].val>0 && (dis[v]==dis[x]+1)){
            int k=dfs(v,min(sum,e[i].val));
            if (k==0){
                dis[v]=Maxn;
            }
            e[i].val-=k;
            e[i^1].val+=k; 
            res+=k;
            sum-=k;
        }
    }
    return res;
}

int x[1000005];
int y[1000005];

signed main(){
    cin>>n>>m;
    s=2*n+2;
    t=2*n+1;
    for (int i=1;i<=m;i++){
        cin>>x[i]>>y[i];
    }
    for (int i=1;i<=n;i++){
        cin>>a[i];
    } 
    for (int j=1;j<=n;j++){
        cin>>p[j];
    }

    for (int i=1;i<=n;i++){
        add(s,i,a[i]);
        add(i,s,0);
    }
    for (int i=1;i<=n;i++){
        add(i,i+n,p[i]);
        add(i+n,i,0);
    }

    for (int i=1;i<=m;i++){
        add(x[i]+n,y[i],Maxn);
        add(y[i],x[i]+n,0);
    }
    cin>>q;
    add(q+n,t,Maxn);
    add(t,q+n,0);
    while(bfs()){
        ans+=dfs(s,Maxn);
    } 

    cout<<ans;

    return 0;
}