以下代码在洛谷上可以 AC,但在本机上连样例都过不了。(编译选项 -O2 -std=c++14 -static -Wall -Wextra -Wl,-stack=140692391198720
)
最离奇的是我最后明明是输出两个数,本机样例就输出一个 0。
求助大佬,这究竟是怎么回事?
#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;
}