首页 > 代码库 > HDU4289Control(最大流)
HDU4289Control(最大流)
看了这道题，然后重新开始练习自己的刚敲不久的网络流，发现还是难以一遍敲得完整啊，，，，，
调了。。。遍，改了。。。遍，测了。。。遍，交了，，，遍，总算是A了，，不简单啊
然后试着用了其他两种算法EK和dinic都试着去练习一下，慢慢A了，，，真是不简单有木有
题目大意是这样的，有一些小偷打算从城市S到城市T,但是我们不知道他们会走哪些边，为了确保一定可以能够抓住所有的小偷，现在需要在某些城市布置一些警察，已知在城市i布置的花费是P[i],现在要使的抓住小偷的同时我的花费最小，求最小花费。
这里用到了最大流的一个定理，最小割最大流定理：当起点到终点的最大流算出来时，这个最大流就是将图划分为两个互不连通的集合的最小割。证明可以自己百度或看其他神牛的博客。
有了这个定理，就变成了裸的最大流问题了
下面我试着用三种方法做了这道题，比较了一下发现最快的依然是SAP，其次是dinic，最后是EK算法
SAP
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <vector> 8 #include <cstdio> 9 #include <cctype> 10 #include <cstring> 11 #include <cstdlib> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 #define INF 0x3f3f3f3f 16 #define inf ((LL)1<<40) 17 #define lson k<<1, L, mid 18 #define rson k<<1|1, mid+1, R 19 #define mem0(a) memset(a,0,sizeof(a)) 20 #define mem1(a) memset(a,-1,sizeof(a)) 21 #define mem(a, b) memset(a, b, sizeof(a)) 22 #define FOPENIN(IN) freopen(IN, "r", stdin) 23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout) 24 template<class T> T ABS ( T a) { return a >= 0 ? a : -a; } 25 template<class T> T CMP_MIN ( T a, T b ) { return a < b; } 26 template<class T> T CMP_MAX ( T a, T b ) { return a > b; } 27 template<class T> T MAX ( T a, T b ) { return a > b ? a : b; } 28 template<class T> T MIN ( T a, T b ) { return a < b ? a : b; } 29 template<class T> T GCD ( T a, T b ) { return b ? GCD ( b, a % b ) : a; } 30 template<class T> T LCM ( T a, T b ) { return a / GCD ( a, b ) * b; } 31 template<class T> void SWAP( T& a, T& b ) { T t = a; a = b; b = t; } 32 33 typedef __int64 LL; 34 //typedef long long LL; 35 const int MAXN = 1010; 36 const int MAXM = 200100; 37 const double eps = 1e-14; 38 const double PI = 4.0 * atan(1.0); 39 const LL MOD = 1000000007; 40 41 #define L(i) (i<<1) 42 #define R(i) (i<<1|1) 43 44 int m, n, s, d; 45 struct Edge { int to, cap, next; }edge[MAXM<<3]; 46 int tot, head[MAXN]; 47 48 int src, des; 49 int gap[MAXN], dep[MAXN], aug[MAXN], cur[MAXN], pre[MAXN]; 50 51 void addEdge(int u, int v, int c) 52 { 53 edge[tot].to = v; edge[tot].cap = c; edge[tot].next = head[u]; 54 head[u] = tot ++; 55 edge[tot].to = u; edge[tot].cap = 0; edge[tot].next = head[v]; 56 head[v] = tot ++; 57 } 58 59 void init() 60 { 61 int x, y; 62 tot = 0; 63 mem1(head); mem0(edge); 64 scanf("%d %d", &s, &d); 65 for(int i = 1; i <= n; i ++) 66 { 67 scanf("%d", &x); 68 addEdge(L(i), R(i), x); 69 addEdge(R(i), L(i), x); 70 } 71 for(int i = 0; i < m; i ++) 72 { 73 scanf("%d %d", &x, &y); 74 addEdge(R(x), L(y), INF); 75 addEdge(R(y), L(x), INF); 76 } 77 src = http://www.mamicode.com/0; 78 des = (n+1)<<1; 79 addEdge(src, L(s), INF); 80 addEdge(R(d), des, INF); 81 } 82 83 int SAP(int n) 84 { 85 mem0(gap); 86 mem0(dep); 87 mem0(aug); 88 mem0(pre); 89 aug[src] = INF; 90 pre[src] = -1; 91 gap[0] = n; 92 int max_flow = 0, u = src; 93 for(int i = 0; i <= n; i ++) 94 cur[i] = head[i]; 95 while(dep[src] < n) 96 { 97 if(u == des) 98 { 99 max_flow += aug[des];100 for(int v = pre[des]; v != -1; v = pre[v])101 {102 int id = cur[v];103 edge[id].cap -= aug[des];104 edge[id^1].cap += aug[des];105 aug[v] -= aug[des];106 if(edge[id].cap == 0)107 u = v;108 }109 }110 int flag = 0;111 for(int i = cur[u]; i != -1; i = edge[i].next)112 {113 int v = edge[i].to;114 if(edge[i].cap > 0 && dep[u] == dep[v]+1)115 {116 flag = 1;117 pre[v]= u;118 cur[u] = i;119 aug[v] = MIN(aug[u], edge[i].cap);120 u = v;121 break;122 }123 }124 if(!flag)125 {126 if(--gap[dep[u]] == 0)127 break;128 int min_dep = n;129 cur[u] = head[u];130 for(int i = head[u]; i != -1; i = edge[i].next)131 {132 int v = edge[i].to;133 if(edge[i].cap > 0 && dep[v] < min_dep)134 {135 min_dep = dep[v];136 cur[u] = i;137 }138 }139 dep[u] = min_dep + 1;140 gap[dep[u]] ++;141 if(pre[u] != -1) u = pre[u];142 }143 }144 return max_flow;145 }146 147 int main()148 {149 while(~scanf("%d %d", &n, &m))150 {151 init();152 printf("%d\n", SAP(des));153 }154 return 0;155 }
dinic
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <vector> 8 #include <cstdio> 9 #include <cctype> 10 #include <cstring> 11 #include <cstdlib> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 #define INF 0x3f3f3f3f 16 #define inf ((LL)1<<40) 17 #define lson k<<1, L, mid 18 #define rson k<<1|1, mid+1, R 19 #define mem0(a) memset(a,0,sizeof(a)) 20 #define mem1(a) memset(a,-1,sizeof(a)) 21 #define mem(a, b) memset(a, b, sizeof(a)) 22 #define FOPENIN(IN) freopen(IN, "r", stdin) 23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout) 24 template<class T> T ABS ( T a) { return a >= 0 ? a : -a; } 25 template<class T> T CMP_MIN ( T a, T b ) { return a < b; } 26 template<class T> T CMP_MAX ( T a, T b ) { return a > b; } 27 template<class T> T MAX ( T a, T b ) { return a > b ? a : b; } 28 template<class T> T MIN ( T a, T b ) { return a < b ? a : b; } 29 template<class T> T GCD ( T a, T b ) { return b ? GCD ( b, a % b ) : a; } 30 template<class T> T LCM ( T a, T b ) { return a / GCD ( a, b ) * b; } 31 template<class T> void SWAP( T& a, T& b ) { T t = a; a = b; b = t; } 32 33 typedef __int64 LL; 34 //typedef long long LL; 35 const int MAXN = 1010; 36 const int MAXM = 200100; 37 const double eps = 1e-14; 38 const double PI = 4.0 * atan(1.0); 39 const LL MOD = 1000000007; 40 41 #define L(i) (i<<1) 42 #define R(i) (i<<1|1) 43 44 int m, n, s, d; 45 struct Edge { int to, cap, next; }edge[MAXM<<3]; 46 int tot, head[MAXN]; 47 48 int src, des; 49 int dis[MAXN]; 50 51 void addEdge(int u, int v, int c) 52 { 53 edge[tot].to = v; edge[tot].cap = c; edge[tot].next = head[u]; 54 head[u] = tot ++; 55 edge[tot].to = u; edge[tot].cap = 0; edge[tot].next = head[v]; 56 head[v] = tot ++; 57 } 58 59 void init() 60 { 61 int x, y; 62 tot = 0; 63 mem1(head); mem0(edge); 64 scanf("%d %d", &s, &d); 65 for(int i = 1; i <= n; i ++) 66 { 67 scanf("%d", &x); 68 addEdge(L(i), R(i), x); 69 addEdge(R(i), L(i), x); 70 } 71 for(int i = 0; i < m; i ++) 72 { 73 scanf("%d %d", &x, &y); 74 addEdge(R(x), L(y), INF); 75 addEdge(R(y), L(x), INF); 76 } 77 src = http://www.mamicode.com/0; 78 des = (n+1)<<1; 79 addEdge(src, L(s), INF); 80 addEdge(R(d), des, INF); 81 } 82 83 bool bfs() 84 { 85 queue<int>q; 86 mem1(dis); 87 dis[src] = 0; 88 q.push(src); 89 while(!q.empty()) 90 { 91 int u = q.front(); q.pop(); 92 for(int i = head[u]; i != -1; i = edge[i].next) 93 { 94 int v = edge[i].to; 95 if(dis[v] == -1 && edge[i].cap > 0) 96 { 97 dis[v] = dis[u] + 1; 98 q.push(v); 99 }100 }101 }102 return dis[des] != -1;103 }104 105 int dfs(int cur, int aug)106 {107 if(cur == des || aug == 0)108 return aug;109 int flow = 0;110 for(int i = head[cur]; i != -1; i = edge[i].next)111 {112 int v = edge[i].to;113 if ( dis[v] == dis[cur]+1 && edge[i].cap > 0 )114 {115 int f = dfs( v, MIN(edge[i].cap, aug) );116 edge[i].cap -= f;117 edge[i^1].cap += f;118 flow += f;119 aug -= f;120 if(aug == 0)121 break;122 }123 }124 return flow;125 }126 127 int dinic()128 {129 int res = 0;130 while (bfs())131 {132 res += dfs(src, INF);133 }134 return res;135 }136 137 int main()138 {139 //FOPENIN("in.txt");140 while(~scanf("%d %d", &n, &m))141 {142 init();143 printf("%d\n", dinic());144 }145 return 0;146 }
EK
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <vector> 8 #include <cstdio> 9 #include <cctype> 10 #include <cstring> 11 #include <cstdlib> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 #define INF 0x3f3f3f3f 16 #define inf ((LL)1<<40) 17 #define lson k<<1, L, mid 18 #define rson k<<1|1, mid+1, R 19 #define mem0(a) memset(a,0,sizeof(a)) 20 #define mem1(a) memset(a,-1,sizeof(a)) 21 #define mem(a, b) memset(a, b, sizeof(a)) 22 #define FOPENIN(IN) freopen(IN, "r", stdin) 23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout) 24 template<class T> T ABS ( T a) { return a >= 0 ? a : -a; } 25 template<class T> T CMP_MIN ( T a, T b ) { return a < b; } 26 template<class T> T CMP_MAX ( T a, T b ) { return a > b; } 27 template<class T> T MAX ( T a, T b ) { return a > b ? a : b; } 28 template<class T> T MIN ( T a, T b ) { return a < b ? a : b; } 29 template<class T> T GCD ( T a, T b ) { return b ? GCD ( b, a % b ) : a; } 30 template<class T> T LCM ( T a, T b ) { return a / GCD ( a, b ) * b; } 31 template<class T> void SWAP( T& a, T& b ) { T t = a; a = b; b = t; } 32 33 typedef __int64 LL; 34 //typedef long long LL; 35 const int MAXN = 440; 36 const int MAXM = 200100; 37 const double eps = 1e-14; 38 const double PI = 4.0 * atan(1.0); 39 const LL MOD = 1000000007; 40 41 #define L(i) (i<<1) 42 #define R(i) (i<<1|1) 43 44 int n, m, s, d; 45 46 int src, des; 47 int cap[MAXN][MAXN], flow[MAXN][MAXN], pre[MAXN], a[MAXN]; 48 49 void init() 50 { 51 int x, y; 52 src = http://www.mamicode.com/1; 53 des = (n+1)<<1; 54 mem0(cap);mem0(pre); 55 scanf("%d %d", &s, &d); 56 cap[src][L(s)] = INF; 57 cap[R(d)][des] = INF; 58 for(int i = 1; i <= n; i ++) 59 { 60 scanf("%d", &x); 61 cap[L(i)][R(i)] = x; 62 cap[R(i)][L(i)] = x; 63 } 64 for(int i = 0; i < m; i ++) 65 { 66 scanf("%d %d", &x, &y); 67 cap[R(x)][L(y)] = INF; 68 cap[R(y)][L(x)] = INF; 69 } 70 } 71 72 int EK(int n) 73 { 74 queue<int>q; 75 mem0(flow); 76 int max_flow = 0; 77 while(true) 78 { 79 mem0(a); 80 a[src] = INF; 81 q.push(src); 82 while(!q.empty()) 83 { 84 int u = q.front(); q.pop(); 85 for(int v = 1; v <= n; v ++) if(!a[v] && cap[u][v]>flow[u][v]) 86 { 87 pre[v]= u; 88 q.push(v); 89 a[v] = MIN(a[u], cap[u][v] - flow[u][v]); 90 } 91 } 92 if(a[des] == 0) break; 93 for(int u = des; u != src; u = pre[u]) 94 { 95 flow[pre[u]][u] += a[des]; 96 flow[u][pre[u]] -= a[des]; 97 } 98 max_flow += a[des]; 99 }100 return max_flow;101 }102 103 int main()104 {105 //FOPENIN("in.txt");106 while(~scanf("%d %d", &n, &m))107 {108 init();109 printf("%d\n", EK(des));110 }111 return 0;112 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。