-网络流-最大流- [洛谷 P1343]地震逃生

题目描述

汶川地震发生时，四川**中学正在上课，一看地震发生，老师们立刻带领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神牛规定这样是不可以的……

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

Solution

这道题可以用最大流解决，然后再用总人数除以最大流量就可以了。

记住，如果有余数，就要+1毕竟剩下的人也是人啊

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define MAXN 1000002
#define INF 2000000000
namespace STman {
    template <typename Tp>
    inline void read(Tp &x) {
    #define C getchar()
        Tp f = 1;
        x = 0;
        char k = C;
        while (k < '0' || k > '9') {
            if (k == '-') f = -1;
            k = C;
        }
        while (k >= '0' && k <= '9') {
            x = x * 10 + k - '0';
            k = C;
        }
        x = x * f;
    #undef C
    }
    template <typename Tp>
    inline void write(Tp x) {
        if (x < 0) putchar('-') , x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename Tp>
    inline Tp max(Tp a , Tp b) {
        if (a > b) return a;
        else return b;
    }
    template <typename Tp>
    inline Tp min(Tp a , Tp b) {
        if (a < b) return a;
        else return b;
    }
    template <typename Tp>
    inline void swap(Tp &a , Tp &b) {
        Tp t = a;
        a = b;
        b = a;
    }
    template <typename Tp>
    inline Tp abs(Tp &a) {
        if (a < 0) return -a;
        else return a;
    }
    inline void sp() {
        putchar(32);
    }
    inline void et() {
        putchar(10);
    }
}
using namespace STman;
struct Edge {
    int v , nx , w;
} e[MAXN];
std::queue <int> q;
int n , m , maxfl , total , head[MAXN] , ecnt = 1  , x , y , z , r , k , dep[MAXN] , cur[MAXN];
void add(int f , int t , int w) {
    e[++ecnt] = (Edge) {t , head[f] , w};
    head[f] = ecnt;
    e[++ecnt] = (Edge) {f , head[t] , 0};
    head[t] = ecnt;
}
bool bfs(int s , int t) {
    memset(dep , 0x7f , sizeof(dep));
    while (!q.empty()) q.pop();
    for (int i = 1 ; i <= n ; i++) {
        cur[i] = head[i];
    }
    dep[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int i = head[v] ; i ; i = e[i].nx) {
            int to = e[i].v;
            if (dep[to] > INF && e[i].w) {
                dep[to] = dep[v] + 1;
                q.push(to);
            }
        }
    }
    if (dep[t] < INF) return 1;
    else return 0;
}
int dfs(int u , int t , int l) {
    if (!l || u == t) return l;
    int fl = 0 , f;
    for (int i = cur[u] ; i ; i = e[i].nx) {
        cur[u] = i;
        int to = e[i].v;
        if (dep[to] == dep[u] + 1 && (f = dfs(to , t , min(l , e[i].w)))) {
            fl += f;
            l -= f;
            e[i ^ 1].w += f;
            e[i].w -= f;
            if (!l) break;
        }
    }
    return fl;
}
int Dinic(int s , int t) {
    int maxf = 0;
    while (bfs(s , t)) {
        maxf += dfs(s , t , INF);
    }
    return maxf;
}
int main() {
    read(n) , read(m) , read(total);
    r = 1;
    k = n;
    for (int i = 1 ; i <= m ; i++) {
        read(x) , read(y) , read(z);
        add(x , y , z);
    }
    maxfl = Dinic(r , k);
    if (!maxfl) {
        puts("Orz Ni Jinan Saint Cow!");
        return 0;
    }
    write(maxfl) , sp();
    write(total / maxfl + ((total % maxfl == 0) ? 0 : 1));
    return 0;
}