网络流之最大流Dinic --- poj 1459
2019-05-13 07:11:28来源:博客园 阅读 ()
题目链接
Description
Input
Output
Sample Input
2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)20 7 2 3 13 (0,0)1 (0,1)2 (0,2)5 (1,0)1 (1,2)8 (2,3)1 (2,4)7 (3,5)2 (3,6)5 (4,2)7 (4,3)5 (4,5)1 (6,0)5 (0)5 (1)2 (3)2 (4)1 (5)4
Sample Output
15 6
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cstdlib> #include <queue> using namespace std; const int N = 105; const int MAXN = 1e9 + 7; struct Edge { int to; int value; int next; }e[2*N*N]; int head[N], cnt; int deep[N]; int n, np, nc, m; void insert(int u, int v, int value) { e[++cnt].to = v; e[cnt].value = value; e[cnt].next = head[u]; head[u] = cnt; } void init() { memset(head, -1, sizeof(head)); cnt = -1; } bool BFS() { memset(deep,-1,sizeof(deep)); queue<int> Q; deep[0] = 0; Q.push(0); while (!Q.empty()) { int u = Q.front(); Q.pop(); for (int edge = head[u]; edge != -1; edge = e[edge].next) { int v = e[edge].to; if (deep[v] == -1 && e[edge].value > 0) { deep[v] = deep[u] + 1; Q.push(v); } } } if (deep[n + 1] == -1) return false; return true; } int DFS(int u,int flow_pre) { if (u == n + 1) return flow_pre; int flow = 0; for (int edge = head[u]; edge != -1; edge = e[edge].next) { int v = e[edge].to; if (deep[v] != deep[u]+1 || e[edge].value==0) continue; int _flow= DFS(v, min(flow_pre, e[edge].value)); flow_pre -= _flow; flow += _flow; e[edge].value -= _flow; e[edge ^ 1].value += _flow; if (flow_pre == 0) break; } if (flow == 0) deep[u] = -1; return flow; } int GetMaxFlow() { int ans = 0; while (BFS()) { ans += DFS(0,MAXN); } return ans; } int main() { while (scanf("%d%d%d%d", &n, &np, &nc, &m) != EOF) { init(); int u, v, z; for (int i = 0; i < m; i++) { scanf(" (%d,%d)%d", &u, &v, &z); insert(u+1, v+1, z); insert(v+1, u+1, 0); } for (int i = 0; i < np; i++) { scanf(" (%d)%d", &u, &z); insert(0, u+1, z); insert(u+1, 0, 0); } for (int i = 0; i < nc; i++) { scanf(" (%d)%d", &u, &z); insert(u + 1, n + 1, z); insert(n + 1, u + 1, 0); } printf("%d\n",GetMaxFlow()); } }
原文链接:https://www.cnblogs.com/chen9510/p/10846876.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 一个工业级、跨平台、轻量级的 tcp 网络服务框架:gevent 2020-06-05
- 动态规划:最大子串和 2020-01-30
- 【新年呈献】高性能网络通信框架 HP-Socket v5.7.1 2020-01-07
- 最小割最大流定理&残量网络的性质 2019-12-17
- 北华大学网络赛题 2019-12-07
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash