FF_pigeon @ 2023-07-11 19:15:47
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int n, m, s, t;
const int N = 205;
const int M = 5e3+100;
struct Edge
{
int to, nxt;
ll flow;
}e[M*2];
int head[N], dis[N], cur[N], ecnt = 1;
void addedge( int u , int v , int fl )
{
e[++ecnt]=(Edge){v,head[u],fl};head[u] = ecnt;
e[++ecnt]=(Edge){u,head[v],0};head[v] = ecnt;
}
bool BFS()
{
memset(dis,0x3f,sizeof(dis));
dis[s] = 0;
queue<int> q;
q.push(s);
while( !q.empty() )
{
int u = q.front();
q.pop();
for( int i = head[u] ; i ; i = e[i].nxt )
{
if( e[i].flow != 0 && dis[e[i].to] == INF)
{
dis[e[i].to] = dis[u]+1;
q.push(e[i].to);
}
}
}
return dis[t] != INF;
}
ll DFS( int u , ll a )
{
if( u == t || a == 0 ) return a;
ll ret = 0;
for( int &i = cur[i] ; i ; i = e[i].nxt )
{
if( e[i].flow == 0 || dis[e[i].to] != dis[u]+1 )continue;
int f = DFS(e[i].to,min(a,e[i].flow));
if( f )
{
ret += f;
e[i].flow -= f;
e[i^1].flow += f;
a -= f;
if( a == 0 ) return ret;
}
}
}
ll Dinic( int S1 , int T1 )
{
s = S1;
t = T1;
ll ret = 0;
while( BFS() )
{
memcpy(cur,head,sizeof(cur));
ret += DFS(s,INF);
}
return ret;
}
int main()
{
memset(head,0,sizeof(head));
cin >> n >> m >> s >> t;
int a, b, c;
for( int i = 1 ; i <= m ; ++i )
{
cin >> a >> b >> c;
addedge(a,b,c);
}
ll ans = Dinic(s,t);
cout << ans << endl;
return 0;
}
不想多言
by wrkwrkwrk @ 2023-07-11 19:25:23
for( int &i = cur[i] ; i ; i = e[i].nxt )//cur[i]的i哪里来的
应写成
for( int &i = cur[u] ; i ; i = e[i].nxt )
在DFS函数末尾加上return ret;
另外,建议在本地编译时加-Wall
。
by Aleph_Drawer @ 2023-07-11 19:27:46
两个都会报错捏()
by FF_pigeon @ 2023-07-11 19:56:26
谢谢大佬~~ (滑跪) ~~ 已AC