社区讨论
最大流板子第十个点WA了,在线求调
P3376【模板】网络最大流参与者 5已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @lqq0yfrt
- 此快照首次捕获于
- 2023/12/29 10:38 2 年前
- 此快照最后确认于
- 2023/12/29 17:51 2 年前
rt,可能马蜂有那么一点点点清奇新,轻喷qwq
CPP#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;
}
回复
共 7 条回复,欢迎继续交流。
正在加载回复...