求助上下界网络流
查看原帖
求助上下界网络流
1190738
xtzqhywww楼主2024/8/10 10:37

在跑完第一遍费用流之后的删边应该怎么删啊

本题中,如果不把nxt也清空会错,但别的题目中清空nxt会错,这是为什么

本题代码

#include"bits/stdc++.h"
#define re register
#define int long long
#define pii pair<int,int> 
#define fi first
#define se second
using namespace std;
const int maxn=1e6+10,maxm=1e7+10,inf=1e18;
int n,s1,t1,s,t,cnt=1,ans;
int head[maxn],dis[maxn],h[maxn],f[maxn];
struct edge{
	int to,nxt,f,w;
}e[maxm<<1];
struct node{
	int v,e;
}pre[maxm<<1];
bitset<maxn> vis;
inline void add(int u,int v,int f,int w){
	++cnt;
	e[cnt]={v,head[u],f,w};
	head[u]=cnt;
}
inline void add_edge(int u,int v,int f,int w){add(u,v,f,w),add(v,u,0,-w);}
inline void spfa(){
	for(re int i=1;i<=n+3;++i) h[i]=inf;
	queue<int> q;
	h[s]=0;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(re int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(e[i].f&&h[v]>h[u]+e[i].w){
				h[v]=h[u]+e[i].w;
				if(!vis[v]) q.push(v),vis[v]=1;
			}
		}
	}
}
inline bool dij(){
	for(re int i=1;i<=n+3;++i) dis[i]=inf;
	vis.reset();
	priority_queue<pii,vector<pii>,greater<pii>> q;
	dis[s]=0;
	q.push({0,s});
	while(!q.empty()){
		int u=q.top().se;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(re int i=head[u];i;i=e[i].nxt){
			int v=e[i].to,w=e[i].w+h[u]-h[v];
			if(e[i].f&&dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				pre[v].v=u;
				pre[v].e=i;
				if(!vis[v]) q.push({dis[v],v});
			}
		}
	}
	return dis[t]!=inf;
}
inline void mfmc(){
	int mnc=0;
	spfa();
	while(dij()){
		int mnf=inf;
		for(re int i=1;i<=n+3;++i) h[i]+=dis[i];
		for(re int i=t;i!=s;i=pre[i].v) mnf=min(mnf,e[pre[i].e].f);
		for(re int i=t;i!=s;i=pre[i].v){
			e[pre[i].e].f-=mnf;
			e[pre[i].e^1].f+=mnf;
		}
		mnc+=mnf*h[t];
	}
	ans+=mnc;
}
signed main(){
// 	freopen("1.in","r",stdin);
// 	freopen("1.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	s1=1,t1=n+1,s=t1+1,t=s+1;
	for(re int i=1,num;i<=n;++i){
		cin>>num;
		for(re int j=1,v,w;j<=num;++j){
			cin>>v>>w;
			add_edge(i,v,inf-1,1*w);
			f[v]-=1,f[i]+=1;
			ans+=1*w;
		}
	}
	for(re int i=2;i<=n;++i) add_edge(i,t1,inf,0);
	for(re int i=1;i<=t1;++i){
		if(f[i]<0) add_edge(s,i,-f[i],0);
		if(f[i]>0) add_edge(i,t,f[i],0);
	}
	add_edge(t1,s1,inf,0);
	mfmc();
	e[cnt].f=e[cnt^1].f=0;
	e[cnt].nxt=e[cnt^1].nxt=0;//这里不清空就成0pts了
	s=s1,t=t1;
	mfmc();
	cout<<ans;
	return 0;
}
2024/8/10 10:37
加载中...