Benzenesir @ 2023-05-04 14:37:54
#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#define ll long long
#define fp(a,b,c) for(ll a=b;a<=c;a++)
#include <tuple>
#define fd(a,b,c) for(ll a=b;a>=c;a--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fr first
#define sd second
#define mod 1000000007
#define inf 0x3f3f3f3f
//#define int long long
using namespace std;
const int maxN=100+10;
struct node{int to,flow,nex;};
struct liu{
int idx=1;
int head[maxN*4],cur[maxN*4],dep[maxN*4],in[maxN*4],s,t,n,m;//起点,终点,点数,边数
node g[maxN*100];
int vis[maxN];
inline void add(int u,int v,int flow){
g[++idx]={v,flow,head[u]};
head[u]=idx;
g[++idx]={u,0,head[v]};
head[v]=idx;
}
bool bfs(){
queue<int>q;
memset(in,0,sizeof(in));
memset(dep,0x3f,sizeof(dep));
q.push(s);
dep[s]=1;
in[s]=1;
while(!q.empty()){
int temp=q.front();
q.pop();
for(int i=head[temp];i;i=g[i].nex)
if(!g[i].flow) continue;
else if(dep[g[i].to]>dep[temp]+1){
dep[g[i].to]=dep[temp]+1;
if(!in[g[i].to])
in[g[i].to]=1,q.push(g[i].to);
}
}
return dep[t]!=0x3f3f3f3f;
}
inline int dfs(int now,int cap){
if(now==t)return cap;
int p=cap;
for(int &i=cur[now];i;i=g[i].nex){
if(!p) break;
if(!g[i].flow&&dep[g[i].to]!=dep[now]+1) continue;
int tp=dfs(g[i].to,min(p,g[i].flow));
if(tp) g[i].flow-=tp,g[i^1].flow+=tp,p-=tp;
else dep[g[i].to]=-1;
}
return cap-p;
}
inline int dinic(){
int np=0,mf=0;
while(bfs()){
fp(i,1,n) cur[i]=head[i];
while(np=dfs(s,inf)) mf+=np;
}return mf;
}
inline void clear(){
memset(in,0,sizeof(in));
memset(dep,0,sizeof(dep));
memset(cur,0,sizeof(cur));
memset(head,0,sizeof(head));
idx=1;
s=0,t=0,n=0,m=0;
}
}mf;//求最大独立集
signed main(){
cin >> mf.n >> mf.m >> mf.s >> mf.t;
int u,v,w;
for(int i=1;i<=mf.m;++i){
cin >> u >> v >> w;
mf.add(u,v,w);
}
// for(int i=1;i<=n;++i)
// add(i,i+n,1);
// for(int i=1;i<=m;++i){
// cin >> u >> v;
// add(u+n,v,inf),add(v+n,u,inf);
// }
// s+=n;
//cout << mf.idx << endl;
cout <<mf.dinic() << endl;;
return 0;
}
结构体里的代码是之前的板子,应该没有较大的问题
by SpeedStar @ 2023-05-04 15:00:04
@Benzenesir 我猜是你的dfs写炸了
by Benzenesir @ 2023-05-04 15:14:47
@寒烟冷浅暮殇 fix,thx