最小费用最大流求助(邻接表dij算法),无法通过样例
查看原帖
最小费用最大流求助(邻接表dij算法),无法通过样例
384007
封禁用户楼主2021/12/5 20:36

萌新初学oi,求助网络流, 由于不会spfa,就用了dij算法,照着题解打(模板题应该没问题吧),但过不去样例

我的代码:

#include<bits/stdc++.h>
using namespace std;
const long long inf=0x7fffffffffffffff;
inline int read(){
    char c;
    int ret=0;
    for(c=getchar();c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())ret=ret*10+c-'0';
    return ret;
}
inline void write(int x) {
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}
class line{
public:
	long long u,v,w,c;
	line *next;
	line(int u=0,int v=0,int w=0,int c=0,line *next=NULL):
		u(u),v(v),w(w),c(c),next(next){}
}*L[5009];
class node{
public:
	line *edge;
	void newline(int u,int v,int w,int c){edge=new line(u,v,w,c,edge);}
}dat[5009];
long long n,m,s,t,u,v,w,c,mincost,maxflow,dis[5009],flow[5009],from[5009],last,h[5009];
bool vis[5009];
bool dij(long long start,long long end){
	line *p;
	long long minn,mn;
	last=start;
	for(int i=1;i<=n;i++){
		dis[i]=inf;
		flow[i]=inf;
		from[i]=vis[i]=0;
		L[i]=NULL;
	}
	dis[start]=0;
	vis[start]=true;
	flow[start]=inf;
	for(p=dat[last].edge;p!=NULL;p=p->next){
		if(p->w>0&&vis[p->v]==false&&dis[p->v]>dis[last]+p->w+h[last]-h[p->v]){
			dis[p->v]=dis[last]+p->c+h[last]-h[p->v];
			flow[p->v]=min(p->w,flow[last]);
			from[p->v]=last;
			L[p->v]=p;
		}
	}
	for(int i=2;i<=n;i++){
		minn=inf;
		mn=-1;
		for(int i=1;i<=n;i++)
			if(vis[i]==false&&minn>dis[i]){
				minn=dis[i];mn=i;
			}
		if(mn==-1)return false;
		vis[mn]=true;
		if(mn==end)return true;
		for(p=dat[last].edge;p!=NULL;p=p->next){
			if(p->w>0&&vis[p->v]==false&&dis[p->v]>dis[last]+p->w+h[last]-h[p->v]){
				dis[p->v]=dis[last]+p->c+h[last]-h[p->v];
				flow[p->v]=min(p->w,flow[last]);
				from[p->v]=last;
				L[p->v]=p;
			}
		}
		last=mn;
	}
	return dis[end]!=inf;
}
line *get(line *p){
	for(line*q=dat[p->v].edge;q!=NULL;q=q->next)if(q->v==p->u)return q;
	return NULL;
}
int main(){
	freopen("read.txt","r",stdin);
	n=read();m=read();s=read();t=read();
	for(int i=1;i<=m;i++){
		u=read();v=read();w=read();c=read();
		dat[u].newline(u,v,w,c);dat[v].newline(v,u,0,-c);
	}
	while(dij(s,t)){
		mincost+=flow[t]*(dis[t]-h[s]+h[t]);
		maxflow+=flow[t];
		for(int i=t;i!=s;i=from[i]){
			L[i]->w-=flow[t];
			get(L[i])->w+=flow[t];
		}
		for(int i=1;i<=n;i++)
			if(dis[i]!=inf)h[i]+=dis[i];
	}
	write(mincost);putchar(' ');write(maxflow);
}

样例输出:

60 20
2021/12/5 20:36
加载中...