题解 P1343 【地震逃生】

· · 题解

网络流中的最大流，这里用dinic()加前向星解决

#pragma GCC optimize(200000)/不用问为什么,要相信O(200000)优化比O(2)快得多
//至少听起来是这样的
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
struct edge{
    long long next,w,to;
}e[1000005];
inline long long read(){
    long long t=0;
    char v=getchar();
    while(v<'0'||v>'9')v=getchar();
    while(v>='0'&&v<='9'){
        t=(t<<3)+(t<<1)+v-'0';
        v=getchar();
    }
    return t;
}
long long p[1000002];
long long head[1000002],b,c,d,n,m,cnt=1,S,T,x,o;
inline void bu(register long long u,register long long v,register long long w){
      e[++cnt].to=v;
      e[cnt].w+=w;
      e[cnt].next=head[u];
      head[u]=cnt;
      e[++cnt].to=u;
      e[cnt].next=head[v];
      head[v]=cnt;
}   
queue <long long> q;
inline long long spfa(register long long s,register long long t){
    memset(p,-1,sizeof(p));
    while(!q.empty())q.pop();
    q.push(s);
    p[s]=0;
    while(!q.empty()){
        long long r=q.front();
        q.pop();
        if(r==t)return 1;
        for(register long long i=head[r];i;i=e[i].next){
            if(e[i].w>0&&p[e[i].to]<0){
                q.push(e[i].to);
                p[e[i].to]=p[r]+1;
                }
        }
    }
    return 0;
}
inline long long dfs(register long long s,register long long t,register long long mx){
    long long r=0,y=0;
    if(s==t)return mx;
    for(register long long i=head[s];i;i=e[i].next)
        if(e[i].w>0&&p[e[i].to]==p[s]+1){
            y=dfs(e[i].to,t,min(e[i].w,mx));
            e[i].w-=y;
            e[i^1].w+=y;
            r+=y;
            mx-=y;
            if(!mx)return r;
        }

    return r;
}
inline long long dinic(){
    long long ans=0;
    while(spfa(S,T))ans+=dfs(S,T,0x7fffffff);
    return ans;
}
int main(){
    n=read();
    m=read();
    x=read();
    S=1;
    T=n;
    for(register long long i=1;i<=m;++i){
        b=read();
        c=read();
        d=read();
        bu(b,c,d);
    }
    o=dinic();
    if(o==0)printf("Orz Ni Jinan Saint Cow!");
    else printf("%d %d",o,(x+o-1)/o);
}//其实O(200000)没有太大的区别