代码求调
//【模板】最小费用最大流
#include<bits/stdc++.h>
using namespace std;
#if true
#define USE_QUEUE
#endif
#define int long long
const int inf=0x7ffffff;
inline int read(){
int x=0,f=1;
char c;
for(c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-f;
for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^48);
return x*f;
}
class edge{
public:
int to,pri,flw;
edge*next,*fb;//fb=反边
edge(int to,edge *next,int flw=1,int pri=1):next(next),to(to),flw(flw),pri(pri){}
};
class node{
public:
int dis,incf,flw;
bool vis;
edge *e,*cur; //cur:当前弧,以便优化使用
node():e(nullptr),cur(nullptr),dis(inf),vis(false),incf(0){}
edge *add(int to,int flw=1,int pri=1){return e=new edge(to,e,flw,pri);}
};
unordered_map<int,node>dat;
#ifdef USE_QUEUE
queue<int> q;
#else
stack<int> q;
#endif
int n,m,s,t,u,v,w,c,ans,flow,cost;
inline bool spfa(){
while(!q.empty())q.pop();
q.push(s),dat[s].dis=0,dat[s].vis=true,dat[s].incf=inf,dat[s].cur=dat[s].e;
for(int now;!q.empty();){
#ifdef USE_QUEUE
now=q.front();
#else
now=q.top();
#endif
q.pop(),dat[now].vis=false;
for(edge *p=dat[now].e;p!=nullptr;p=p->next){
if(p->flw && (dat[p->to].dis>dat[now].dis+p->pri)){
dat[p->to].dis=dat[now].dis+p->pri;
dat[p->to].incf=min(dat[p->to].incf,p->flw);
dat[p->to].cur=p;
if(!dat[p->to].vis)dat[p->to].vis=true,q.push(p->to);
}
}
}
return dat[t].dis!=inf;
}
inline int dfs(int now,int sum){
dat[now].vis=true;
if(now==t)return sum;
int used=0,tmp;
for(edge*p=dat[now].cur;p!=nullptr;p=p->next){
tmp=dfs(p->to,min(p->flw,sum-used));
if(p->flw>0&&dat[t].dis==dat[now].dis+p->pri&&(!dat[p->to].vis||t==p->to)&&tmp){\
p->flw-=tmp,p->fb->flw+=tmp;
cost+=tmp*p->pri,used+=tmp;
if(used>=sum)break;
}
}
dat[now].vis=false;
return used;
}
inline void add(int u,int v,int w=1,int c=1){
dat[u].add(v,w,c),dat[v].add(u,0,-c);
dat[u].e->fb=dat[v].e,dat[v].e->fb=dat[u].e;
//注意反边,其边权初值应当为0
}
inline void dinic(){
while(spfa()){
printf("step A done.\n");
ans+=dfs(s,inf);
printf("step B done.\n");
}
}
signed main(){
n=read(),m=read(),s=read(),t=read();
for(int i=1;i<=m;i++)u=read(),v=read(),w=read(),c=read(),add(u,v,w,c);
dinic();
printf("%lld %lld",flow,cost);
}
码风不太好,谢谢大佬^_^