luoguP1343 地震逃生（网络流最大流模板）

题目描述

汶川地震发生时，四川**中学正在上课，一看地震发生，老师们立刻带领x名学生逃跑，整个学校可以抽象地看成一个有向图，图中有n个点，m条边。1号点为教室，n号点为安全地带，每条边都只能容纳一定量的学生，超过楼就要倒塌，由于人数太多，校长决定让同学们分成几批逃生，只有第一批学生全部逃生完毕后，第二批学生才能从1号点出发逃生，现在请你帮校长算算，每批最多能运出多少个学生，x名学生分几批才能运完。

输入格式

第一行3个整数n,m,x(x<2^31,n<=200,m<=2000)；以下m行，每行三个整数a,b,c（a1,a<>b,0描述一条边，分别代表从a点到b点有一条边，且可容纳c名学生。

输出格式

两个整数，分别表示每批最多能运出多少个学生，x名学生分几批才能运完。如果无法到达目的地（n号点）则输出“Orz Ni Jinan Saint Cow!”

输入输出样例

输入

6 7 7
1 2 1
1 4 2
2 3 1
4 5 1
4 3 1
3 6 2
5 6 1

输出

3 3

说明/提示

【注释】

比如有图

1 2 100

2 3 1

100个学生先冲到2号点，然后1个1个慢慢沿2-3边走过去

18神牛规定这样是不可以的……

也就是说，每批学生必须同时从起点出发，并且同时到达终点

网络流详解戳这里https://blog.csdn.net/weixin_43907802/article/details/84705855

以下是kuangbin的模板

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 205;
const int M = 4005;    //边集二倍
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

int head[N], dis[N], tot, n, m, x;
struct Edge {
    int to, next, cap, flow;
}edge[M];

void init() {
    tot = 2;
    memset(head, -1, sizeof(head));
}

void addedge(int u, int v, int w, int rw = 0) {
    edge[tot].to = v;
    edge[tot].cap = w;
    edge[tot].flow = 0;
    edge[tot].next = head[u];
    head[u] = tot++;

    edge[tot].to = u;
    edge[tot].cap = rw;
    edge[tot].flow = 0;
    edge[tot].next = head[v];
    head[v] = tot++;
}

int Q[N];
int dep[N], cur[N], sta[N]; ///数组cur记录点u之前循环到了哪一条边
bool bfs(int s, int t, int n) {
    int fron = 0, tail = 0;
    memset(dep, -1, sizeof(dep[0]) * (n + 1));
    dep[s] = 0;
    Q[tail++] = s;
    while(fron < tail) {
        int u = Q[fron++];
        for(int i = head[u]; i != -1; i = edge[i].next) {
            int v = edge[i].to;
            if(edge[i].cap > edge[i].flow && dep[v] == -1) {
                dep[v] = dep[u] + 1;
                if(v == t) return true;
                Q[tail++] = v;
            }
        }
    }
    return false;
}

int dinic(int s, int t, int n) {
    int maxflow = 0;
    while(bfs(s, t, n)) {
        for(int i = 0; i <= n; ++i) cur[i] = head[i];
        int u = s, tail = 0;
        while(cur[s] != -1) {
            if(u == t) {
                int tp = inf;
                for(int i = tail - 1; i >= 0; --i)
                    tp = min(tp, edge[sta[i]].cap - edge[sta[i]].flow);
                maxflow += tp;
                for(int i = tail - 1; i >= 0; --i) {
                    edge[sta[i]].flow += tp;
                    edge[sta[i] ^ 1].flow -= tp;
                    if(edge[sta[i]].cap - edge[sta[i]].flow == 0)
                        tail = i;
                }
                u = edge[sta[tail] ^ 1].to;
            }
            else if(cur[u] != -1 && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] + 1 == dep[edge[cur[u]].to]) {
                sta[tail++] = cur[u];
                u = edge[cur[u]].to;
            }
            else {
                while(u != s && cur[u] == -1)
                    u = edge[sta[--tail] ^ 1].to;
                cur[u] = edge[cur[u]].next;
            }
        }
    }
    return maxflow;
}

int main() {
    init();
    int u, v, w;
    scanf("%d%d%d", &n, &m, &x);
    for(int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        addedge(u, v, w);
    }
    int maxflow = dinic(1, n, n);
    if(maxflow == 0) {
        printf("Orz Ni Jinan Saint Cow!\n");
        return 0;
    }
    int cnt = x / maxflow;
    if(x % maxflow) cnt++;
    printf("%d %d\n", maxflow, cnt);
    return 0;
}