题解：P14832 [THUPC 2026 初赛] Unpair Ampere

· · 题解

网络流好题。

需要代价最小使得条件不成立，想到最小割。

以下设 0 类点为 u，1 类点为 v，-1 类点为 w。

考虑怎么表示限制。对于一条链 u\to w_1\to w_2\to v，发现砍掉 w_1 和砍掉 w_2 是独立的，而砍掉 u 或砍掉 v 会影响后面所有的 w。所以我们对于每一条 DAG 上的边 (x,y)，连接 (x,y,+\infty),(y',x',+\infty)；对于每个点 w，连接 (w,w',a_w)；对于每个点 u，连接 (S,u,a_u),(u,u',+\infty)；对于每个点 v，连接 (v,v',+\infty),(v',T,a_v)。

又发现如果一个 u 和一个 v 被同时砍掉，仍不合法，于是我们增加边权使得这种情况一定不优，对于每条连接 S,T 的边强制要求多流过 D。对于点 u，连接 (S,u,a_u+D),(u,u',+\infty),(u',T,D)；对于点 v，连接 (S,v,D),(v,v',+\infty),(v',T,a_v+D)。

最后在答案减去 D 乘上 u,v 的数量就做完了。

边数是 O(n+m) 的，在 10^5 量级左右，Dinic 可以轻松跑过。

:::success[Code]

#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define dFor(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
#define inf (1<<30)
#define D (1<<20)
class Dinic{
    private:
        struct Edge{
            int to,rev;
            int cap;
        };
        int n;
        vector<vector<Edge>> g;
        vector<int> dis,it;
        bool bfs(int s,int t){
            fill(dis.begin(),dis.end(),0);
            queue<int> q;
            dis[s]=1;
            q.push(s);
            while(!q.empty()){
                int u=q.front();
                q.pop();
                for(auto &e:g[u]){
                    if(!dis[e.to]&&e.cap>0){
                        dis[e.to]=dis[u]+1;
                        q.push(e.to);
                    }
                }
            }
            return dis[t]!=0;
        }
        int dfs(int u,int t,int f){
            if(u==t) return f;
            for(int &i=it[u];i<(int)g[u].size();i++){
                Edge &e=g[u][i];
                if(e.cap<=0) continue;
                if(dis[e.to]!=dis[u]+1) continue;
                int push=dfs(e.to,t,min(f,e.cap));
                if(push>0){
                    e.cap-=push;
                    g[e.to][e.rev].cap+=push;
                    return push;
                }
            }
            return 0;
        }
    public:
        Dinic(int n=0):n(n){
            g.assign(n+1,{});
            dis.assign(n+1,{});
            it.assign(n+1,{});
        }
        void add(int u,int v,int w){
            int szu=g[u].size(),szv=g[v].size();
            g[u].push_back({v,szv,w});
            g[v].push_back({u,szu,0});
        }
        int maxflow(int s,int t){
            int flow=0;
            while(bfs(s,t)){
                fill(it.begin(),it.end(),0);
                while(1){
                    int push=dfs(s,t,inf);
                    if(!push) break;
                    flow+=push;
                }
            }
            return flow;
        }
};
#define MAXN 5005
int n,m;
int d[MAXN],a[MAXN];
vector<int> e[MAXN];
int in[MAXN];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    Dinic dinic(n*2+2);
    int S=n*2+1,T=n*2+2;
    For(i,1,n){
        cin>>d[i];
    }
    int cnt=0;
    For(i,1,n){
        cin>>a[i];
        if(d[i]==-1){
            dinic.add(i,i+n,a[i]);
        }else if(d[i]==0){
            dinic.add(S,i,a[i]+D);
            dinic.add(i+n,T,D);
            dinic.add(i,i+n,inf);
            cnt++;
        }else{
            dinic.add(i+n,T,a[i]+D);
            dinic.add(S,i,D);
            dinic.add(i,i+n,inf);
            cnt++;
        }
    }
    For(i,1,m){
        int u,v;
        cin>>u>>v;
        dinic.add(u,v,inf);
        dinic.add(v+n,u+n,inf);
    }
    cout<<dinic.maxflow(S,T)-D*cnt<<endl;
    return 0;
}

:::