附:
# 我的代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
const long long inf=0x7fffffffffffffff;
inline int read(){
char c;
int ret=0;
for(c=getchar();c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';c=getchar())ret=ret*10+c-'0';
return ret;
}
inline void write(int x) {
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
class line{
public:
long long u,v,w,c;
line *next;
line(int u=0,int v=0,int w=0,int c=0,line *next=NULL):
u(u),v(v),w(w),c(c),next(next){}
}*L[5009];
class node{
public:
line *edge;
void newline(int u,int v,int w,int c){edge=new line(u,v,w,c,edge);}
}dat[5009];
long long n,m,s,t,u,v,w,c,mincost,maxflow,dis[5009],flow[5009],from[5009],last,h[5009];
bool vis[5009];
bool dij(long long start,long long end){
line *p;
long long minn,mn;
last=start;
for(int i=1;i<=n;i++){
dis[i]=inf;
flow[i]=inf;
from[i]=vis[i]=0;
L[i]=NULL;
}
dis[start]=0;
vis[start]=true;
flow[start]=inf;
for(p=dat[last].edge;p!=NULL;p=p->next){
if(p->w>0&&vis[p->v]==false&&dis[p->v]>dis[last]+p->w+h[last]-h[p->v]){
dis[p->v]=dis[last]+p->c+h[last]-h[p->v];
flow[p->v]=min(p->w,flow[last]);
from[p->v]=last;
L[p->v]=p;
}
}
for(int i=2;i<=n;i++){
minn=inf;
mn=-1;
for(int i=1;i<=n;i++)
if(vis[i]==false&&minn>dis[i]){
minn=dis[i];mn=i;
}
if(mn==-1)return false;
vis[mn]=true;
if(mn==end)return true;
for(p=dat[last].edge;p!=NULL;p=p->next){
if(p->w>0&&vis[p->v]==false&&dis[p->v]>dis[last]+p->w+h[last]-h[p->v]){
dis[p->v]=dis[last]+p->c+h[last]-h[p->v];
flow[p->v]=min(p->w,flow[last]);
from[p->v]=last;
L[p->v]=p;
}
}
last=mn;
}
return dis[end]!=inf;
}
line *get(line *p){
for(line*q=dat[p->v].edge;q!=NULL;q=q->next)if(q->v==p->u)return q;
return NULL;
}
int main(){
freopen("read.txt","r",stdin);
n=read();m=read();s=read();t=read();
for(int i=1;i<=m;i++){
u=read();v=read();w=read();c=read();
dat[u].newline(u,v,w,c);dat[v].newline(v,u,0,-c);
}
while(dij(s,t)){
mincost+=flow[t]*(dis[t]-h[s]+h[t]);
maxflow+=flow[t];
for(int i=t;i!=s;i=from[i]){
L[i]->w-=flow[t];
get(L[i])->w+=flow[t];
}
for(int i=1;i<=n;i++)
if(dis[i]!=inf)h[i]+=dis[i];
}
write(mincost);putchar(' ');write(maxflow);
}
```
# 样例输出:
`60 20`
by _3847_ @ 2021-12-05 21:21:55
u1s1 别指望有人帮你调网络流
碰上了也是运气好
by sycqwq @ 2021-12-05 21:24:31
@[无敌的蒟蒻](/user/151647) `why?`
by _3847_ @ 2021-12-05 21:25:21
@[lzk_jr_Na2CO3](/user/384007) 难啊
by Solgareo @ 2021-12-05 21:28:54
@[Solgareo](/user/353378) 啊……
就兑运气,弱校选手没活路。
by wangbinfeng @ 2021-12-05 21:31:01
https://www.luogu.com.cn/discuss/379612
by lgvc @ 2021-12-05 21:39:59
@[lzk_jr_Na2CO3](/user/384007) 代码这种事情还是自己调吧,考试的时候没人帮你调
但可以提一点建议:
1. 最好不要用指针,容易错,效率也不高
2. 这种东西建议对着别人博客写,不要东拼西凑,我在此提供一下[我的模板](https://www.luogu.com.cn/paste/mdruadeq)
3. 不会的算法尽量还是要学(指spfa),还是很有用的,spfa没有死
by 45dino @ 2021-12-05 21:40:45
@[45dino](/user/240812) thx
别人博客我找不到,题解只有一个时dij的但只有关键代码……然后我就把前两篇拼到一起了
spfa我抽空自学吧,不过为什么大家都说spfa死了您却认为没有呢
by wangbinfeng @ 2021-12-05 21:45:54
@[lgvc](/user/366807) 《如果我有钱的话》
by wangbinfeng @ 2021-12-05 21:46:14
@[lgvc](/user/366807) 我一般就在b站白嫖
by wangbinfeng @ 2021-12-05 21:47:05