奇怪 RE 求调
  • 板块学术版
  • 楼主catandcode
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/6/16 19:34
  • 上次更新2023/10/23 13:01:44
查看原帖
奇怪 RE 求调
767681
catandcode楼主2023/6/16 19:34

网络流模板,照着 OIwiki 写了个 MPM,报错 Aborted / IOT trap,下载第一个测试点,程序在主函数 return 0 语句前 RE,有什么写法的问题吗?

#include<bits/stdc++.h>
#define ld long double
#define ll long long
using namespace std;
const int N=2e2+5;
const int M=5e3+5;
int n,m,s,t,tol,head[N],from[M<<1],to[M<<1],hd,tl,q[N],fr[M<<1];
ll limit[M<<1],fl[M<<1];
void add(int x,int y,int z) {
	from[++tol]=head[x]; fr[tol]=x; head[x]=tol; to[tol]=y; limit[tol]=z;
	from[++tol]=head[y]; fr[tol]=y; head[y]=tol; to[tol]=x; limit[tol]=0;
}
vector<int> dis,alive;
vector<int> out[N],in[N];
vector<ll> pin,pout,ex;
#define get(x) (min(pin[x],pout[x]))
void del(int u) {
	for(int i:out[u]) {
		int v=to[i];
		auto it=find(in[v].begin(),in[v].end(),i);
		in[v].erase(it);
		pin[v]-=limit[i]-fl[i];
	}
	for(int i:in[u]) {
		int v=fr[i];
		auto it=find(out[v].begin(),out[v].end(),i);
		out[v].erase(it);
		pout[v]-=limit[i]-fl[i];
	}
}
void get_way(int ori,int des,ll f,bool tmp) {
	hd=1,tl=0; ex.assign(n,0); ex[ori]=f; q[++tl]=ori;
	while(hd<=tl) {
		int u=q[hd++];
		if(u==des) return;
		ll tot=ex[u];
		auto it=tmp?out[u].begin():in[u].begin();
		while(1) {
			int v=tmp?to[*it]:fr[*it];
			ll c=min(tot,limit[*it]-fl[*it]);
			if(c==0) break;
			if(tmp) pout[u]-=c,pin[v]-=c;
			else pin[u]-=c,pout[v]-=c;
			if(!ex[v]) q[++tl]=v;
			ex[v]+=c,fl[*it]+=c,fl[(*it)^1]-=c,tot-=c;
			if(limit[*it]-fl[*it]==0) {
				auto jt=it; ++jt;
				if(tmp) in[v].erase(find(in[v].begin(),in[v].end(),*it)),out[u].erase(it);
				else out[v].erase(find(out[v].begin(),out[v].end(),*it)),in[u].erase(it);
				it=jt;
			}
			else break;
			if(!tot) break;
		}
	}
}
ll maxflow() {
	ll flow=0;
	while(1) {
		pin.assign(n,0),pout.assign(n,0);
		dis.assign(n,-1),alive.assign(n,1);
		tl=0; q[++tl]=s,dis[s]=0,hd=1;
		while(hd<=tl) {
			int u=q[hd++];
			for(int i=head[u],v=to[i];i;i=from[i],v=to[i]) {
				if(limit[i]-fl[i]==0||dis[v]!=-1) continue;
				dis[v]=dis[u]+1,q[++tl]=to[i];
			}
		}
		if(dis[t]==-1) return flow;
		for(int i=1;i<=n;++i) out[i].clear(),in[i].clear();
		for(int i=2;i<=tol;++i) {
			if(limit[i]-fl[i]==0) continue;
			int u=fr[i],v=to[i];
			if(dis[u]+1==dis[v]&&(dis[v]<dis[t]||v==t)) {
				in[v].push_back(i),out[u].push_back(i);
				pin[v]+=limit[i]-fl[i],pout[u]+=limit[i]-fl[i];
			}
		}
		pin[s]=pout[t]=1e18;
		while(1) {
			int u=-1;
			for(int i=1;i<=n;++i) if(alive[i]&&(u==-1||get(i)<get(u))) u=i;
			if(u==-1) break;
			if(!get(u)) {
				alive[u]=0,del(u);
				continue;
			}
			ll f=get(u);
			flow+=f,get_way(u,s,f,0),get_way(u,t,f,1),alive[u]=0,del(u);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin>>n>>m>>s>>t; tol=1;
	for(int i=1,x,y,z;i<=m;++i) cin>>x>>y>>z,add(x,y,z);
	cout<<maxflow()<<"\n";
	return 0;
}
10 25 3 1
9 3 80
5 10 62
4 2 13
7 2 20
3 10 90
6 10 53
2 3 11
6 3 45
9 5 37
10 9 93
7 8 28
4 5 28
1 2 52
4 5 54
1 2 62
7 4 64
4 3 40
7 3 39
8 2 72
7 5 5
3 6 88
3 2 56
9 2 72
2 1 81
6 7 84

2023/6/16 19:34
加载中...