题解 P4662 【[BalticOI 2008]黑手党】

· · 题解

\Large\texttt{My Blog}

题目链接：Luogu 4662

Byteland 国警方收到了一条匿名举报，其中说当地黑帮老大正计划一次从港口到郊区仓库的运输。警方知道运输的时间并且知道运输需要用到国家的高速公路网。

高速公路网包含 n 个收费站和 m 条双向的高速公路，每个路段直接连着两个不同的收费站。一个收费站可能与很多其他的收费站相连。汽车只能通过收费站进入或离开高速公路网。据所知，黑帮会距港口边最近的收费站进入高速公路，从距仓库最近的收费站离开（不会在出高速后重新进入）。特警组位于选定的收费站处。当运输车辆进入被监控的收费站时，它就会被警察抓住。

从这个角度看，最简单的办法就是在每个收费站处都安排特警班。然而，控制第 i 个收费站需要特定的费用 c_i，每个收费站费用不同。警方想要让花费最小，所以他们需要制定一个收费站的最小控制集，这个集合满足两个条件：

你需要找到收费站的最小控制集。

数据范围：1\le n\le 200，1\le m\le 2\times 10^4，1\le c_i\le 10^7

Solution

我们需要将一些收费站安排特警班，使得源点和汇点不连通，于是这个问题就是最小割问题。

我们考虑如何将割点转化成割边。由于每个点只能被割一次，我们首先需要拆点：将点 i 拆成 i_1 和 i_2 两个点，其中 i_1 和 i_2 之间连容量为代价（本题中代价为 1）的边。对于对于一条边 (u,v)，也就转化为 (u_2,v_1,\texttt{INF}) 和 (v_2,u_1,0)，其中容量为 \texttt{INF} 使得这条边不可能被割掉，即割掉的边一定为 (i_1,i_2) 这样的边。

由于源点和汇点也可以被割，所以源点转化为 s_1，汇点转化为 t_2。

最后我们证明一下正确性。此时，整张图的形态没有改变，每个点只能被割一次对应着每条边 (i_1,i_2) 只能被割一次，正确性得证。

对于控制集，我们从源点 s_1 出发沿着残量大于 0 的边开始 \texttt{DFS}，将所有访问的点打标记。对于一条正向边 (u,v)，如果 u 被打了标记而 v 没有被打标记，那么就意味着这条边所代表的点被割掉了。

时间复杂度：O(n^2m)

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

const int N=4e2+5,M=1e5+5;
const int INF=1<<30;
int n,m,tot=1,lnk[N],ter[M],nxt[M],val[M],dep[N],cnr[N];
bool vis[N];

void add(int u,int v,int w) {
    ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,val[tot]=w;
}
void addedge(int u,int v,int w) {
    add(u,v,w),add(v,u,0);
}
int bfs(int s,int t) {
    memset(dep,0,sizeof(dep));
    memcpy(cnr,lnk,sizeof(lnk));
    std::queue<int> q;
    q.push(s),dep[s]=1;
    while(!q.empty()) {
        int u=q.front(); q.pop();
        for(int i=lnk[u];i;i=nxt[i]) {
            int v=ter[i];
            if(val[i]&&!dep[v]) q.push(v),dep[v]=dep[u]+1;
        }
    }
    return dep[t];
}
int dfs(int u,int t,int flow) {
    if(u==t) return flow;
    int ans=0;
    for(int i=cnr[u];i&&ans<flow;i=nxt[i]) {
        cnr[u]=i;
        int v=ter[i];
        if(val[i]&&dep[v]==dep[u]+1) {
            int x=dfs(v,t,std::min(val[i],flow-ans));
            if(x) val[i]-=x,val[i^1]+=x,ans+=x;
        }
    }
    if(ans<flow) dep[u]=-1;
    return ans;
}
void dinic(int s,int t) {
    while(bfs(s,t)) while(dfs(s,t,INF));
}
void dfs(int u) {
    vis[u]=1;
    for(int i=lnk[u];i;i=nxt[i]) if(val[i]&&!vis[ter[i]]) dfs(ter[i]);
}
int main() {
    int s,t;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=n;++i) {
        int x;
        scanf("%d",&x);
        addedge(i,i+n,x);
    }
    while(m--) {
        int u,v;
        scanf("%d%d",&u,&v);
        addedge(u+n,v,INF),addedge(v+n,u,INF);
    }
    dinic(s,t+n);
    dfs(s);
    std::vector<int> ans;
    for(int i=2;i<=tot;i+=2) {
        int u=ter[i^1],v=ter[i];
        if(vis[u]&&!vis[v]) ans.push_back(u);
    }
    std::sort(ans.begin(),ans.end());
    for(int sz=(int)ans.size()-1,i=0;i<=sz;++i) {
        printf("%d%c",ans[i]," \n"[i==sz]);
    }
    return 0;
}