找增广路应该是没问题的,可能是流量算错了,但本蒟蒻找不出来TT
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 550000;
const int INF = 2005020600;
int n , m , s , t;
bool flag[3000][3000] , vis[N];
int head[N] , to[N] , ne[N] , id = 1;
int pre[N];
long long ans , dis[N] , w[N];
void add(int x , int y , long long z)
{
to[++ id] = y;
ne[id] = head[x];
head[x] = id;
w[id] = z;
to[++ id] = x;
ne[id] = head[y];
head[y] = id;
}
int bfs()
{
for(int i = 1 ; i <= n ; i ++)
{
vis[i] = 0;
}
queue<int> q;
q.push(s);
vis[s] = 1;
dis[s] = INF;
while(!q.empty())
{
int x = q.front();
q.pop();
for(int i = head[x] ; i ; i = ne[i])
{
if(w[i] == 0)
continue;
int v = to[i];
if(vis[v] == 1)
continue;
dis[v] = min(dis[x] , w[i]);
//cout << v << ' ' << dis[v] << endl;
pre[v] = i;
q.push(v);
vis[v] = 1;
if(v == t)
return 1;
}
}
return 0;
}
void update()
{
int x = t;
while(x != s)
{
int v = pre[x];
w[v] -= dis[t];
w[v ^ 1] += dis[t];
x = to[v ^ 1];
}
//cout << dis[t] << endl;
/*
15
38
19
*/
ans += dis[t];
}
signed main()
{
scanf("%lld%lld%lld%lld" , &n , &m , &s , &t);
for(int i = 1 ; i <= m ; i ++)
{
int u , v ;
long long W;
scanf("%lld%lld%lld" , &u , &v , &W);
if(flag[u][v] == 0)
{
add(u , v , W);
//add(v , u , W);
flag[u][v] = id;
}
else
{
w[flag[u][v] - 1] += W;
}
}
//int ttt = 0;
while(bfs())
{
update();
//ttt++;
}
//cout << ttt << endl;
printf("%lld" , ans);
return 0;
}