EK+spfa,63分蒟蒻求调
查看原帖
EK+spfa,63分蒟蒻求调
540994
lichengyun楼主2022/5/11 22:27
#include <bits/stdc++.h>
#define int long long
using namespace std;
int head[50005],n,m,s,t,cnt=2,pre[50005],no[50005],dis[50005];
struct edge{
	int u,v,cap,cost,nxt;
}g[1000005];
inline void addedge(int u,int v,int cap,int cost){
	g[cnt].cap=cap;g[cnt].u=u;g[cnt].v=v;g[cnt].cost=cost;
	g[cnt].nxt=head[u];head[u]=cnt++;
}
inline int read(){
	char ch;int ans;
	ch=ans=0;
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=ans*10+(ch-'0'),ch=getchar();
	return ans;
}

int bfs(int& cost){
	for(int i=1;i<=n;i++)pre[i]=no[i]=0,dis[i]=INT_MAX;
	dis[s]=0;
	queue<int>node;
	node.push(s);
	while(!node.empty()){
		int top=node.front();node.pop();
		if(top==t)break;
		for(int i=head[top];i;i=g[i].nxt){
			if((dis[g[i].v]>dis[top]+g[i].cost)&&g[i].cap)
				pre[g[i].v]=top,no[g[i].v]=i,node.push(g[i].v),dis[g[i].v]=dis[top]+g[i].cost;//spfa
		}
	}
	if((!pre[t])||(!dis[t]))return 0;
	int ans=INT_MAX;//维护边权、最大流
	for(int i=t;i!=s;i=pre[i]){
		ans=min(ans,g[no[i]].cap);
	}
	for(int i=t;i!=s;i=pre[i]){
		g[no[i]].cap-=ans;
		g[no[i]^1].cap+=ans;
	}
	cost=ans*dis[t];
	return ans;
}


int EK(int &cost){
	int ans=0,tmp,tmp2;//Edmons-Karp
	while(tmp=bfs(tmp2))ans+=tmp,cost+=tmp2;
	return ans;
}

signed main(){
	n=read(),m=read(),s=read(),t=read();
	for(int i=0;i<m;i++){
		int u=read(),v=read(),w=read(),c=read();
		addedge(u,v,w,c);//edge
		addedge(v,u,0,c);//reverse
	}
	int cost=0, ans=EK(cost);
	printf("%lld %lld",ans,cost);
	return 0;
}

wa了后四个点

2022/5/11 22:27
加载中...