P_VICVIC_R @ 2023-12-29 10:37:12
rt,可能马蜂有那么一点点点清奇新,轻喷qwq
#include<bits/stdc++.h>
#define f1 first
#define f2 second
#define int long long
#define V_(T) vector<T>
#define P_(T1,T2) pair<T1,T2>
using namespace std;
static const int ni=2050;
static const int N=1000000;
static const int inf=0x7fffffff;
static const int INF=0x7f7f7f7f7f7f7f;
namespace Graph{
class graph{
public:
struct Edge{
int nxt;
int to;
int val;
};
int tot=1;
int n_,m_;
V_(int) sign;
V_(Edge) e;
graph(int _n_=0,int _m_=0)
:n_(_n_),m_(_m_)
{
for(int i=0;i<=(m_<<1);i++){sign.push_back(0);e.push_back({0,0,0});}
}
~graph(){}
void add(int fro,int to,int val)
{
tot++;
e[tot].to=to;
e[tot].val=val;
e[tot].nxt=sign[fro];
sign[fro]=tot;
}
void add(int fro,int to)
{
tot++;
e[tot].to=to;
e[tot].nxt=sign[fro];
sign[fro]=tot;
}
};
static const graph Empty;
class Dinic
{
private:
Graph::graph GL;
V_(int) cvrg;
V_(int) ncur;
int S_,T_;
#define sign(x) GL.sign[x]
#define to(x) GL.e[x].to
#define vl(x) GL.e[x].val
#define nx(x) GL.e[x].nxt
inline bool bfs()
{
cvrg=V_(int) (GL.n_+1,0);
queue<int> ql;
ql.push(S_);
cvrg[S_]=1;
while(!ql.empty()){
int rt=ql.front();
ql.pop();
for(int i=sign(rt);i;i=nx(i)){
int to=to(i);
if(!cvrg[to]&&vl(i)){
cvrg[to]=cvrg[rt]+1;
ql.push(to);
if(to==T_){return true;}
}
}
}
return false;
}
inline int dfs(int rt,int flo)
{
if(rt==T_){
return flo;
}
int tmp_sum=flo;
for(int i=ncur[rt];i&&tmp_sum;i=nx(i)){
ncur[rt]=i;
int to=to(i);
if(cvrg[to]==cvrg[rt]+1&&vl(i)){
int fl=dfs(to,min(flo,vl(i)));
if(!fl){
cvrg[to]=0;
}
vl(i)-=fl;
vl(i^1)+=fl;
tmp_sum-=fl;
}
}
return flo-tmp_sum;
}
#undef sign
#undef to
#undef vl
#undef nx
public:
int maxinum_flow;
Dinic(class Graph::graph G_= Empty,int S=1,int T=1)
:GL(G_),S_(S),T_(T)
{
maxinum_flow=0;
while(bfs()){
// bfs();
ncur=GL.sign;
while(int tmp=dfs(S,INF))
{
maxinum_flow+=tmp;
}
}
}
~Dinic(){}
};
}
using namespace Graph;
int n,m;
int S,T;
signed main()
{
std::ios::sync_with_stdio(false);
std::cout.tie(0);
std::cin.tie(0);
cin>>n>>m>>S>>T;
graph G(n+n,m+m);
for(int i=0;i<m;i++){
int x,y,z;
cin>>x>>y>>z;
G.add(x,y,z);
G.add(y,x,0);
}
Dinic ans(G,S,T);
cout<<ans.maxinum_flow;
return 0;
}
by _anll_ @ 2023-12-29 10:38:21
看不懂,但先膜为敬awa
by P_VICVIC_R @ 2023-12-29 10:39:17
额额是用类写的,可能有一点点点怪吧awq
by DeusExMachina @ 2023-12-29 10:59:46
https://www.luogu.com.cn/paste/cc9on0aj
给你格式化了一下代码
by Union_of_Britain @ 2023-12-29 10:59:51
臭
by _qingshu_ @ 2023-12-29 11:06:33
@PAVIC_victor
把第 91 行的
int fl=dfs(to,min(flo,vl(i)));
改成
int fl=dfs(to,min(tmp_sum,vl(i)));
就好了,你流量没有实时减少
by P_VICVIC_R @ 2023-12-29 11:07:46
%%% @qingshu %%%
by _anll_ @ 2023-12-29 11:07:54
!惊现情书哥哥!先膜为敬
by carefree_Zhuang @ 2024-01-29 16:41:25
%%%