63pts最后3T1WA求调
查看原帖
63pts最后3T1WA求调
452438
_Minecraft12345楼主2024/4/13 16:06

调试发现第8个点第二次进SPFA后死循环了

下面一堆警钟都看了,也没有找到问题,估计能敲新警钟

#include<bits/stdc++.h>
using namespace std;
int head[100010],cur[100010],nxt[100010],to[100010],w[100010];
int cnt=1;
int n,m,s,t;
int c[100010];
void ae(int x,int y,int ww,int cc) {
	++cnt;
	w[cnt]=ww;
	to[cnt]=y;
	nxt[cnt]=head[x];
	head[x]=cnt;
	c[cnt]=cc;
}
int dis[100010],deep[100010];
bool book[100010];
queue<int>q;
bool spfa() {
	memset(dis,0x7f,sizeof(dis));
	memset(deep,0,sizeof(deep));
	memset(book,0,sizeof(book));
	for(int i=1; i<=n; i++) {
		cur[i]=head[i];
	}
	q.push(s);
	dis[s]=0;
	deep[s]=1;
	book[s]=1;
	while(!q.empty()) {
		int x=q.front();
		q.pop();
		book[x]=0;
		for(int i=head[x]; i; i=nxt[i]) {
			int y=to[i];
			if(w[i]==0)continue;
			if(dis[y]>dis[x]+c[i]) {
				dis[y]=dis[x]+c[i];
				deep[y]=deep[x]+1;
				if(book[y]==0) {
					book[y]=1;
					q.push(y);
				}
			}
		}
	}
	if(deep[t])return 1;
	return 0;
}
struct node {
	int f,c;//flow,cost
};
node dfs(int x,int minn) {
	if(x==t) {
		return {minn,0};
	}
	for(int &i=cur[x]; i; i=nxt[i]) {
		int y=to[i];
		if(deep[y]!=deep[x]+1||w[i]==0) {
			continue;
		}
		node tmp=dfs(y,min(minn,w[i]));
		if(tmp.f!=0) {
			w[i]-=tmp.f;
			w[i^1]+=tmp.f;
			tmp.c+=tmp.f*c[i];
			return tmp;
		}
	}
	return {0,0};
}
int main() {
	//freopen("P3381_8.in","r",stdin);
	cin>>n>>m>>s>>t;
	for(int i=1; i<=m; i++) {
		int ui,vi,wi,ci;
		cin>>ui>>vi>>wi>>ci;
		ae(ui,vi,wi,ci);
		ae(vi,ui,0,-ci);
	}
	int flow=0,cost=0;
	while(spfa()) {
		while(1) {
			node tmp=dfs(s,0x7fffffff);
			if(tmp.f==0)break;
			flow+=tmp.f;
			cost+=tmp.c;
		}
	}
	cout<<flow<<' '<<cost;
	return 0;
}
2024/4/13 16:06
加载中...