题解 P1343 【地震逃生】

· · 题解

分析

我们看一下补充说明，每次只能额定的学生数量，不能出现拥挤的情况，于是它就在疯狂暗示我们这就是网络流。下面是正解。

这题肯定贪心，由于先送哪个同学没有区别，如果每次放最多的一波人出去肯定不吃亏，所以就一股脑地每次塞最多的一波人出去就行了。

所以现在是看每次最多送几个人。

然后再一看题面，这就是裸的网络流。

dinic 算法写好，算出每次最多几个人，然后除x就行了。

注意，没法逃走的情况即一次一个人都出不去，特判一下就好了。

数据范围呢？出题人很贴心地给我们设置了一个n\le 200的数据，来代表这是真的网络流，不会卡常。不过其实数据还可以再加大，因为网络流的剪枝非常厉害，n再大一点也无妨。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2009;
struct edge{int to,nxt,w;}e[N*2];int hd[N],tot=1;
void add(int u,int v,int w){
    e[++tot]=(edge){v,hd[u],w}; hd[u]=tot;
}

int n,m,d[N],ans,x;
bool bfs(){
    queue<int>q; memset(d,0,sizeof(d));
    q.push(1),d[1]=1;
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int i=hd[u],v;i;i=e[i].nxt)
            if(!d[v=e[i].to]&&e[i].w){
                q.push(v),d[v]=d[u]+1;
                if(v==n) return 1;
            }
    }
    return 0;
} 
int dfs(int u,int flow){
    if(u==n) return flow;
    int rest=flow;
    for(int i=hd[u],v;i&&rest;i=e[i].nxt){
        if(e[i].w&&d[v=e[i].to]==d[u]+1){
            int tmp=dfs(v,min(rest,e[i].w));
            if(!tmp) d[v]=0;
            rest-=tmp; e[i].w-=tmp; e[i^1].w+=tmp;
        }
    }
    return flow-rest; //真正给出去的 
}

int main(){
    scanf("%d%d%d",&n,&m,&x);
    for(int i=1,u,v,w;i<=m;i++)
        scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,0);
    int tmp=0;
    while(bfs()) while(tmp=dfs(1,1e9)) ans+=tmp;
    if(!ans){puts("Orz Ni Jinan Saint Cow!");return 0;} 
    printf("%d ",ans);
    int a2=ceil(x*1./ans);
    printf("%d",a2);
    return 0;
}

然后不知道什么是网络瘤的可以看：我的网络流