BCZSX @ 2019-04-16 13:39:34
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#define MAXN 10100
#define MAXM 101000
#define INF 0x3f3f3f3f
struct node
{
int v,w,next;
}edge[MAXM];
queue<int> que;
int n,m,s,t,ans,cnt,u,v,w;
int head[MAXM],dis[MAXN];
void add_edge(int u,int v,int w)
{
edge[++ cnt].next = head[u];
edge[cnt].v = v;
edge[cnt].w = w;
head[u] = cnt;
}
bool bfs()
{
memset(dis,- 1,sizeof(dis));
que.push(s);
dis[s] = 0;
while (! que.empty())
{
int u = que.front();
que.pop();
for (int i = head[u] ; i != - 1 ; i = edge[i].next)
{
int v = edge[i].v;
if (dis[v] == - 1 && edge[i].w > 0)
{
dis[v] = dis[u] + 1;
que.push(v);
}
}
}
return dis[t] != - 1;
}
int dfs(int u,int exp)
{
if (u == t) return exp;
int flow = 0,tmp;
for (int i = head[u] ; i != - 1 ; i = edge[i].next)
{
int v = edge[i].v;
if (dis[v] == dis[u] + 1 && edge[i].w > 0)
{
tmp = dfs(v,min(edge[i].w,exp));
if (! tmp) continue;
exp -= tmp;
flow += tmp;
edge[i].w -= tmp;
edge[i ^ 1].w += tmp;
if (! exp) break;
}
}
return flow;
}
int main()
{
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i = 1 ; i <= m ; ++ i)
{
scanf("%d%d%d", &u, &v, &w);
add_edge(u,v,w);
add_edge(v,u,0);
}
while (bfs()) ans += dfs(s,INF);
printf("%d", ans);
return 0;
}
by huhao @ 2019-04-16 13:55:00
@BCZSX cnt
初始不应该是1
?
by BCZSX @ 2019-04-16 13:56:42
@huhao 为什么呀?QAQ
by huhao @ 2019-04-16 13:59:06
@BCZSX
你用^1
来找对应的,从2
开始编号才对应得上啊
by BCZSX @ 2019-04-16 14:01:20
@huhao 改完后代码还是死循环……
by hyfhaha @ 2019-04-16 14:02:38
head 清-1
by hyfhaha @ 2019-04-16 14:03:22
@BCZSX head 清-1
by BCZSX @ 2019-04-16 14:05:14
终于改好了,谢谢两位大佬@huhao@hyfhaha