题目大意
给出一个有向图，每天每人只能做一次飞机。现在给出起点，终点，和需要走的人数，还有每条航线的限制人数，问最少多少天最慢的人到达终点。
思路
很明显是网络流的模型，，至于如何去验证，其实连二分都不用，枚举最少天数，然后每次加一层边进行验证就行了。
CODE;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;}
在爱情里，有时候简单的一句话，能胜过千言万语。
