##T4个点,求助……
查看原帖
##T4个点,求助……
353316
Crazy_S_K楼主2021/2/18 14:56
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
#define maxn 50000+7
struct edge{
	int to,next,lim,cos;
}e[maxn];
int tail=0,head[maxn];
inline void add(int from,int to,int limit,int cos){
	tail++;
	e[tail].to=to;
	e[tail].next=head[from];
	head[from]=tail;
	e[tail].cos=cos;
	e[tail].lim=limit;
	tail++;
	e[tail].to=from;
	e[tail].next=head[to];
	e[tail].lim=0;
	e[tail].cos=-cos;
	head[to]=tail;
}
queue<int>q;
int vis[maxn],dis[maxn],pre[maxn],flow[maxn],last[maxn];
inline bool SPFA(){
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	vis[s]=1;
//	memset(pre,-1,sizeof(pre));
//	memset(flow,0,sizeof(flow));
	flow[s]=0x3f3f3f3f;
//	while(!q.empty())q.pop();
	dis[s]=0;q.push(s);
	while(!q.empty()){
		int nyq=q.front();
		q.pop();vis[nyq]=0;
		for(register int i=head[nyq];i!=-1;i=e[i].next){
			int xsc=e[i].to;
			if(e[i].lim&&e[i].cos+dis[nyq]<dis[xsc]){
				dis[xsc]=dis[nyq]+e[i].cos;
				pre[xsc]=nyq;
				last[xsc]=i;
				flow[xsc]=min(flow[nyq],e[i].lim);
				if(!vis[xsc]){
					vis[xsc]=1;
					q.push(xsc);
				}
			}
		}
	}
	return dis[t]!=0x3f3f3f3f;
}
inline void Max_current(){
	int ans1=0,ans2=0;
	while(SPFA()){
		int xsc;
		xsc=t;
		while(xsc!=s){
			e[last[xsc]].lim-=flow[t];
			e[last[xsc]^1].lim+=flow[t];
			xsc=pre[xsc];
		}
		ans1+=flow[t];
		ans2+=flow[t]*dis[t];
	}
	cout<<ans1<<' '<<ans2<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	memset(head,-1,sizeof(head));
	cin>>n>>m>>s>>t;
	for(register int i=1;i<=m;i++){
		int q,w,e,r;
		cin>>q>>w>>e>>r;
		if(q==w)continue;
		add(q,w,e,r);
	}
	Max_current();
	return 0;
}
2021/2/18 14:56
加载中...