程序员人生 网站导航

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

栏目:php教程时间:2015-03-24 08:35:11

题目大意

给出1个有向图,每天每人只能做1次飞机。现在给出出发点,终点,和需要走的人数,还有每条航线的限制人数,问最少多少天最慢的人到达终点。

思路

很明显是网络流的模型,至于如何去验证,其实连2分都不用,枚举最少天数,然后每次加1层边进行验证就好了。

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; }
------分隔线----------------------------
------分隔线----------------------------

最新技术推荐