网络流嘛，怎么看都是一堆逗逼题嘛，反正遇到还是都做不起嘛。。。。
网络流的模板非常简单，难点都在于建图，网络流的建图解决问题范围之广，下至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=1; int sour=0,sink=1; 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=0; E[tope].next=V[y]; V[y]=&E[tope]; E[tope].neg=&E[tope-1]; E[tope-1].neg=&E[tope]; } int q[MAXV],lev[MAXV]; int vis[MAXV],bfstime=0; bool bfs() { int head=-1,tail=0; Edge *ne; lev[sour]=1; vis[sour]=++bfstime; q[0]=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]]+1; } } return vis[sink]==bfstime; } int dfs(int now,int maxf) { int ret=0,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]+1)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]=-1; return ret; } int dinic() { int ret=0; 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=0; scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",va+i); for (int i=1;i<=n;i++) scanf("%d",vb+i); for (int i=1;i<=n;i++)//x[i]==0?va[i]:vb[i] { res+=va[i]; res+=vb[i]; addedge(sour,i+2,va[i]);//x[i]==1?-va[i] -> max(0,x[i]-0)*va[i]; addedge(i+2,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=1;i<=m;i++) { scanf("%d",&t); scanf("%d%d",&ca,&cb); res+=ca;res+=cb; ya=i+2+n; yb=i+2+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=0;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,2+p,INF); addedge(2+p,yb,INF); } } printf("%d ",res-dinic()); }
在看另一道题：
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=0,sink=1; int tope=-1; 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=0; 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*20]; int vis[MAXN],vistime=0; int prv[MAXN]; Edge *prve[MAXN]; int spfa(int now) { int head=-1,tail=0; Edge *ne; memset(dis,INF,sizeof(dis)); dis[now]=0; q[0]=now; vis[now]=++vistime; while (head<tail) { now=q[++head]; vis[now]=0; 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=1;i<=n;i++) scanf("%d",a+i); for (int i=1;i<=n+1;i++) { addedge(2+i-1,2+i,INF,0); } for (int i=1;i<=n+1;i++) { if (a[i]>a[i-1]) addedge(2+i,sink,a[i]-a[i-1],0); else addedge(sour,2+i,a[i-1]-a[i],0); } for (int i=0;i<m;i++) { scanf("%d%d%d",&x,&y,&z); addedge(2+y+1,2+x,INF,z); } pair<int,int> res; res=cost_flow(); printf("%d ",res.second); }
bzoj 1070：易到一看就是贪心的题目，但是贪心又无法解决。其实贪心和网络流（费用流）在多数情况是可以互换的。
题解传送门：http://www.cnblogs.com/mhy12345/p/4417083.html
暂且写到这儿，还有什么题目以后再补充。