star_eternal @ 2017-10-20 08:03:01
#include<cstdio>
#include<queue>
#include<cstring>
#define N 10000+10
#define M 300000+10
using namespace std;
struct Arc{
int next,to,cap;
}arc[M<<1];
int head[N],arnum=1;
void add(int from,int to,int cap)
{
arc[++arnum]=(Arc){head[from],to,cap};
head[from]=arnum;
}
void insert(int from,int to,int cap)
{
add(from,to,cap);
add(to,from,0);
}
int n,m;
struct cmp{
int u,h;
cmp(int u=0,int h=0):u(u),h(h){};
inline bool operator < (const cmp & a)const {return h<a.h;}
};
priority_queue<cmp>Q;
int h[N],flow[N],gap[N];
bool push(int u,int v,int i)
{
int minf=min(arc[i].cap,flow[u]);
flow[u]-=minf;flow[v]+=minf;
arc[i].cap-=minf;
arc[i^1].cap+=minf;
}
void Gap(int l,int s,int t)
{
for(int i=1;i<=n;i++)
{
if(i!=s &&i!=t&& l<h[i]&&h[i]<=n)h[i]=n+1;
}
}
int maxflow(int s,int t)
{
while(!Q.empty())Q.pop();
memset(h,0,sizeof(h));memset(flow,0,sizeof(flow));memset(gap,0,sizeof(gap));
h[s]=n;flow[s]=1e9;Q.push(cmp(s,h[s]));
while(!Q.empty())
{
int u=Q.top().u;Q.pop();
if(!flow[u])continue;
for(int i=head[u];i;i=arc[i].next)
{
int v=arc[i].to;
if((u==s||h[u]==h[v]+1)&&push(u,v,i)&&v!=s&&v!=t) Q.push(cmp(v,h[v]));
}
if (u!=s && u!=t && flow[u]){
if (!(--gap[h[u]])) Gap(h[u],s,t);
++gap[++h[u]];
Q.push(cmp(u,h[u]));
}
}
return flow[t];
}
int main()
{
int s,t;
scanf("%d%d%d%d",&n,&m,&s,&t);
int u,v,cap;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&cap);
if(!cap)continue;
insert(u,v,cap);
}
printf("%d\n",maxflow(s,t));
}
by xtxwwwd @ 2018-02-05 14:00:22
滑稽 没有问题