社区讨论

P3381 不同环境下输出不同求助

P3381【模板】最小费用最大流参与者 2已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@m6j8jy6y
此快照首次捕获于
2025/01/30 19:12
去年
此快照最后确认于
2025/01/31 11:33
去年
查看原帖
以下代码在洛谷上可以 AC,但在本机上连样例都过不了。(编译选项 -O2 -std=c++14 -static -Wall -Wextra -Wl,-stack=140692391198720
最离奇的是我最后明明是输出两个数,本机样例就输出一个 00
求助大佬,这究竟是怎么回事?
CPP
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=5010,M=5e4+10; int s,t,cnt=1,h[N],d[N],f[N],lst[N]; bool vis[N];
struct Edge { int v,w,c,nxt; }e[M<<1];
void add(int u,int v,int w,int c) { e[++cnt]=(Edge){v,w,c,h[u]},h[u]=cnt; }
bool SPFA() {
	memset(d,0x3f,sizeof(d)),memset(vis,false,sizeof(vis));
	queue<int>q; q.push(s),d[s]=0,f[s]=0x3f3f3f3f,vis[s]=true;
	while(!q.empty()) {
		int u=q.front(); q.pop(),vis[u]=false;
		for(int i=h[u];i;i=e[i].nxt) {
			int v=e[i].v,w=e[i].w,c=e[i].c;
			if(w&&d[v]>d[u]+c) {
				d[v]=d[u]+c,f[v]=min(f[u],w),lst[v]=i;
				if(!vis[v]) vis[v]=true,q.push(v);
			}
		}
	}
	return d[t]!=0x3f3f3f3f;
}
int main() {
	ios::sync_with_stdio(false),cin.tie(nullptr);
	int n,m,u,v,w,c,flow=0,cost=0; cin>>n>>m>>s>>t;
	while(m--) cin>>u>>v>>w>>c,add(u,v,w,c),add(v,u,0,-c);
	while(SPFA()) {
		flow+=f[t],cost+=f[t]*d[t];
		for(int i=lst[t];i;i=lst[e[i^1].v]) e[i].w-=f[t],e[i^1].w+=f[t];
	}
	cout<<flow<<' '<<cost;
	return 0;
}

回复

5 条回复,欢迎继续交流。

正在加载回复...