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

jianami · 2025-12-23 11:23:07 · 题解

记 (u,v,c) 表示网络流中从 u 向 v 流量为 c 的边。

我们考虑最小割，把火力发电场供电的设施连到 S 上，太阳能发电场供电的设施连到 T 上。具体而言：

• 对于原图中的每一条边 (u,v)，建 (u,v,+\infty),(v + n,u+n,+\infty)，意思是建正反两个图。

• 对于每个 d_u = -1 的点，建 (u,u + n,a_u)，意思是删掉 u 这个点需要 a_u 代价。

• 对于每个 d_u = 0 的点，建 (S,u,V + a_u),(u + n,T,V),(u,u + n,+\infty)，V 为大常数，意思是 u 为火力发电场不需要代价，变为太阳能发电场需要 a_u 代价。V 的意义是防止 (S,u),(u + n,T) 全被割掉，如果这样一定不优。当然 (S,u),(u + n,T) 必须恰好割一条，否则 S,T 将连通。

这样建图我们可以发现，某个点 u 同时被两个发电场供电，等价于存在一条 S \rightarrow u \rightarrow T 的路径。跑最小割，最后答案要减去发电厂的数量 \times V。

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;

const int N = 1e6 + 10,V = 1e8,INF = 1e18;

int dep[N],c[N],now[N],head[N],to[N],nxt[N],n,m,s,t,ec = 1,q[N];
int d[N],a[N];

void add(int u,int v,int w){
    to[++ec] = v,c[ec] = w,nxt[ec] = head[u],head[u] = ec;
}

bool getdep(){
    memset(dep,-1,sizeof(dep));
    int l = 1,r = 0;
    dep[s] = 0,q[++r] = s,now[s] = head[s];
    while(l <= r){
        int u = q[l++];
        for(int e = head[u];e;e = nxt[e]){
            int v = to[e],w = c[e];
            if(dep[v] == -1 && w){
                dep[v] = dep[u] + 1,now[v] = head[v];q[++r] = v;    
            }
        }
    }
    return (dep[t] != -1);
}

int getflow(int u,int f){
    if(u == t) return f;
    int ret = 0;
    for(int e = now[u];e;e = nxt[e]){
        now[u] = e;int v = to[e],w = c[e];
        if(dep[v] == dep[u] + 1 && w){
            int val = getflow(v,min(f - ret,w));
            c[e] -= val,c[e ^ 1] += val,ret += val;
            if(f == ret) return ret;
        }
    }return ret;
}

signed main(){
    ios::sync_with_stdio(0); 
    cin.tie(0);
    cin >> n >> m;
    s = 2 * n + 1,t = 2 * n + 2;
    for(int i = 1;i <= n;i ++){
        cin >> d[i];
    } 
    for(int i = 1;i <= n;i ++) cin >> a[i];
    int sum = 0;
    for(int i = 1;i <= n;i ++){
        //cin >> d[i];
        if(d[i] == 0){
            add(s,i,V + a[i]);add(i,s,0);
            add(i + n,t,V);add(t,i + n,0);
            add(i,i + n,INF);add(i + n,i,0);
            sum ++;
        }else if(d[i] == 1){
            add(s,i,V);add(i,s,0);
            add(i + n,t,V + a[i]);add(t,i + n,0);
            add(i,i + n,INF);add(i + n,i,0);
            sum ++;
        }else{
            add(i,i + n,a[i]);add(i + n,i,0);
        }
    } 

    for(int i = 1;i <= m;i ++){
        int u,v;cin >> u >> v;
        add(u,v,INF);add(v,u,0);
        add(v + n,u + n,INF);add(u + n,v + n,0);
    }

    int ans = 0;
    while(getdep()) ans += getflow(s,1e18);
    cout << ans - sum * V;

    return 0;
}