调试发现第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;
}