社区讨论

谁来救救初学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 条回复,欢迎继续交流。

正在加载回复...