在跑完第一遍费用流之后的删边应该怎么删啊
本题中,如果不把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;
}