lindongli2004 @ 2018-12-31 19:49:00
代码如下
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long//int都成了long long
using namespace std;
const int M=2002019,N=200017,inf=1e15+7;//如此大的范围
int ans,n,m,s,t,dep[N],stk[N];
struct Edge{
int from,to,next,data;
}e[M<<1];int v[N],tot;
void add_real(int x,int y,int z)
{
e[tot].from=x;
e[tot].to=y;
e[tot].data=z;
e[tot].next=v[x];
v[x]=tot;++tot;
}
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
bool bfs()
{
for(int i=1;i<=n;i++)dep[i]=-1;
dep[s]=0;
int head(1),tail(0);
stk[++tail]=s;
while(head<=tail)
{
int w=stk[head++];
for(int p=v[w];p!=-1;p=e[p].next)
{
int kp=e[p].to;
if(dep[kp]==-1 && e[p].data>0)
{
dep[kp]=dep[w]+1;
stk[++tail]=kp;
}
}
}
if(dep[t]<0)return false;
return true;
}
int dfs(int x,int exp)
{
if(x==t)return exp;
int tmp=0,flow=0;
for(int p=v[x];p!=-1;p=e[p].next)
{
int kp=e[p].to;
if(dep[kp]==dep[x]+1 && e[p].data>0)
{
tmp=dfs(kp,min(exp,e[p].data));
if(!tmp)continue;
exp-=tmp;
flow+=tmp;
e[p].data-=tmp;
e[p^1].data+=tmp;
if(!exp)break;
}
}
return flow;
}
#undef int
int main()
{
n=read();m=read();s=read();t=read();
for(int i=0;i<=m*3;i++)e[i].next=v[i]=-1;
for(int i=1;i<=m;i++){
long long a=read(),b=read(),c=read();
add_real(a,b,c);add_real(b,a,0);
}
while(bfs())
ans+=dfs(s,inf);
cout<<ans<<endl;
return 0;
}
我想知道:why?
by NULL0x7f @ 2019-01-22 13:09:04
同问