题解 P1343 【地震逃生】

苏幕寒 · 2019-08-03 09:37:25 · 题解

其实这道题目就是一道朴素的求最大流的题目； 先bfs分层；再dfs对每一层次的流量进行修改； 最后输出答案就可以了；不会的可以先去做一 下 P3376 这道模板题； 上代码：

#include<bits/stdc++.h>
using namespace std;
const int N=10005;
int n,m,s;
struct edge{
    int v,nxt,val;
}e[N*2];
int head[N],cnt=1;
int dis[N];
int maxflow;
void add(int u,int v,int val){
    e[++cnt]=(edge){v,head[u],val};head[u]=cnt;
    e[++cnt]=(edge){u,head[v],0};head[v]=cnt;
}
bool bfs()
{
    queue<int>q;
    memset(dis,-1,sizeof(dis));
    q.push(1);dis[1]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=head[x];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(dis[v]==-1&&e[i].val)
            {
                q.push(v);
                dis[v]=dis[x]+1;
            }
        }
    }
    return dis[n]!=-1;
}
int dfs(int u,int flow)
{
    if(u==n) return flow;
    int res=0;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(dis[v]==dis[u]+1&&e[i].val)
        {
            int fl=dfs(v,min(e[i].val,flow));
            if(fl)
            {
                e[i].val-=fl;e[i^1].val+=fl;
                flow-=fl;res+=fl;
                if(!flow) return res;
            }
        }
    }
    return res;
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        int x,y,val;
        scanf("%d%d%d",&x,&y,&val);
        add(x,y,val);
    }
    while(bfs()) maxflow+=dfs(1,1<<29);
    if(maxflow)printf("%d ",maxflow);
    else {
        printf("Orz Ni Jinan Saint Cow!");
        return 0;   
    }
    if(s%maxflow==0) printf("%d",s/maxflow);
    else printf("%d",s/maxflow+1);
    return 0;
}