萌新文明刚形成5000年,求助网络流(最小费用最大流)
查看原帖
萌新文明刚形成5000年,求助网络流(最小费用最大流)
387009
wangbinfeng楼主2023/12/22 15:52

代码求调。

//【模板】最小费用最大流 
#include<bits/stdc++.h>
using namespace std;
#if true
#define USE_QUEUE
#endif
#define int long long
const int inf=0x7ffffff;
inline int read(){
	int x=0,f=1;
	char c;
	for(c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-f;
	for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^48);
	return x*f;
}
class edge{
public:
    int to,pri,flw;
    edge*next,*fb;//fb=反边
    edge(int to,edge *next,int flw=1,int pri=1):next(next),to(to),flw(flw),pri(pri){}
};
class node{
public:
	int dis,incf,flw;
	bool vis;
    edge *e,*cur; //cur:当前弧,以便优化使用
    node():e(nullptr),cur(nullptr),dis(inf),vis(false),incf(0){}
    edge *add(int to,int flw=1,int pri=1){return e=new edge(to,e,flw,pri);}
}dat[5009];
//unordered_map<int,node>dat;
#ifdef USE_QUEUE
queue<int> q;
#else 
stack<int> q;
#endif
int n,m,s,t,u,v,w,c,ans,flow,cost;
inline bool spfa(){
	while(!q.empty())q.pop();
	q.push(s),dat[s].dis=0,dat[s].vis=true,dat[s].incf=inf,dat[s].cur=dat[s].e;
	for(int now;!q.empty();){
#ifdef USE_QUEUE
		now=q.front();
#else
		now=q.top();
#endif
		q.pop(),dat[now].vis=false;
		for(edge *p=dat[now].e;p!=nullptr;p=p->next){
			if(p->flw && (dat[p->to].dis>dat[now].dis+p->pri)){
				dat[p->to].dis=dat[now].dis+p->pri;
				dat[p->to].incf=min(dat[p->to].incf,p->flw);
				dat[p->to].cur=p;
				if(!dat[p->to].vis)dat[p->to].vis=true,q.push(p->to);
			}
		}	
	} 
	return dat[t].dis!=inf;
}
inline int dfs(int now,int sum){
	dat[now].vis=true;
	if(now==t)return sum;
	int used=0,tmp; 
	for(edge*p=dat[now].cur;p!=nullptr;p=p->next){
		tmp=dfs(p->to,min(p->flw,sum-used));
		if(p->flw>0&&dat[t].dis==dat[now].dis+p->pri&&(!dat[p->to].vis||t==p->to)&&tmp){\
			p->flw-=tmp,p->fb->flw+=tmp;
			cost+=tmp*p->pri,used+=tmp;
			if(used>=sum)break;
		} 
	} 
	dat[now].vis=false;
	return used;
}
inline void add(int u,int v,int w=1,int c=1){
    dat[u].add(v,w,c),dat[v].add(u,0,-c);
	dat[u].e->fb=dat[v].e,dat[v].e->fb=dat[u].e;
	//注意反边,其边权初值应当为0 
}
inline void dinic(){
	while(spfa()){
		printf("step A done.\n");
		ans+=dfs(s,inf);
		printf("step B done.\n");
	}
}
signed main(){
    n=read(),m=read(),s=read(),t=read();
	for(int i=1;i<=m;i++)u=read(),v=read(),w=read(),c=read(),add(u,v,w,c);
    dinic();
    printf("%lld %lld",flow,cost);
}

使用邻接表存图。

2023/12/22 15:52
加载中...