星星之火 @ 2018-01-19 16:46:06
#include<algorithm>
#include<cstdio>
#include<queue>
#include<memory.h>
using namespace std;
#define N 1000005
#define maxx 99999999
int edge_num;
int head[N];
int n,m,s,t;
struct EDGE
{
int to;
int next;
int f=0;
int c;
}edge[N];
int dep[N];
int bfs()
{ queue <int> q;
memset(dep,0,sizeof(dep));
dep[s]=1;
q.push(s);
while (!q.empty())
{
int x=q.front();q.pop();
for (int i=head[x];i;i=edge[i].next)
{
int go=edge[i].to;
if (!dep[go]&&edge[i].f<edge[i].c)
{
dep[go]=dep[x]+1;
q.push(go);
}
}
}
return dep[t];
}
int dfs(int x,int flow)
{
if (x==t) return flow;
int ans=0;
for (int i=head[x];i;i=edge[i].next)
{
if (flow<=ans) break;
int go=edge[i].to;
if (dep[go]==dep[x]+1&&edge[i].c>edge[i].f)
{
int s=dfs(go,min(flow-ans,edge[i].c-edge[i].f));
ans+=s;
edge[i].f+=s;
edge[i^1].f-=s;
}
}
return ans;
}
int dinic()
{
int ans=0;
while (bfs())
{
ans+=dfs(s,maxx);
}
return ans;
}
int main()
{
scanf("%d %d %d %d",&n,&m,&s,&t);
for (int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
edge[++edge_num].next=head[a];edge[edge_num].c=c;edge[edge_num].to=b;head[a]=edge_num;
edge[++edge_num].next=head[b];edge[edge_num].c=0;edge[edge_num].to=a;head[b]=edge_num;
}
int ans=dinic();
printf("%d",ans);
return 0;
}
by 星星之火 @ 2018-04-20 16:19:34
好吧偶然翻到以前的帖子。。。这题我好像已经A了
by 星星之火 @ 2018-04-20 16:20:07
这板子好像有点问题