「BalticOI 2008」Mafia

发表于 | | 阅读次数:
字数统计: 1.2k 字

Description

题目链接：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,\text{INF})$ 和 $(v_2,u_1,0)$，其中容量为 $\text{INF}$ 使得这条边不可能被割掉，即割掉的边一定为 $(i_1,i_2)$ 这样的边。

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

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

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

时间复杂度：$O(n^2m)$（$\text{Dinic}$）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
#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;
}
0%