avatar
fireworks99
keep hungry keep foolish

UVA 10480 Sabotage(最小割)

Description

N个城市,M条连接城市的边,现在要切断城市1与城市2间的联络,求最小费用

Attention

一般的网络流知道了S(源点)T(汇点),就默认了流向,所以路是单向的(两条边,w+0)

但这题不同,两城市是等价的,都是S都是T,所以路是双向的(两条边,w+w)

若是已知唯一的S(源点)T(汇点),而题目又暗示(或明示)路是双向的(四条边w+0+w+0)

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; ll n, m, maxflow, deep[N], u[N], v[N]; struct edge { ll to, w, pre; } a[200005]; int cnt = -1; ll 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 = w; head[to] = cnt; } bool bfs() { memset(deep, -1, sizeof(deep)); fro = bac = 0; q[bac++] = start, deep[start] = 0; while(fro < bac) { ll first = q[fro++]; for(int i = head[first]; i != -1; i = a[i].pre) { ll v = a[i].to; if(deep[v] < 0 && a[i].w > 0) { deep[v] = deep[first] + 1; q[bac++] = v; } } } return deep[over] > 0; } ll DFS(ll s, ll cap) { if(s == over) return cap; ll f; for(int i = head[s]; i != -1; i = a[i].pre) { ll 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() { ll temp; while(bfs()) while((temp = DFS(start, INF)) > 0) maxflow += temp; } int main() { while(~scanf("%lld%lld", &n, &m)) { if(n == 0 && m == 0) break; ll cost; start = 1, over = 2; memset(head, -1, sizeof(head)); memset(u, 0, sizeof(u)); memset(v, 0, sizeof(v)); cnt = -1, maxflow = 0; for(int i = 0; i < m; ++i) { scanf("%lld%lld%lld", &u[i], &v[i], &cost); add(u[i], v[i], cost); } Dinic(); for(int i = 0; i < m; ++i) { if((deep[ u[i] ] < 0 && deep[ v[i] ] >= 0) || (deep[ v[i] ] < 0 && deep[ u[i] ] >= 0)) cout << u[i] << ' ' << v[i] << '\n'; } cout << '\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
  • 127
  • 128
  • 129
Site by Baole Zhao | Powered by Hexo | theme PreciousJoy