费用流+SPFA ||Luogu P3381【模板】最小费用最大流

代码：
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<queue>
 5 #define ll long long
 6 #define min(a,b) ((a)<(b)?(a):(b))
 7 #define max(a,b) ((a)>(b)?(a):(b))
 8 using namespace std;
 9 inline ll rd(){
10     ll x=0,f=1;char c=getchar();
11     while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
12     while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
13     return f*x;
14 }
15 const int maxn=5050,maxm=50050;
16 int N,M,num_edge=-1,edge_head[maxn],S,T,u,v,w,f,pre[maxn];
17 ll Dis[maxn],Fw[maxn],mxfw,mndis;
18 bool vis[maxn];
19 queue<int>Q;
20 struct Edge{int to,nx,from;ll dis,fw;}edge[maxm<<1];
21 inline void Add_edge(int from,int to,ll fw,ll dis){
22     edge[++num_edge].nx=edge_head[from];
23     edge[num_edge].from=from;
24     edge[num_edge].to=to;
25     edge[num_edge].fw=fw;
26     edge[num_edge].dis=dis;
27     edge_head[from]=num_edge;
28     return;
29 }
30 inline bool SPFA(){
31 //    for(int i=1;i<=N;i++)
32 //        Dis[i]=Fw[i]=1ll<<60;
33     memset(Dis,0x7f,sizeof(Dis));
34     memset(Fw,0x7f,sizeof(Fw));
35     memset(vis,0,sizeof(vis));
36     pre[S]=pre[T]=-1;//Imp
37     Q.push(S);
38     vis[S]=1;
39     Dis[S]=0;
40     while(!Q.empty()){
41         int x=Q.front();
42         Q.pop();
43         vis[x]=0;
44         for(int i=edge_head[x];i!=-1;i=edge[i].nx){
45             int y=edge[i].to;
46             if(edge[i].fw&&edge[i].dis+Dis[x]<Dis[y]){
47                 Dis[y]=edge[i].dis+Dis[x];
48                 Fw[y]=min(Fw[x],edge[i].fw);//这一步和Dinic差不多 
49                 pre[y]=i;
50                 if(vis[y]==0){
51                     Q.push(y);
52                     vis[y]=1;
53                 }
54             }
55         }
56     }
57     if(pre[T]!=-1)return 1;
58     return 0;
59 }
60 inline void FYL(){
61     mxfw=mndis=0;
62     while(SPFA()){
63         mxfw+=Fw[T];
64         mndis+=Dis[T]*Fw[T];
65         for(int i=pre[T];i!=-1;i=pre[edge[i].from]){
66             edge[i].fw-=Fw[T];
67             edge[i^1].fw+=Fw[T];
68         }
69     }
70     return;
71 }
72 int main(){
73     memset(edge_head,-1,sizeof(edge_head));
74     N=rd();M=rd();S=rd();T=rd();
75     for(int i=1;i<=M;i++){
76         u=rd();v=rd();w=rd();f=rd();
77         Add_edge(u,v,w,f);
78         Add_edge(v,u,0,-f);
79     }
80     FYL();
81     printf("%lld %lld
",mxfw,mndis);
82     return 0;
83 }
By:AlenaNuna