题解：P14122 [SCCPC 2021] Direction Setting

jzl_1210 · 2026-04-24 19:08:23 · 题解

一个简简单单的费用流。
纪念自己切的第不知道多少道蓝题。

题解

这道题目应该很好想吧，我一开始还乱搞导致白白浪费了很多小时。

不难发现，结果要我们统计的是节点的度数，与那个节点指向它没有关系，所以对问题进行转化，即对点 u 或点 v 产生度数的贡献，所以这道题目方法就出来了。分两种点：表示点的和表示边的。
边点向点 u 和点 v 各连一条容量为 1，费用为 0 的边。因为源点 s 向这个边点提供的流量只有 1，所以只能对一个点产生度数贡献，即流到哪个点就对那个点产生贡献。
现在只剩一个问题了，度数减去限制 a_i 该怎么处理，不难想到分流，即再向汇点连一条容量 a_i，费用为 0 的边就行了。

代码

真的很好写。

#include <bits/stdc++.h>
#define ll long long
#define pub push_back
using namespace std;
const int N = 905, inf = 1e9;
int T, n, m, cur[N], dis[N], s, t, ans2, jl[305];
bool vis[N];
struct Node{int to, w, c, fx;};
vector <Node> ed[N];
void add(int u, int v, int w, int c){
    int tmp = ed[v].size(), tmp2 = ed[u].size();
    ed[u].pub({v, w, c, tmp}), ed[v].pub({u, 0, -c, tmp2});
}
queue <int> q;
bool spfa(){
    for(int i = 1;i <= t;i++) dis[i] = inf;
    dis[s] = 0, q.push(s), vis[s] = 1;
    while(!q.empty()){
        int tmp = q.front();
        q.pop(), vis[tmp] = 0;
        for(auto bl : ed[tmp]){
            int i = bl.to, bw = bl.w, fy = bl.c;
            if(bw && dis[tmp] + fy < dis[i]){
                dis[i] = dis[tmp] + fy;
                if(!vis[i]) q.push(i), vis[i] = 1;
            }
        }
    }
    return dis[t] != inf;
}
int dfs(int x, int dl){
    if(x == t || !dl) return dl;
    int sum = 0, js = 0;
    vis[x] = 1;
    for(auto &bl : ed[x]){
        if(++js < cur[x]) continue;
        cur[x] = js;
        int i = bl.to, bw = bl.w, fy = bl.c;
        if(bw && dis[i] == dis[x] + fy && !vis[i]){
            int hl = dfs(i, min(dl, bw));
            bl.w -= hl, ed[i][bl.fx].w += hl;
            sum += hl, dl -= hl, ans2 += hl * fy;
            if(dl == 0) break;
        }
    }
    if(sum == 0) dis[x] = inf;
    vis[x] = 0;
    return sum;
}
void qzdl(){
    int tmp;
    while(spfa()){
        memset(cur, 0, sizeof cur);
        dfs(s, inf);
    }
} 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> T;
    while(T--){
        cin >> n >> m, s = n + m + 1, t = n + m + 2;
        for(int i = 1;i <= n;i++){
            int x;
            cin >> x, add(i + m, t, x, 0);
            add(i + m, t, inf, 1);
        }
        for(int i = 1;i <= m;i++){
            int u, v;
            cin >> u >> v, jl[i] = v;
            add(s, i, 1, 0), add(i, u + m, 1, 0);
            if(u != v) add(i, v + m, 1, 0);
        }
        ans2 = 0, qzdl(), cout << ans2 << "\n";
        for(int i = 1;i <= m;i++)
            for(auto bl : ed[i]){
                int j = bl.to, bw = bl.w;
                if(j > m && j <= m + n && bw == 0){
                    if(j - m == jl[i]) cout << "0";
                    else cout << "1";
                    break;
                }
            }
        cout << "\n";
        for(int i = 1;i <= t;i++) ed[i].clear();
    }
    return 0;
}