Obviathy @ 2023-02-16 17:56:17
#include<bits/stdc++.h>
# define ll long long
using namespace std;
const int N = 1e4,inf = 1023021618;
int n,t,m,s;
struct edge{
int u,v,nxt;
ll w;
}e[N];
int tot=-1;
int h[N],cur[N];
ll maxflorr;
int d[N];
inline void add(int u,int v,int w){
//正
e[++tot].u = u;
e[tot].v = v;
e[tot].w = w;
e[tot].nxt = h[u];
h[u] = tot;
//反
e[++tot].u = v;
e[tot].v = u;
e[tot].w = 0;
e[tot].nxt = h[v];
h[v] = tot;
}
inline bool bfs(){
for(int i = 1;i <= n;i ++)d[i] = -1;
queue<int>q;
q.push(s);
// cur[s] = h[s];
d[s] = 0;
while(!q.empty()){
int u = q.front();
q.pop();
for(int i = h[u];i>-1;i = e[i].nxt){
int v = e[i].v;
if(e[i].w > 0 && d[v] == -1){
q.push(v);
d[v] = d[u] + 1;
//cur[v] = h[v];
if(v == t)return 1;
}
}
}
return 0;
}
inline ll dfs(int u,ll flow){
if(u == t||flow==0)return flow;
ll f,res = 0;
for(int i = cur[u];i!=-1;i = e[i].nxt){
cur[u] = i;
int v = e[i].v;
if( d[v] == d[u] + 1 && (f = dfs(v,min(flow,e[i].w)))){
e[i].w -= f;
e[i^1].w += f;
res += f;
flow -= f;
if(flow==0)return res;
}
}
return res;
}
int main(){
cin.tie(0);
cout.tie(0);
cin >> n >> m >> s >> t;
for(int i = 1;i <= m;i ++){
int u,v,w;
cin >> u >> v >> w;
add(u,v,w);
}
while(bfs()){
for(int i = 1;i <= n;i ++)cur[i] = h[i];
maxflorr += dfs(s,inf);
}
cout << maxflorr << endl;
return 0;
}
by Obviathy @ 2023-02-16 17:56:39
dinic
by Alexandra @ 2023-02-16 18:04:08
memset一下h数组
by 小熙熙 @ 2023-02-16 18:04:27
此贴已完结,本人已过
by Deuteron @ 2023-02-16 18:06:17
你们太巨了/bx
by 小熙熙 @ 2023-02-16 18:08:22
@小可爱萌萌哒 你在哪?现在
by 小熙熙 @ 2023-02-16 18:08:49
@小可爱萌萌哒 在本部?
by Obviathy @ 2023-02-16 19:06:58
结案了
by 此间的少年fu @ 2023-02-16 20:01:25
萌新刚学OI???
by 此间的少年fu @ 2023-02-16 20:01:47
yxy好谦虚~
by _Extroversion @ 2023-02-17 15:30:37
一般要说MnZn刚学OI1秒钟