「Luogu 1345」Telecowmunication

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

Description

题目链接：Luogu 1345

农夫约翰的奶牛们喜欢通过电邮保持联系，于是他们建立了一个奶牛电脑网络，以便互相交流。这个网络包括 $n$ 台电脑和 $m$ 个电脑之间的连接。这些电脑用如下的方式发送电邮：如果存在一个由 $c$ 台电脑组成的序列 $a_1,a_2,\dots,a_c$，且 $a_1$ 与 $a_2$ 相连，$a_2$ 与 $a_3$ 相连……那么电脑 $a_1$ 和 $a_c$ 就可以互发电邮。

很不幸，有时候某些倒霉的电脑会坏掉。说这意味着这台电脑不能再发送电邮了，于是与这台电脑相关的连接也就不可用了。

有两头奶牛就想：如果我们两个不能互发电邮，至少需要坏掉多少台电脑呢？你需要计算出这个最小值。

数据范围：$1\le n\le 100$，$1\le m\le 600$

Solution

这道题和「BalticOI 2008」Mafia 的本质是一样的，都是割掉一部分点，使得源点和汇点不连通，只是源点和汇点是不能割掉的。于是根据 Mafia 的思路，我们有一个小变化：源点为 $s_2$，汇点为 $t_1$。之后直接跑最小割就行了。

时间复杂度：$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
 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int N=205,M=5e3+5;
int n,m,tot=1,lnk[N],ter[M],nxt[M],val[M],dep[N],cnr[N];

int id(int x,int y) {
    return (x-1)*m+y;
}
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;
}
int dinic(int s,int t) {
    int ans=0;
    while(bfs(s,t)) {
        int x;
        while((x=dfs(s,t,1<<30))) ans+=x;
    }
    return ans;
}
int main() {
    int s,t;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=n;++i) addedge(i,i+n,1);
    while(m--) {
        int u,v;
        scanf("%d%d",&u,&v);
        addedge(u+n,v,1<<30);
        addedge(v+n,u,1<<30);
    }
    printf("%d\n",dinic(s+n,t));
    return 0;
}
0%