这题 dijkstra+dinic多路增广 为何跑的这么慢?
查看原帖
这题 dijkstra+dinic多路增广 为何跑的这么慢?
238408
vectorwyxSD省选加油楼主2022/1/5 21:21

RT,是我写假了吗 QAQ

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define sml(x,y) (x=min(x,y))
#define big(x,y) (x=max(x,y))
#define ll long long
#define ull unsigned long long
#define db double
#define fo(i,x,y) for(int i=x;i<=y;++i)
#define go(i,x,y) for(int i=x;i>=y;--i)
using namespace std;
inline int read(){int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){if(ch=='-') fh=-1; ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*fh;}
inline void out(int *a,int l,int r){fo(i,l,r) cout<<*(a+i)<<' ';puts("");}

const int N=2e5+5;
const ll inf=1e18;
int dlt[N],n,m,ti,s,t,ins[N];
struct Edge{
	int to,next,r,val;
}e[N];
int head[N],tot=1,now[N],vis[N];
ll h[N],dis[N],ans;
void connect(int x,int y,int r,int c){
	e[++tot]=(Edge){y,head[x],r,c};
	head[x]=tot;
}

void spfa(){
	fo(i,1,n) h[i]=inf;
	queue<int> q;q.push(0);
	while(!q.empty()){
		int x=q.front();q.pop();
		ins[x]=1;
		for(int i=head[x];i;i=e[i].next){
			int p=e[i].to;
			if(h[p]>h[x]+e[i].val){
				h[p]=h[x]+e[i].val;
				if(!ins[p]) q.push(p),ins[p]=1;
			}
		}
	}
}

bool dij(){
	++ti;
	priority_queue<pair<ll,int> > q;
	fo(i,1,n) dis[i]=inf;dis[s]=0;q.push(mk(0,s));
	while(!q.empty()){
		while(!q.empty()&&dlt[q.top().se]==ti) q.pop();
		if(q.empty()) break;
		int x=q.top().se;q.pop();
		now[x]=head[x];
		for(int i=head[x];i;i=e[i].next)if(e[i].r){
			int p=e[i].to;
			if(dis[p]>dis[x]+e[i].val){
				dis[p]=dis[x]+e[i].val;
				q.push(mk(-dis[p],p));
			}
		}
	}
	return dis[t]<inf;
}

ll dfs(int x,ll lim){
	//printf("dfs(%d %lld)\n",x,lim);
	if(x==t) return lim;
	vis[x]=ti;ll ret=0;
	for(int i=now[x];i;i=e[i].next){
		int p=e[i].to;now[x]=i;
		if(!e[i].r||vis[p]==ti||dis[p]!=dis[x]+e[i].val) continue;
		ll k=dfs(p,min(lim,(ll)e[i].r));
		e[i].r-=k,e[i^1].r+=k;
		lim-=k,ret+=k;
		ans+=k*(e[i].val-h[x]+h[p]);
		if(!lim) return ret;
	}
	return ret;
}

signed main(){
	cin>>n>>m>>s>>t;ll maxflow=0;
	fo(i,1,m){
		int x=read(),y=read(),w=read(),c=read();
		connect(x,y,w,c);
		connect(y,x,0,-c);
	}
	fo(i,1,n) connect(0,i,0,0);
	spfa();
	fo(i,1,n) for(int j=head[i];j;j=e[j].next) e[j].val+=h[i]-h[e[j].to];
	while(dij()){
		++ti;
		maxflow+=dfs(s,inf);
	}
	cout<<maxflow<<' '<<ans;
	return 0;
}
2022/1/5 21:21
加载中...