洛谷 1345 [USACO5.4]奶牛的电信Telecowmunication 题解

发表于 | 更新于 | 阅读次数：
本文字数： 985 字 | 阅读时长 ≈ 5 分钟

题意简述

给你一个无向图，还有源点（S）和汇点（T）。求最少删除多少个点使得源点和汇点不连通。

点数n<=100，边数m<=600

思路框架

把每个点$u$拆成出点和入点，设为$Out(u)$和$In(u)$。

对于每个$u$，建流$In(u)\to_1 Out(u)$。

对于每个无向边，我们把它拆成两个有向边。

对于一条有向边$u\to v$，建流$Out(u)\to_{\infty}In(u)$

从$Out(S)$到$In(T)$跑最小割（最大流），就是答案了。

具体思路

这里讲讲我们是如何想到上面的拆点建图的。

原本我们的图是这样的：

blog1.jpg

这是一个点，它有入边和出边。

变成这样：
blog2.jpg
（蓝边流量为1，黑边流量为正无穷）

那么我们按照这样去建图，把一个点转化成一条边，删掉边就相当于删掉点。这样，我们就珂以把求最小割点的问题，转化成求最小割边的问题了。

然后由于原图上，我们只能删除点，不能删除边。我们只要把原图上的边权都变成无穷大，就不会割掉原边了（显然不是最优解啊）。

然后，由最小割=最大流，跑一遍Dinic就完了。

代码

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

#include <bits/stdc++.h>using namespace std;
namespace Flandre_Scarlet
{
    #define N 155555
    #define INF 0x3f3f3f3f
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt) 
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }
    class Graph //这一段是裸的Dinic，会的直接跳到112行。
    /*
    简述函数功能
    BFS/DFS：内部实现函数，会Dinic应该知道
    AddFlow(u,v,w)：u到v建流，流量为w
    Dinic()：主求解函数，求从Source到Sink的最大流
    Source和Sink珂以在外面修改
    */
    {
        public:
            int EdgeCount;
            int head[N];
            struct Edge
            {
                int To,Label;
                int Next;
            }Ed[200100];
            void clear()
            {
                MEM(head,-1);
                MEM(Ed,-1);
                EdgeCount=-1;
            }
            void AddEdge(int u,int v,int w)
            {
                ++EdgeCount;
                Ed[EdgeCount]=(Edge){v,w,head[u]};
                head[u]=EdgeCount;
            }
            void AddFlow(int u,int v,int w) {AddEdge(u,v,w);AddEdge(v,u,0);}

            int Source,Sink;
            int deep[N];
            queue<int>Q,EmptyQ;
            bool BFS()
            {
                Q=EmptyQ;FK(deep);
    
                Q.push(Source);
                deep[Source]=1;
                do
                {
                    int u=Q.front();Q.pop();
                    for(int i=head[u];~i;i=Ed[i].Next)
                    {
                        int v=Ed[i].To;
                        if (deep[v]==0 and Ed[i].Label>0)
                        {
                            deep[v]=deep[u]+1;
                            Q.push(v);
                        }
                    }
                }while(!Q.empty());
    
                return deep[Sink];
            }
            int DFS(int u,int MinFlow)
            {
                if (u==Sink) return MinFlow;
                for(int i=head[u];~i;i=Ed[i].Next)
                {int v=Ed[i].To;
                    if (deep[v]==deep[u]+1 and Ed[i].Label!=0)
                    {
                        int d=DFS(v,min(MinFlow,Ed[i].Label));
                        if (d>0)
                        {
                            Ed[i].Label-=d;
                            Ed[i^1].Label+=d;
                            return d;
                        }
                    }
                }
                return 0;
            }
            int Dinic()
            {
                int ans=0;
                while(BFS())
                {
                    int d;
                    while(d=DFS(Source,INF)) ans+=d;
                }
                return ans;
            }
    }Nt;

    int n,m,s,t;
    #define In(x)  (x+n)
    #define Out(x) (x)
    //拆点
    void Input()
    {
        Rd(4,&n,&m,&s,&t);
        Nt.clear();
        F(i,1,n) Nt.AddFlow(In(i),Out(i),1);
        F(i,1,m)
        {
            int u,v;Rd(2,&u,&v);
            Nt.AddFlow(Out(u),In(v),INF);
            Nt.AddFlow(Out(v),In(u),INF);
        }
        //上面说的建图
    }

    void Soviet()
    {
        Nt.Source=Out(s),Nt.Sink=In(t); //注意是从Out(s)到In(t)，要不然答案不对
        printf("%d\n",Nt.Dinic());
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main(){
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w