社区讨论
谁来救救初学OI的萌新啊。。
P3376【模板】网络最大流参与者 7已保存回复 15
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 15 条
- 当前快照
- 1 份
- 快照标识符
- @mi6xys9s
- 此快照首次捕获于
- 2025/11/20 12:38 4 个月前
- 此快照最后确认于
- 2025/11/20 15:24 4 个月前
RT,实在找不出问题了。。
CPP#include<bits/stdc++.h>
#define gc getchar
const int MAXN=10010;
const int MAXM=100010;
const int INF=0x7f7f7f7f;
using namespace std;
int n,m,i,j,x,y,z,cnt=1,Beg,End,ans;
struct Pre{int side,pre;};
Pre pre[MAXM];
int head[MAXM];
struct Edge{int to,val,nxt;};
Edge g[MAXM];
bool vis[MAXN];
void addEdge(int u,int v,int val){
g[++cnt].to=v;
g[cnt].val=val;
g[cnt].nxt=head[u];
head[u]=cnt;
}
struct io{
int read(){
int x=0;char c;
for(c=gc();!isdigit(c);c=gc()) ;
for(;isdigit(c);c=gc()) x=x*10+c-48;
return x;
}
}Fio;
#define read Fio.read
queue<int>q;
bool bfs(){
memset(pre,0,sizeof(pre));
memset(vis,0,sizeof(vis));
vis[Beg]=1;q.push(Beg);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=g[i].nxt){
int to=g[i].to;
if(vis[to]||g[i].val==0) continue;
//cout << to << endl;
vis[to]=1;
pre[to].side=i;
pre[to].pre=u;
if(to==End) return 1;
q.push(to);
//while(!q.empty()) q.pop();
}
}
//cout << 1 << endl;
return 0;
}
int EK(){
int ans=0;
while(bfs()){
int i,j;
int Min=INF;
for(i=End;i!=Beg;i=pre[i].pre)
Min=min(Min,g[pre[i].side].val);
for(i=End;i!=Beg;i=pre[i].pre){
g[pre[i].side].val-=Min;
g[pre[i].side^1].val+=Min;
}
ans+=Min;
}
return ans;
}
int main(){
n=read();m=read();Beg=read();End=read();
for(i=1;i<=m;i++){
int u=read(); int v=read(); int l=read();
addEdge(u,v,l);
addEdge(v,u,0);
}
ans=EK();
printf("%d\n",ans);
}
回复
共 15 条回复,欢迎继续交流。
正在加载回复...