```cpp
/*
Dinic最大流全程:
1.bfs分层+判断有无增广路,当前弧设为head
2.dfs寻找增广路
2-1.dfs的时候,带两个参数cur(当前遍历到的点),mini(当前增广路最小的流量)
2-2.如果到了汇点,返回mini,同时累积最大流
2-3.统计当前点我用的流量大小。
2-4.从当前弧开始流,流一次更新当前弧。
2-5.如果遍历到的点在我下一层并且流量不为0,那么我就可以试着走走,注意,最小流量要减去我用过的流量!
2-6.如果走通了,那么正边减流量,反边加流量,同时统计当前点用的流量大小,如果已经流满了,就没必要继续枚举了
2-7.最后返回值为我用的流量大小。
Dinic最小费用最大流:
spfa分层+用距离代替深度
需要一个额外的vis数组,表示这个点是否被访问过,访问过就不访问了(除了汇点
*/
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
struct Edge{
int v,flow,cost;
}edge[100005];
int read(){
int x=0,f=1;
char c=getchar();
while((c<'0'||c>'9')&&c!='-')c=getchar();
if(c=='-'){
f=-1;
c=getchar();
}
while((c>='0')&&c<='9'){
x=x*10+(c-'0');
c=getchar();
}
return x*f;
}
int nxt[100005];
int head[5005];
bool in[5005];
bool vis[5005];
int dis[5005];
int ansflow,anscost,cnt;
void addedge(int u,int v,int flow,int cost){
edge[++cnt].v=v;
edge[cnt].flow=flow;
edge[cnt].cost=cost;
nxt[cnt]=head[u];
head[u]=cnt;
return;
}
bool spfa(){
for(register int i=1;i<=n;i++){
in[i]=false;
dis[i]=2147483647;
}
queue<int> q;
q.push(s);
dis[s]=0;
in[s]=true;
while(!q.empty()){
int tmp=q.front();
q.pop();
in[tmp]=false;
for(register int i=head[tmp];i;i=nxt[i]){
int v=edge[i].v;
int flow=edge[i].flow;
int cost=edge[i].cost;
if(flow&&dis[tmp]+cost<dis[v]){
dis[v]=dis[tmp]+cost;
if(!in[v]){
in[v]=true;
q.push(v);
}
}
}
}
return dis[t]<2147483647;
}
int dfs(int cur,int mini){
if(cur==t){
vis[t]=true;
ansflow+=mini;
return mini;
}
int fl=0;
int used=0;
vis[cur]=true;
for(register int i=head[cur];i;i=nxt[i]){
int v=edge[i].v;
int flow=edge[i].flow;
int cost=edge[i].cost;
if(((!vis[v])||v==t)&&dis[cur]+cost==dis[v]&&flow){
int tmp=dfs(v,min(mini-used,flow));
if(tmp){
used+=tmp;
edge[i].flow-=tmp;
edge[i^1].flow+=tmp;
anscost+=edge[i].cost*tmp;
if(used==mini)break;
}
}
}
return used;
}
void dinic(){
while(spfa()){
vis[t]=true;
while(vis[t]){
for(register int i=1;i<=n;i++){
vis[i]=false;
}
dfs(s,2147483647);
}
}
return;
}
int main(){
n=read();m=read();s=read();t=read();
int u,v,flow,cost;
for(register int i=1;i<=m;i++){
u=read(),v=read(),flow=read(),cost=read();
addedge(u,v,flow,cost);
addedge(v,u,0,-cost);
}
dinic();
printf("%d %d",ansflow,anscost);
return 0;
}
```
by hmya @ 2022-10-22 16:19:30
`cnt` 初始值应该为 $1$……
by Nt_Tsumiki @ 2022-10-22 16:27:55
@[H2OCaO](/user/264490)
by Nt_Tsumiki @ 2022-10-22 16:28:20
@[Nt_Yester](/user/420129) 都行)
by hmya @ 2022-10-22 16:55:00
@[H2OCaO](/user/264490) 都行才怪 [link](https://www.luogu.com.cn/record/91009257)
by Nt_Tsumiki @ 2022-10-22 16:59:33
@[Nt_Yester](/user/420129) 我以为我设的-1,我是沙比对不起,谢谢谢谢
by hmya @ 2022-10-22 17:01:49