63 mle求助
查看原帖
63 mle求助
252549
Iwara楼主2024/4/17 18:24

RT

#include<bits/stdc++.h>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const ll MAXN=5e3+5,MAXM=1e5+5;
int n,m,s,t,x,y,z,c;
struct MF{
	struct edge{
		int u,v,w,nxt,flow,cost;
	}e[MAXM];
	int head[MAXN],edge_num;
	int max_flow,val;
	int deep[MAXN],cur[MAXN];
	bool vis[MAXN];
	void init(){
		memset(head,0,sizeof(head));
		edge_num=1;
		return;
	}
	void add_edge(int From,int To,int Len,int C){
		edge_num++;
		e[edge_num]=(edge){From,To,Len,head[From],0,C};
		head[From]=edge_num;
		edge_num++;
		e[edge_num]=(edge){To,From,0,head[To],0,-C};
		head[To]=edge_num;
		return;
	}
	bool bfs(){
//		cout<<"!!!!!!!!!!\n";
		queue<ll> q;
		memset(deep,0,sizeof(deep));
		memset(vis,0,sizeof(vis));
		deep[s]=1;
		q.push(s);
		while(q.size()){
			ll now=q.front();
			q.pop();
			if(vis[now])continue;
			vis[now]=1;
			for(ll i=head[now];i;i=e[i].nxt){
				if(!deep[e[i].v]&&e[i].w>e[i].flow){
					deep[e[i].v]=deep[now]+e[i].cost;
					q.push(e[i].v);
				}
			}
//			cout<<"!\n";
		}
		return vis[t];
	}
	int dfs(int now,int flow_l){
		if(now==t||flow_l==0)return flow_l;
		int now_flow=0,d;
		for(int &i=cur[now];i;i=e[i].nxt){
			if(deep[e[i].v]==deep[now]+e[i].cost&&(d=dfs(e[i].v,min(flow_l-now_flow,e[i].w-e[i].flow)))){
				now_flow+=d;
				e[i].flow+=d;
				e[i^1].flow-=d;
				val+=d*e[i].cost;
				if(now_flow==flow_l)return now_flow;
			}
		}
		return now_flow;
	}
	void dinic(){
		while(bfs()){
//			cout<<"?\n";
			memcpy(cur,head,sizeof(head));
			max_flow+=dfs(s,INT_MAX);
		}
		return;
	}
}mf;
int main(){
	cin>>n>>m>>s>>t;
	mf.init();
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z>>c;
		mf.add_edge(x,y,z,c);
	}
//	cout<<"?????????????????\n";
	mf.dinic();
	cout<<mf.max_flow<<" "<<mf.val;
	return 0;
}
2024/4/17 18:24
加载中...