2018.08.20 loj#116. 소스가 있고 상하계 최대 흐름 (템플릿)
사실 두 번째 달리기의 최대 흐름은 첫 번째 답이 자동으로 추가된 것이다.
코드:
#include
#define N 100005
#define M 2000010
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int first[N],s,t,ss,tt,n,m,d[N],cnt=-1,m_[N];
struct Node{int v,next,c;}e[M];
inline void add(int u,int v,int c){e[++cnt].v=v,e[cnt].c=c,e[cnt].next=first[u],first[u]=cnt;}
inline bool bfs(){
queue<int>q;
memset(d,-1,sizeof(d));
q.push(s),d[s]=0;
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=first[x];~i;i=e[i].next){
int v=e[i].v;
if(d[v]!=-1||e[i].c<=0)continue;
d[v]=d[x]+1;
if(v==t)return true;
q.push(v);
}
}
return false;
}
inline int dfs(int x,int f){
if(x==t||!f)return f;
int flow=f;
for(int i=first[x];~i;i=e[i].next){
int v=e[i].v;
if(flow&&d[v]==d[x]+1&&e[i].c>0){
int tmp=dfs(v,min(flow,e[i].c));
if(!tmp)d[v]=-1;
e[i].c-=tmp,e[i^1].c+=tmp,flow-=tmp;
}
}
return f-flow;
}
inline bool check(){
for(int i=first[s];~i;i=e[i].next)if(e[i].c>0)return false;
for(int i=first[t];~i;i=e[i].next)if(e[i^1].c>0)return false;
return true;
}
inline int solve(){
int ret=0;
while(bfs())ret+=dfs(s,inf);
return ret;
}
int main(){
memset(first,-1,sizeof(first));
int sum=0;
n=read(),m=read(),ss=read(),tt=read(),s=0,t=n+1;
for(int i=1;i<=m;++i){
int u=read(),v=read(),down=read(),up=read();
m_[u]-=down,m_[v]+=down,add(u,v,up-down),add(v,u,0);
}
for(int i=1;i<=n;++i){
if(m_[i]>0)add(s,i,m_[i]),sum+=m_[i],add(i,s,0);
if(m_[i]<0)add(i,t,-m_[i]),add(t,i,0);
}
add(tt,ss,inf),add(ss,tt,0);
if(solve()!=sum){cout<<"please go home to sleep";return 0;}
first[s]=first[t]=-1;
s=ss,t=tt;
cout<return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Rails Turbolinks를 페이지 단위로 비활성화하는 방법원래 Turobolinks란? Turbolinks는 링크를 생성하는 요소인 a 요소의 클릭을 후크로 하고, 이동한 페이지를 Ajax에서 가져옵니다. 그 후, 취득 페이지의 데이터가 천이 전의 페이지와 동일한 것이 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.