如题,网络流已经大体全部掌握了,来做一下费用流,有神犇跟我说,费用流跟网络流的区别就是把bfs改成spfa求一条路径最短的增广路,这个路径指的是费用路径。于是我按着自己的思路写出了这样的板子,但是后四个点无情WA,球球帮忙
#include<bits/stdc++.h>
#define maxn 100005
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair<int,int> P;
struct eee{
int to;
int w;
int d;
int next;
}edge[maxn];
struct ppp{
int v;//??????
int edge;//
}pre[maxn];
int s,t,ans,n,m,cnt;
int root[maxn],dis[maxn],inque[maxn],vis[maxn];
priority_queue<P,vector<P>,greater<P>>q;
inline void add(int x,int y,int w,int d){
edge[++cnt]={y,w,d,root[x]};
root[x]=cnt;
}
bool spfa(){
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
while(q.size())q.pop();
dis[s]=0;
q.push({0,s});
while(q.size()){
auto p=q.top();
q.pop();
int u=p.second;
if(vis[u])continue;
if(dis[u]!=p.first)continue;
//printf("%d %d\n",p.first,p.second);
vis[u]=1;
for(int i=root[u];i;i=edge[i].next){
int v=edge[i].to,w=edge[i].d;
if(vis[v]||!edge[i].w)continue;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
pre[v]={u,i};
q.push({dis[v],v});
}
}
}
return dis[t]!=inf;
}
void EK(){
int ans=0,w=0;
while(spfa()){
int k=inf;
int f=dis[t];
for(int i=t;i!=s;i=pre[i].v){
k=min(edge[pre[i].edge].w,k);
}
for(int i=t;i!=s;i=pre[i].v){
edge[pre[i].edge].w-=k;
edge[pre[i].edge^1].w+=k;
}
ans+=k;
w+=k*f;
}
cout<<ans<<' '<<w<<endl;
}
void sync(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
signed main(){
//freopen("P3381_8.in","r",stdin);
sync();
cin>>n>>m>>s>>t;
while(m--){
int u,v,w,c;
cin>>u>>v>>w>>c;
add(u,v,w,c);
add(v,u,0,c);
}
EK();
return 0;
}