网络流嘛，怎么看都是一堆逗逼题嘛，反正遇到还是都做不起嘛。。。。
网络流的模板非常简单，难点都在于建图，网络流的建图解决问题范围之广，下至A+B Problem，上至单纯形，线性规划。所以如果对于网络流的各种建图方式不熟悉，那么碰到对应的问题肯定完跪。
最大流：
这一部分确实没什么可以说的，你说他考裸的最大流？是不可能滴。考模拟增广路？至少我现在还没有遇到。
最小割：
网络流题目中最难的题目一般都是最小割，最小割建图大概有三种方式。
bzoj 3438 小A的作物
描述
小M在MC里开辟了两块巨大的耕地A和B（你可以认为容量是无穷），现在，小P有n中作物的种子，每种作物的种子有1个（就是可以种一棵作物）（用 1...n编号），现在，第i种作物种植在A中种植可以获得ai的收益，在B中种植可以获得bi的收益，而且，现在还有这么一种神奇的现象，就是某些作物 共同种在一块耕地中可以获得额外的收益，小M找到了规则*有m种作物组合，第i个组合中的作物共同种在A中可以获得c1i的额外收益，共同总在B中可以 获得c2i的额外收益，所以，小M很快的算出了种植的最大收益，但是他想要考考你，你能回答他这个问题么？
这道题由于其中蕴含严格的依赖关系，所以我们可以通过最大权闭合子图来建图，这个思路想起来还是比较顺的，但是我讲的不是这个算法。
讲最小割模型一般化，设i点与S相连则X[i]=0，否则X[i]=1，边(w,v)的流量w[u][v]
我们可以得到
最小割=sigma(max(0,x[v]-x[u])*w[u][v])
另：x[i]<=x[j]可理解为max(0,x[i]-x[j])*inf
可以认为，变量取值范围为0/1的线性规划问题都能像这样转换为最小割问题。
在回到原题设Xi为作物i种在哪个田地，Yi为第i个条件是否满足。可以通过各种无脑变换出线性规划方程组，建图就行了，初次推导还是非常烦，但是相信多推几次应该会熟练一些。
当然这道题要求答案最大化，我们应该先默认加入所有的权值，在使损失最小化。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 100100
#define MAXV 100100
#define MAXE 5100000
#define INF 0x3f3f3f3f
struct Edge
{
int val,np;
Edge *next,*neg;
}E[MAXE],*V[MAXV];
int tope=;
int sour=,sink=;
inline void addedge(int x,int y,int z)
{
// cout<<"Add edge:<"<<tope+1<<">"<<x<<" "<<y<<":"<<z<<endl;
E[++tope].np=y;
E[tope].val=z;
E[tope].next=V[x];
V[x]=&E[tope]; E[++tope].np=x;
E[tope].val=;
E[tope].next=V[y];
V[y]=&E[tope]; E[tope].neg=&E[tope-];
E[tope-].neg=&E[tope];
}
int q[MAXV],lev[MAXV];
int vis[MAXV],bfstime=;
bool bfs()
{
int head=-,tail=;
Edge *ne;
lev[sour]=;
vis[sour]=++bfstime;
q[]=sour;
while (head<tail)
{
for (ne=V[q[++head]];ne;ne=ne->next)
{
if (!ne->val || vis[ne->np]==bfstime)continue;
q[++tail]=ne->np;
vis[ne->np]=bfstime;
lev[ne->np]=lev[q[head]]+;
}
}
return vis[sink]==bfstime;
}
int dfs(int now,int maxf)
{
int ret=,t;
if (now==sink || !maxf)return maxf;
Edge* ne;
for (ne=V[now];ne;ne=ne->next)
{
if (!ne->val || lev[ne->np]!=lev[now]+)continue;
t=dfs(ne->np,min(maxf,ne->val));
ne->val-=t;
ne->neg->val+=t;
maxf-=t;
ret+=t;
//cout<<"Flow:"<<now<<"-"<<ne->np<<":"<<x<<"("<<ne->val<<")"<<endl;
}
if (!ret)lev[now]=-;
return ret;
}
int dinic()
{
int ret=;
while (bfs())
{
ret+=dfs(sour,INF);
}
return ret;
}
int va[MAXN],vb[MAXN]; int main()
{
freopen("input.txt","r",stdin);
int n,m;
int res=;
scanf("%d",&n);
for (int i=;i<=n;i++)
scanf("%d",va+i);
for (int i=;i<=n;i++)
scanf("%d",vb+i);
for (int i=;i<=n;i++)//x[i]==0?va[i]:vb[i]
{
res+=va[i];
res+=vb[i];
addedge(sour,i+,va[i]);//x[i]==1?-va[i] -> max(0,x[i]-0)*va[i];
addedge(i+,sink,vb[i]);//x[i]==0?-vb[i] -> max(0,1-x[i])*vb[i];
}
int t,x,y,z,ca,cb,p;
int ya,yb;
scanf("%d",&m);
for (int i=;i<=m;i++)
{
scanf("%d",&t);
scanf("%d%d",&ca,&cb);
res+=ca;res+=cb;
ya=i++n;
yb=i++n+m;
//ya[i]==1?-ca -> max(0,ya[i]-0)*ca
addedge(sour,ya,ca);
//yb[i]==0?-cb -> max(0,1-yb[i])*cb
addedge(yb,sink,cb);
for (int j=;j<t;j++)
{
scanf("%d",&p);
//if (x[p]==1) then ya[i]=1; -> ya[i]>=x[p] -> max(0,x[p]-ya[i])*inf
//if (x[p]==0) then yb[i]=0; -> yb[i]<=x[p] -> max(0,yb[i]-x[p])*inf
addedge(ya,+p,INF);
addedge(+p,yb,INF);
}
}
printf("%d\n",res-dinic());
}
bzoj 3438
在看另一道题：
n × m 的棋盘,要给每个点染色
若 (i, j) 为黑色,则美观度加 A i,j ;若为白色,则美观度增加 B i,j
若 (i, j) 与 (i, j + 1) 同为黑,则美观度增加 C i,j ;若同为白色,则美观度增加 D i,j
若 (i, j) 与 (i + 1, j) 同为黑,则美观度增加 E i,j ;若同为白色,则美观度增加 F i,j
求美观度的和的最大值
这道题是上面一道题的简化版。但可以通过另外的方式建图
这道题只有相邻两点间有连边，所以说我们可以将某两点间的边提出来，这是我们还不知道每条边的权值。
对于每一个最小割，都有对应的割边集合以及期望最小割的值，我们可以联立解方程解出答案。
这个方法适用面窄但非常方便。
费用流：
费用流在省选难度考点集中在流量平衡上。
bzoj 1061 志愿者招募
只要看出通过某种变换，原题变成了每个变量只出现两次，且一正一负的方程组，那么我们就可以将每个变量看做一条边，通过费用流解决。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 100000
#define MAXE MAXV*20
#define MAXV MAXN
#define INF 0x3f3f3f3f
struct Edge
{
int np,val,cost;
Edge *next,*neg;
}E[MAXE],*V[MAXV];
int sour=,sink=;
int tope=-;
void addedge(int x,int y,int z,int c)
{
// cout<<"Add:"<<x<<" "<<y<<" "<<z<<" "<<c<<endl;
E[++tope].np=y;
E[tope].val=z;
E[tope].cost=c;
E[tope].next=V[x];
V[x]=&E[tope]; E[++tope].np=x;
E[tope].val=;
E[tope].cost=-c;
E[tope].next=V[y];
V[y]=&E[tope]; V[x]->neg=V[y];
V[y]->neg=V[x];
}
int dis[MAXN];
int q[MAXN*];
int vis[MAXN],vistime=;
int prv[MAXN];
Edge *prve[MAXN];
int spfa(int now)
{
int head=-,tail=;
Edge *ne;
memset(dis,INF,sizeof(dis));
dis[now]=;
q[]=now;
vis[now]=++vistime;
while (head<tail)
{
now=q[++head];
vis[now]=;
for (ne=V[now];ne;ne=ne->next)
{
if (ne->val && dis[ne->np]>dis[now]+ne->cost)
{
dis[ne->np]=dis[now]+ne->cost;
prv[ne->np]=now;
prve[ne->np]=ne;
if (vis[ne->np]!=vistime)
q[++tail]=ne->np;
}
}
}
return dis[sink]!=INF;
}
pair<int,int> cost_flow()
{
pair<int,int> res;
while (spfa(sour))
{
int mxflow=INF;
for (int x=sink;x!=sour;x=prv[x])
mxflow=min(mxflow,prve[x]->val);
for (int x=sink;x!=sour;x=prv[x])
prve[x]->val-=mxflow,prve[x]->neg->val+=mxflow;
res.first+=mxflow;
res.second+=mxflow*dis[sink];
}
return res;
}
int a[MAXN]; int main()
{
//freopen("input.txt","r",stdin);
int n,m,x,y,z;
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++)
scanf("%d",a+i);
for (int i=;i<=n+;i++)
{
addedge(+i-,+i,INF,);
}
for (int i=;i<=n+;i++)
{
if (a[i]>a[i-])
addedge(+i,sink,a[i]-a[i-],);
else
addedge(sour,+i,a[i-]-a[i],);
}
for (int i=;i<m;i++)
{
scanf("%d%d%d",&x,&y,&z);
addedge(+y+,+x,INF,z);
}
pair<int,int> res;
res=cost_flow();
printf("%d\n",res.second);
}
bzoj 1061
bzoj 1070：易到一看就是贪心的题目，但是贪心又无法解决。其实贪心和网络流（费用流）在多数情况是可以互换的。
题解传送门：http://www.cnblogs.com/mhy12345/p/4417083.html
暂且写到这儿，还有什么题目以后再补充。