求调 最大流模板题
  • 板块学术版
  • 楼主KυρωVixen
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/1/16 11:48
  • 上次更新2023/10/24 04:01:53
查看原帖
求调 最大流模板题
765382
KυρωVixen楼主2023/1/16 11:48

代码如下,码风比较怪,求谅解。 洛谷模板55,USACO模板爆零,求调。

#include<bits/stdc++.h>
#define int long long 
#define to e[i].v
using namespace std;
int n,m,s,t,maxf,cnt=1,lst[201],pre[201],flow[201],hd[201];
bool vis[201],f[201][201];
struct Edge{
	int v,nxt,flow;
}e[10003];
void addedge(int u,int v,int w){
	e[++cnt].v=v; e[cnt].nxt=hd[u];
	e[cnt].flow=w; hd[u]=cnt;
}
bool spfa(){
	queue<int>q; q.push(s);
	memset(vis,0,sizeof(vis));
	vis[s]=1; flow[s]=1145141919810;
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int i=hd[u];i;i=e[i].nxt){
			if(e[i].flow<=0) continue;
			if(vis[to]) continue;
			pre[to]=u; lst[to]=i;
			flow[to]=min(flow[u],e[i].flow);
			q.push(to); vis[to]=1;
			if(to==t) return 1;
			
		}
	}
	return 0;
}
void maxflow(){
	while(spfa()){
		int now=t;
		while(now!=s){
			e[lst[now]].flow-=flow[t];
			e[lst[now]+1].flow+=flow[t];
			now=pre[now];
		}
		maxf+=flow[t];
	}
}
signed main(){
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		int t1,t2,t3; cin>>t1>>t2>>t3;
		if(!f[t1][t2]){
			addedge(t1,t2,t3);
			addedge(t2,t1,0);
			f[t1][t2]=cnt;
		}
		else e[cnt-1].flow+=t3;
	}
	maxflow();
	cout<<maxf<<endl;
} 
2023/1/16 11:48
加载中...