HDU 4289 Control(最小割)

Introduction

道家学派的创始人老子认为一切事物都包含有和无、难和易、长和短、高和下、前和后等对立面，对立的双方能够相互转化

Description

某位妹妹要从S到T运输偷来的心，我们可以在某些途径城市安装监控以逮捕她。每个城市安装监控的费用不同，要保证逮捕到这位妹妹，~~你被逮捕了，罪名:XXXX(某音刷多了)~~ ，安装监控的最少花费是多少？

Analyze

看上去像是要求一个连通图的割点，使得S到T不连通，可并没有体现“最”这一特点，完全是固定的一种方案。(而且S、T不属于割点，而此题可以监控S、T)

而我们知道，在一个已知S、T的网络图中，求完最大流的残余网络S到T不连通，符合题意。可题目求“最小”，奈何等于求“最大”？

老子认为：一切事物都有对立面，对立的双方可以互相转化。

我们知道，一条S到T的可行流的最大值，是这条路上容量最小边的容量

所以，最大即最小，最小即最大。

将原题中费用转为容量。求出最大流，便封锁了S到T的所有路。而这最大流，是各可行流中最小容量的和，即最小费用。

以上理解也可以作为(最大流 == 最小割)的理解,所以这题其实是在求最小割?(滑稽)

感性认识：

假设最开始可行流就一条，那么最大流便是这条可行流上容量最小的边的容量，套到题目上，便是花费最少的监控所花费的金钱(即最小花费)

两条可行流、n条可行流也是这种情况

Update

这道题就是求最小割！使S到T不连通！瞎分析一顿，看别人说最大流就使劲往上套，试图说服自己……只不过最小割与最大流相等而已……仿佛给自己解释了一遍为什么最大流等于最小割

something

算法竞赛要求参赛者熟练掌握各算法、数据结构，那是基础，而这种建模思想却是在其上更为珍贵的、更为有趣的东西

Code

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define eps 1e-8
#define PI acos(-1.0)
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
#define Close ios::sync_with_stdio(false);

const int N = 805;

int n, m, maxflow, deep[N];

struct edge
{
    int to, w, pre;
} a[200005];

int cnt = -1;
int head[N], start, over, q[N], fro, bac;

///网络流中的单向边实际是添加两条边的
///那么双向边对应实际添加四条边
void add(int from, int to, int w)
{
    a[++cnt].to = to;
    a[cnt].pre = head[from];
    a[cnt].w = w;
    head[from] = cnt;
    a[++cnt].to = from;
    a[cnt].pre = head[to];
    a[cnt].w = 0;
    head[to] = cnt;
}

bool bfs()
{
    memset(deep, -1, sizeof(deep));
    fro = bac = 0;
    q[bac++] = start, deep[start] = 0;

    while(fro < bac)
    {
        int first = q[fro++];
        for(int i = head[first]; i != -1; i = a[i].pre)
        {
            int v = a[i].to;
            if(deep[v] < 0 && a[i].w > 0)
            {
                deep[v] = deep[first] + 1;
                q[bac++] = v;
            }
        }
    }
    return deep[over] > 0;
}

int DFS(int s, int cap)
{
    if(s == over)
        return cap;

    int f;
    for(int i = head[s]; i != -1; i = a[i].pre)
    {
        int to = a[i].to;
        if(a[i].w > 0 && deep[to] == deep[s] + 1 &&(f = DFS(to, min(cap, a[i].w))) )
        {
            a[i].w -= f;
            a[i ^ 1].w += f;
            return f;
        }
    }
    deep[s] = -1;
    return 0;
}


void Dinic()
{
    int temp;
    while(bfs())
        while((temp = DFS(start, INF)) > 0)
            maxflow += temp;
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        int cost, u, v;
        memset(head, -1, sizeof(head));
        cnt = -1, maxflow = 0;
        scanf("%d%d", &start, &over);///真起点与伪终点
        over += n;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &cost);
            add(i, i + n, cost);
        }
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d", &u, &v);
            add(u + n, v, INF);
            add(v + n, u, INF);
        }
        Dinic();
        cout << maxflow << '\n';
    }
    return 0;
}
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

图论一顿套模板，只把main函数里输入添边改一下就行……