首页 > 代码库 > 【洛谷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】地震逃生
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。