链接：https://www.luogu.com.cn/problem/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!”

输入输出样例

输入 #1复制

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

输出 #1复制

3 3

说明/提示

【注释】

比如有图

1 2 100

2 3 1

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

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

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

题解：裸的网络流最大流板子题

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200000+10,M=1e4+5,mod=1e9+7;
ll n,m,s,t,h[N],cur[N],cnt=1,vis[N];
struct node{
    ll to,nt,w;
}e[N];
void add(ll u,ll v,ll w)
{
    e[++cnt]={v,h[u],w};
    h[u]=cnt;
}
queue<ll>q;
bool bfs()
{
    memset(vis,0,sizeof(vis));
    vis[s]=1;
    q.push(s);
    while(!q.empty())
    {
        ll u=q.front();
        q.pop();
        cur[u]=h[u];
        for(ll i=h[u];i;i=e[i].nt)
        {
            ll v=e[i].to,w=e[i].w;
            if(w&&!vis[v])
            {
                vis[v]=vis[u]+1;
                q.push(v);
            }
        }
    }
    return vis[t];

}
ll dfs(ll u,ll flow)
{
    if(u==t)
        return flow;
    ll res=flow;
    for(ll i=cur[u];i;i=e[i].nt)
    {
        ll v=e[i].to,w=e[i].w;
        if(w&&vis[u]+1==vis[v])
        {
            ll now=dfs(v,min(res,w));
            if(!now)
                vis[v]=1;
            else
            {
                e[i].w-=now;
                e[i^1].w+=now;
                res-=now;
            }
        }
        if(!res)
        return flow;
    }
    return flow-res;
}
ll T,x;
int main()
{
    //cin>>T;
    //while(T--)
    {
        cin>>n>>m>>x;
        s=1;
        t=n;
        for(int i=1;i<=m;i++)
        {
            ll u,v,w;
            cin>>u>>v>>w;
            add(u,v,w);
            add(v,u,0);

        }
        ll ans=0;
        while(bfs())
        {
            ans+=dfs(s,0x7fffffff);
        }
        if(ans==0&&x!=0)
            cout<<"Orz Ni Jinan Saint Cow!"<<endl;
        else if(ans>=x)
        cout<<ans<<" "<<1<<endl;
        else
        {
            ll k=ceil(x*1.0/ans);
            cout<<ans<<" "<<k<<endl;

        }

    }
    return 0;
}