首页 > 代码库 > 【洛谷P1343】地震逃生

【洛谷P1343】地震逃生

一道傻吊的网络流题,wori我写的读入优化怎么老T?

远离读入优化报平安?

#include<bits/stdc++.h>
#define N 4005
#define inf 1000000007
using namespace std;
int head[4*N],tot=0,n,m,x,s,t,ans;
struct Edge{int u,v,next,f;}G[2000010];
inline void addedge(int u,int v,int f){
    G[tot].u=u;G[tot].v=v;G[tot].f=f;G[tot].next=head[u];head[u]=tot++;
    G[tot].u=v;G[tot].v=u;G[tot].f=0;G[tot].next=head[v];head[v]=tot++;
}
//struct Queue{
//    int q[1000010],l,r;
//    inline bool empty(){return l>r;}
//    inline void push(int x){q[r++]=x;}
//    inline void pop(){l++;}
//    inline int front(){return q[l];}
//    inline void clear(){l=0;r=0;}
//};
int level[12010];queue<int> q;
struct FastIO{
    static const int S=1310720;
    int wpos;char wbuf[S];
    FastIO():wpos(0) {}
    inline int xchar(){
        static char buf[S];
        static int len=0,pos=0;
        if(pos==len)pos=0,len=fread(buf,1,S,stdin);
        if(pos==len)return -1;
        return buf[pos++];
    }
    inline int xuint(){
        int c=xchar(),x=0;
        while(c<=32&&~c)c=xchar();
        if(c==-1)return -1;
        for(;0<=c&&c<=9;c=xchar())x=x*10+c-0;
        return x;
    }
}io;
inline bool bfs(int s,int t){
    queue<int>q;
    memset(level,0,sizeof(level));
    q.push(s);level[s]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        if(u==t)return 1;
        for(int i=head[u];~i;i=G[i].next){
            int v=G[i].v,f=G[i].f;
            if(f&&!level[v])q.push(v),level[v]=level[u]+1;
        }
    }
    return 0;
}
int dfs(int u,int maxf,int t){
    if(u==t)return maxf;int rat=0;
    for(int i=head[u];~i&&rat<maxf;i=G[i].next){
        int v=G[i].v,f=G[i].f;
        if(f&&level[v]==level[u]+1){
            f=dfs(v,min(f,maxf-rat),t);
            G[i].f-=f;G[i^1].f+=f;rat+=f;
        }
    }
    if(!rat)level[u]=inf;
    return rat;
}
inline void dinic(){while(bfs(s,t))ans+=dfs(s,inf,t);}
inline int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch==-)f=-1;}while(ch<0||ch>9);
    do{x=x*10+ch-0;ch=getchar();}while(ch>=0&&ch<=9);
    return f*x;
}
int main(){
    s=1;for(int i=0;i<=N;i++)head[i]=-1;
    n=io.xuint();m=io.xuint();x=io.xuint();t=n;int u,v,w,f;
    for(int i=1;i<=m;i++){
        u=io.xuint(),v=io.xuint(),f=io.xuint();
        addedge(u,v,f);
    }
    dinic();
    if(!ans)puts("Orz Ni Jinan Saint Cow!");
    else printf("%d %d\n",ans,x/ans+(x%ans!=0));
    return 0;
}

 

【洛谷P1343】地震逃生