题解：P4662 [BalticOI 2008] 黑手党 (Day0)

· · 题解

思路：

很明显，这是一道最小割的题。

但是但是，难点在于建边。

我们将一个点 x 拆开为入点 x 和出点 x+n。即把一条边 (x,y) 拆为 (x+n,y) 和 (y+n,x)。而我们只能割某个点被拆后出现的边，所以某个点之间的边的流量要设置成 INF，使它无法被割。

然后剩下的就是最小割模板啦，跑 Dinic 就好啦。

割完之后，再跑一遍 DFS 判断哪些点被割了即可。

:::info[Code]

#include<bits/stdc++.h>
#define int long long
using namespace std ;
const int maxn=1e3+5;
const int maxm=1e5+5;
const int INF=0x3f3f3f3f;
struct node {
    int v;
    int id;
};
int n,m;
int ss,tt;
int ans=0;
int pre[maxn],pre1[maxn];
int dep[maxn];
int a[maxn];
vector<node>g[maxn];
int tot=0;
int w[maxm];
bool vis[maxn];
void add (int u,int v,int ww) {
    g[u].push_back({v,tot});
    g[v].push_back({u,tot^1});
    w[tot]=ww;
    tot+=2;
}
bool bfs (int x) {
    memset(dep,0,sizeof(dep));
    memset(pre,0,sizeof(pre));
    memset(pre1,0,sizeof(pre1));
    queue<int>q;
    q.push(x);
    dep[x]=1;
    while (!q.empty()) {
        int u=q.front();
        q.pop();
        for (auto i:g[u]) {
            int v=i.v;
            int id=i.id;
            if (dep[v]==0&&w[id]>0) {
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[tt];
}
int dfs (int u,int f) {
    if (u==tt) return f;
    int res=0;
    for (auto i:g[u]) {
        int v=i.v;
        int id=i.id;
        if (dep[v]<=dep[u]) continue;
        if (w[id]==0) continue;
        int f2=dfs(v,min(f-res,w[id]));
        res+=f2;
        w[id]-=f2;
        w[id^1]+=f2;
        if (res==f) break;
    }
    return res;
}
void dinic () {
    while (bfs(ss)) ans+=dfs(ss,INF);
}
void getg (int u) {
    vis[u]=1;
    for (auto i:g[u]) {
        int v=i.v;
        int id=i.id;
        if (!vis[v]&&w[id]>0) getg(v);
    }
}

signed main () {
    cin>>n>>m>>ss>>tt; tt+=n;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=m;i++) {
        int x,y;
        cin>>x>>y;
        add(x+n,y,INF);
        add(y+n,x,INF);
    }
    for (int i=1;i<=n;i++) {
        if (i!=tt) add(i,i+n,a[i]);
    }
    dinic();
    getg(ss);
    for (int i=1;i<=n;i++) if (vis[i]^vis[i+n]) cout<<i<<' ';
    return 0;
}

:::