# BZOJ 1570 JSOI 2008 Blue Mary的旅行 网络流

## CODE

```#define _CRT_SECURE_NO_WARNINGS #include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 100010 #define MAXE 1000010 #define S 0 #define SS (MAX - 2) #define T (MAX - 1) #define INF 0x3f3f3f3f using namespace std; struct Edge{ int x, y, z; void Read() { scanf("%d%d%d", &x, &y, &z); } }edge[MAXE]; struct MaxFlow{ int head[MAX], total; int _next[MAXE], aim[MAXE], flow[MAXE]; int backup_flow[MAXE]; int deep[MAXE]; MaxFlow():total(1) {} void Add(int x, int y, int f) { _next[++total] = head[x]; aim[total] = y; backup_flow[total] = f; head[x] = total; } void Insert(int x, int y, int f) { Add(x, y, f); Add(y, x, 0); } bool BFS() { static queue<int> q; while(!q.empty()) q.pop(); memset(deep, 0, sizeof(deep)); deep[S] = 1; q.push(S); while(!q.empty()) { int x = q.front(); q.pop(); for(int i = head[x]; i; i = _next[i]) if(flow[i] && !deep[aim[i]]) { deep[aim[i]] = deep[x] + 1; q.push(aim[i]); if(aim[i] == T) return true; } } return false; } int Dinic(int x, int f) { if(x == T) return f; int temp = f; for(int i = head[x]; i; i = _next[i]) if(flow[i] && temp && deep[aim[i]] == deep[x] + 1) { int away = Dinic(aim[i], min(flow[i], temp)); if(!away) deep[aim[i]] = 0; flow[i] -= away; flow[i ^ 1] += away; temp -= away; } return f - temp; } }solver; int points, edges, persons; ```

```int main() { cin >> points >> edges >> persons; for(int i = 1; i <= edges; ++i) edge[i].Read(); solver.Insert(S, SS, persons); int now = 0; for(int i = 1;; ++i) { for(int j = 1; j <= edges; ++j) solver.Insert(now + edge[j].x, now + edge[j].y + points, edge[j].z); solver.Insert(now + points + points, T, INF); solver.Insert(SS, now + 1, INF); memcpy(solver.flow, solver.backup_flow, sizeof(solver.flow)); int max_flow = 0; while(solver.BFS()) max_flow += solver.Dinic(S, INF); if(max_flow == persons) { cout << i << endl; return 0; } now += points; } return 0; }```

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！