题解 P1343 【地震逃生】

半仙胡小桃 · 2017-04-23 08:41:01 · 题解

很简单的最大流

我是EK也就是动能算法（滑稽）

找1到n能通过的学生的最大人数，如果是0，就没法逃出去了

如果能逃出去就用人数除以一次逃出的人数，如果除不尽要+1次啊，不能舍下剩下的人不管了不是吗233

#include <iostream>  
#include <queue>  
#include <string.h>  
#include <queue> 
#include <cstdio>
using namespace std;  
int maxData = 0x7fffffff; 
queue<int> dl;
int flow[10001];
struct ss{
    int d;
    int wb;
};
struct node{
    int to;
    int cap;
    int rev;
};
vector<node> v[10001];
ss pre[10001];
int n,m;
void add(int from,int to,int cap)
{
    v[from].push_back((node){to,cap,v[to].size()});
    v[to].push_back((node){from,0,v[from].size()-1}); 
}
int BFS(int s,int t)
{
    while(!dl.empty())
     dl.pop();
    for(int i=1;i<=n;i++)
     pre[i].d=-1;
    pre[s].d=0;
    flow[s]=maxData;
    dl.push(s);
    while(!dl.empty())
    {
        int dd=dl.front();
        dl.pop();
        if(dd==t)
         break;
        for(int i=0;i<v[dd].size();i++)
         {
             node &tmp=v[dd][i];
             if(tmp.to!=s&&tmp.cap>0&&pre[tmp.to].d==-1)
              {
                  pre[tmp.to].d=dd;
                  pre[tmp.to].wb=i;
                  flow[tmp.to]=min(flow[dd],tmp.cap);
                  dl.push(tmp.to);
              }
         }
    }
    if(pre[t].d==-1)
     return -1;
    else 
     return flow[t];
}
int max_flow(int s,int t)
{
    int mflow=0;
    int d=0;
    while((d=BFS(s,t))!=-1)
    {
        int k=t;
        while(k!=s)
         {
           v[pre[k].d][pre[k].wb].cap-=d;
           v[k][v[pre[k].d][pre[k].wb].rev].cap+=d;
           k=pre[k].d;
         } 
        mflow+=d;
    }
    return mflow;
}
int main()
{
    int num;
    scanf("%d%d%d",&n,&m,&num);
    for(int i=1;i<=m;i++)
     {
         int x,y,c;
         scanf("%d%d%d",&x,&y,&c);
         add(x,y,c);
     }
    int c=max_flow(1,n);
    if(!c) puts("Orz Ni Jinan Saint Cow!");
    else   
    {
        printf("%d ",c);
        int s=num/c;
        if(num%c) s++;
        printf("%d",s);
    }
}