# 【模板】最小费用最大流

### 最大费用最大流就把最短路改成最长路即可.

```#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=5005;
const int M=100005;
int n,m,s,t,max_flow,ans;
int dis[N],visit[N],incf[N],pre[N];
inline void add(int a,int b,int c,int d){
to[tot]=b;limit[tot]=c;w[tot]=d;
}
inline bool spfa(){
for(int i=1;i<=n;++i)visit[i]=0,dis[i]=1e9;
queue<int>q;q.push(s);
dis[s]=0;visit[s]=1;incf[s]=1e9;
while(q.size()){
int u=q.front();q.pop();visit[u]=0;
if(!limit[i])continue;
int v=to[i];
if(dis[v]>dis[u]+w[i]){
dis[v]=dis[u]+w[i];
incf[v]=min(incf[u],limit[i]);
pre[v]=i;
if(!visit[v])visit[v]=1,q.push(v);
}
}
}
if(dis[t]==1e9)return false;
return true;
}
inline void update(){
int x=t;
while(x!=s){
int i=pre[x];
limit[i]-=incf[t];
limit[i^1]+=incf[t];
x=to[i^1];
}
max_flow+=incf[t];
ans+=dis[t]*incf[t];
}
int main(){