费用流

理解

在lzz大佬讲解下一下就理解了，%%%

就是把bfs改称spfa，中间的dis数组就是费用，也就是要找到s到t的最短路作为增光路

所以所有在dinic找到的增光路费用都是相同的，然后就是板子了

注意在dinic中，防止有负环，所以要用vis数组像dfs一样进行判重

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e3,M=5e4+5,inf=1e14;
int n,m,cnt=1,ans1,ans2,cost;
int dis[N],vis[N],head[N],s[N],now[N];
struct edge{int v,w,c,nxt;
}e[M*2];
void add(int u,int v,int c,int w){e[++cnt]={v,w,c,head[u]};head[u]=cnt;
}
bool SPFA(){for(int i=1;i<=n;i++)  dis[i]=inf,vis[i]=0,now[i]=head[i],s[i]=0;queue<int>q;dis[1]=0;q.push(1);s[1]=1;while(!q.empty()){int u=q.front();q.pop();s[u]=0;for(int i=head[u];i;i=e[i].nxt){int v=e[i].v,w=e[i].w,c=e[i].c;if(c&&dis[v]>dis[u]+w){dis[v]=dis[u]+w;q.push(v),s[v]=1;}}}cost=dis[n];if(dis[n]<inf)  return 1;return 0;
}
int dinic(int u,int sum){if(u==n)  return sum;vis[u]=1;int flow=0;for(int i=now[u];i&&sum;i=e[i].nxt){now[u]=i;//写成i了int v=e[i].v,c=e[i].c,w=e[i].w;if(c&&dis[v]==dis[u]+w&&!vis[v]){int k=dinic(v,min(sum,c));if(!k)  dis[v]=inf;e[i].c-=k,e[i^1].c+=k;//+-别写反了！！！！！！！！flow+=k,sum-=k;}}vis[u]=0;return flow;
}
signed main(){scanf("%lld%lld",&n,&m);for(int i=1;i<=m;i++){//别写成n了！！！！！！！！！！！！！！！int u,v,w,c;scanf("%lld%lld%lld%lld",&u,&v,&c,&w);add(u,v,c,w),add(v,u,0,-w);}while(SPFA()){int flow=dinic(1,inf);ans1+=flow;ans2+=flow*cost;}printf("%lld %lld\n",ans1,ans2);
}