Home Article Practice dinic板子

dinic板子

2023-10-15 09:14  views:434  source:yzh_Error404    

#include<bits/stdc++.h>#define int long longusing namespace std;const int MAXN=1e6+5;const
int INF=0x7f7f7f7f;struct node{int to,nxt,flow;}e[MAXN];int head[MAXN],cnt=1;inline void
adde(int x,int y,int f){e[++cnt].to=y;e[cnt].flow=f;e[cnt].nxt=head[x];head[x]=cnt;}inline
void add(int x,int y,int f){adde(x,y,f);adde(y,x,0);}int n,m,s,t;int cur[MAXN],dis[MAXN];
bitset<MAXN>vis;inline bool bfs(){queue<int>q;memset(dis,-1,sizeof dis);q.push(s);dis[s]=0
;cur[s]=head[s];while(!q.empty()){int x=q.front();q.pop();for(register int i=head[x];i;i=e
[i].nxt){int y=e[i].to,f=e[i].flow;if(dis[y]==-1&&f){dis[y]=dis[x]+1;cur[y]=head[y];if(y==
t)return true;q.push(y);}}}return false;}inline int dfs(int x,int lim){if(x==t)return lim;
int f=0;for(register int i=cur[x];i&&f<lim;i=e[i].nxt){int y=e[i].to;cur[x]=i;if(dis[y]==d
is[x]+1&&e[i].flow){int w=dfs(y,min(e[i].flow,lim-f));if(!w)dis[y]=-1;e[i].flow-=w;e[i^1].
flow+=w;f+=w;}}return f;}inline int dinic(){int ans=0,f;while(bfs())while(f=dfs(s,INF))ans
+=f;return ans;}signed main(){scanf("%lld%lld%lld%lld",&n,&m,&s,&t);for(register int i=1;i
<=m;i++){int x,y,f;scanf("%lld%lld%lld",&x,&y,&f);add(x,y,f);}printf("%lld",dinic());retur
n 0;}



Disclaimer: The above articles are added by users themselves and are only for typing and communication purposes. They do not represent the views of this website, and this website does not assume any legal responsibility. This statement is hereby made! If there is any infringement of your rights, please contact us promptly to delete it.

字符:    改为:
去打字就可以设置个性皮肤啦!(O ^ ~ ^ O)