Dusker @ 2019-01-28 20:47:26
#include<bits/stdc++.h>
#define re register
using namespace std;
const int mmax=1e6+10;
const int inf=2147483647;
struct node
{
int from,to,cap;
}edge[mmax];
int tot,first[mmax],m,n,s,t;
int dis[mmax];
inline int Min(const int &x,const int &y) {return x<y?x:y;}
inline void add(int x,int y,int z)
{
edge[++tot].to=y;
edge[tot].cap=z;
edge[tot].from=first[x];
first[x]=tot;
return;
}
inline bool bfs()
{
memset(dis,0,sizeof(dis));
queue<int> q;
dis[s]=1;q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();
for(re int i=first[u];i;i=edge[i].from)
if(!dis[edge[i].to] && edge[i].cap)
dis[edge[i].to]=dis[u]+1,q.push(edge[i].to);
}
return dis[t];
}
int dfs(int cur,int maxf)
{
if(cur == t || !maxf) return maxf;
int flow=0,f;
for(re int i=first[cur];i;i=edge[i].from)
if(dis[edge[i].to] == dis[cur]+1 && (f=dfs(edge[i].to,Min(edge[i].cap,maxf))))
{
edge[i].cap-=f;
edge[i^1].cap+=f;
maxf-=f;
flow+=f;
if(!maxf) break;
}
return flow;
}
inline int dinic()
{
int ans=0;
while(bfs()) ans+=dfs(s,inf);
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>s>>t;
for(re int i=1;i<=m;i++)
{
int x,y,s;
cin>>x>>y>>s;
add(x,y,s);
add(y,x,0);
}
cout<<dinic();
}
by yurzhang @ 2019-01-28 20:51:02
tot初值赋1
by HrlAcc @ 2019-01-28 20:54:14
TSLzwy大佬
by 鸾辂音尘远 @ 2019-01-28 20:54:45
QAQ tql
by RiverFun @ 2019-01-28 20:54:45
@Dusk_Till_Dawn tot = 1
by qushi @ 2019-01-28 20:56:35
刚给我们讲过去你咋就不会拉?
by Dusker @ 2019-01-28 20:57:42
蟹蟹qaq
by Dusker @ 2019-01-28 20:57:58
@qushi 我在梦游 你别管我((
by yurzhang @ 2019-01-28 21:00:57
你这反边全找错了怎么拿的70分。。
by qushi @ 2019-01-28 21:02:43
@Dusk_Till_Dawn 你长那么胖游不起来的
by t162 @ 2019-01-29 11:11:59
@yurzhang 窝反边全找错噎是七十分。。。