63分蒟蒻求助
查看原帖
63分蒟蒻求助
119638
xia0ji233楼主2022/3/4 17:12

如题,网络流已经大体全部掌握了,来做一下费用流,有神犇跟我说,费用流跟网络流的区别就是把bfs改成spfa求一条路径最短的增广路,这个路径指的是费用路径。于是我按着自己的思路写出了这样的板子,但是后四个点无情WA,球球帮忙

#include<bits/stdc++.h>
#define maxn 100005 
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair<int,int> P;
struct eee{
	int to;
	int w;
	int d;
	int next;
}edge[maxn];
struct ppp{
	int v;//?????? 
	int edge;//
}pre[maxn];
int s,t,ans,n,m,cnt;
int root[maxn],dis[maxn],inque[maxn],vis[maxn];
priority_queue<P,vector<P>,greater<P>>q;
inline void add(int x,int y,int w,int d){
	edge[++cnt]={y,w,d,root[x]};
	root[x]=cnt;
}

bool spfa(){
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	while(q.size())q.pop();
	dis[s]=0;
	q.push({0,s});
	while(q.size()){
		
		auto p=q.top();
		
		q.pop();
		int u=p.second;
		if(vis[u])continue;
		if(dis[u]!=p.first)continue;
		//printf("%d %d\n",p.first,p.second);
		vis[u]=1;
		for(int i=root[u];i;i=edge[i].next){
			int v=edge[i].to,w=edge[i].d;
            
			if(vis[v]||!edge[i].w)continue;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				pre[v]={u,i};
				q.push({dis[v],v});
			}
			
		}
		
	}
	
	return dis[t]!=inf;
}

void EK(){
	int ans=0,w=0;
	while(spfa()){
		int k=inf;
		int f=dis[t];
		for(int i=t;i!=s;i=pre[i].v){
			k=min(edge[pre[i].edge].w,k);
		}
		for(int i=t;i!=s;i=pre[i].v){
			edge[pre[i].edge].w-=k;
			edge[pre[i].edge^1].w+=k;
		}
		ans+=k;
		w+=k*f;
	}
	cout<<ans<<' '<<w<<endl;
}

void sync(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

signed main(){
	//freopen("P3381_8.in","r",stdin);
	sync();
	cin>>n>>m>>s>>t;
	while(m--){
		int u,v,w,c;
		cin>>u>>v>>w>>c;
		add(u,v,w,c);
		add(v,u,0,c);
	}
	EK();
	
	return 0;
}
2022/3/4 17:12
加载中...