- 给定一张(n)个点(m)条边的网络，源点为(1)，汇点为(n)。
- 给出每条边的容量和流量，但可能存在流量超过容量或是一个点流量不平衡的错误情况。
- 一次操作可以将某条边的容量或流量(pm 1)，求最少要多少次操作使得网络正确。
- (n,mle 100)
流量不平衡网络
其实流量不平衡这种情况不仅会出现在这题，应该算是一个相当经典的问题。
实际上，很多题目中我们都需要强制某条边流量是多少甚至强制流满，那其实就相当于是要处理一个流量不平衡的网络。
针对这种问题的通用解法，就是记录每个点的入流减出流(d_i)，如果(d_i>0)说明还没流完，向超级汇连一条容量为(d_i)的边；如果(d_i<0)说明不够流，自超级源连一条容量为(-d_i)的边。
而对于原本的源汇点，我们还需要从原汇点向原源点连一条容量为(INF)的边（或是直接把它们看作一个点），因为它们俩放一起才需要满足流量平衡。
增流与退流
尽管流量的变化很灵活，但容量的变化其实是非常死板的——只有当你超过容量去增流，才需要增大容量。
于是我们根据初始情况下容量(c)和流量(f)的关系，分类讨论建图：
- (fle c)：如果我们想给这条边增流，前(c-f)点只需(1)的代价增大流量，之后(infty)点都需要(2)的代价同时增大流量和容量；而如果我们想给这条边减流，只能减(f)点，都需要(1)的代价。
- (f>c)：首先不管我们要减少流量还是增大容量，都必须要支付(f-c)的代价，这部分可以预支掉。如果我们想给这条边增流，始终都需要(2)的代价；而如果我们想给这条边建流，前(f-c)点由于已经预支无需代价，剩余还能减(c)点都需要(1)的代价。
这样一来再跑遍最小费用最大流，并加上预支代价即可。
代码：(O(Dinic))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100
#define INF (int)1e9
using namespace std;
int n,m,d[N+5];
class MinCostMaxFlow
{
private:
#define PS (N+2)
#define ES (4*N)
#define s (n+1)
#define t (n+2)
#define E(x) ((((x)-1)^1)+1)
int ee,lnk[PS+5];struct edge {int to,nxt,F,C;}e[2*ES+5];
int lst[PS+5],IQ[PS+5],F[PS+5],C[PS+5];queue<int> q;
I bool SPFA()
{
RI i,k;for(i=1;i<=t;++i) F[i]=C[i]=INF;q.push(s),C[s]=0;
W(!q.empty()) for(i=lnk[k=q.front()],q.pop(),IQ[k]=0;i;i=e[i].nxt)
{
if(!e[i].F||C[k]+e[i].C>=C[e[i].to]) continue;
C[e[i].to]=C[k]+e[lst[e[i].to]=i].C,F[e[i].to]=min(F[k],e[i].F),
!IQ[e[i].to]&&(q.push(e[i].to),IQ[e[i].to]=1);
}return F[t]^INF;
}
public:
I void Add(CI x,CI y,CI f,CI c)
{
e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y,e[ee].F=f,e[ee].C=c,
e[++ee].nxt=lnk[y],e[lnk[y]=ee].to=x,e[ee].F=0,e[ee].C=-c;
}
I int MCMF()
{
RI x,g=0;W(SPFA()) {g+=C[t]*F[t],x=t;
W(x^s) e[lst[x]].F-=F[t],e[E(lst[x])].F+=F[t],x=e[E(lst[x])].to;}
return g;
}
}D;
int main()
{
RI i,u,v,c,f,g=0;for(scanf("%d%d",&n,&m),i=1;i<=m;++i) scanf("%d%d%d%d",&u,&v,&c,&f),d[u]+=f,d[v]-=f,//记录度数
f<=c?(D.Add(u,v,c-f,1),D.Add(u,v,INF,2),D.Add(v,u,f,1)):(g+=f-c,D.Add(u,v,INF,2),D.Add(v,u,f-c,0),D.Add(v,u,c,1));//根据f与c的大小关系分类建图
for(i=1;i<=n;++i) d[i]>0&&(D.Add(i,t,d[i],0),0),d[i]<0&&(D.Add(s,i,-d[i],0),0);//流量不平衡，根据正负和超级源汇连边
return D.Add(n,1,INF,0),printf("%d
",g+D.MCMF()),0;//原汇点向原源点连一条容量INF的边，答案为预支代价+最小费用
}