- 提出这个部分主要是针对最大流最小割的几个典型应用，而这几点在算导和黑书上没有详细描述。
- 这里沿用《实用算法》上的三个典型应用：图的割切，图的连通度和图的边连通度。顺便把多源多汇的可行流，容量上下界的最大流，最小路径覆盖[多源多汇的改造问题]，以及最小费用最大流问题一起描述并实现了。[最小费用问题也可以用线型规划来解，就像差分也可以不用图而用线型规划来解，都是相通的。]
- 这块有点太理论了，不过还是都实现一遍吧，最大流的难点在建模，编程都还在其次。但编程是基本功，还在其次的问题都不能秒杀，谈什么建模呢？
1.最小割(S,T)的解法：当流稳定时，换言之，从S出发无法找到一个前向流，使得当前流f再增加。定义残存前向图Df，边集Ef={(u,v)属于E,c(u,v)-f(u,v)>0}，即正向流集，其点集V即为所求！
2.图连通度K(G),定义K(G)为：K(G)=顶点数-1，G为双向完全图；K(G)=Min{P(a,b)}，a,b不相邻，G为非双向完全图。
- 构造流图D：将原图中的u,v分裂为两个等效顶点，以单位容量边相连，将原来的边映射为+无穷边。
- 求出不相邻点a到b的最大流，以及对应的割顶集S。
#include <assert.h>
#include <iostream>
#include <fstream>
const int MAXN=30, MAXE=200;
typedef struct Edge{
int i, j, next, op, f, c;
};
Edge es[MAXE];
int eid=0, n, en, first[MAXN], pre[MAXN], ptr[MAXN], first1[MAXN], queue[MAXN], ansp[MAXN];
bool visited[MAXN];
bool map[MAXN][MAXN];
bool ss[MAXN];
void createGraph();
void addEdge(int i, int j, int c);
void Dicnic(int sv, int st);
void bfslevel(int sv, int st);
void dfs_maxflow(int sv, int st);
void dfsforS(int v);
void createGraph(){
ifstream in("input.txt");
if(!in) exit(EXIT_FAILURE);
cin.rdbuf(in.rdbuf());
//read in for n, e
cin>>n>>en;
int x, y;
//clr for all previous list
eid=0, memset((void*)first, 0xff, sizeof(first)), memset((void*)map, 0, sizeof(map));
for(int i=0; i<n; i++) addEdge(i, i+n, 1);//i -> i+n in weight of 1
for(int i=0; i<en; i++){
cin>>x>>y, map[x][y]=map[y][x]=true;
addEdge(x+n, y, INT_MAX), addEdge(y+n, x, INT_MAX);
}
in.close();
}
es[eid].i=i, es[eid].j=j, es[eid].f=0, es[eid].c=c;
es[eid].next=first[i], first[i]=eid, es[eid].op=eid+1; eid++;
es[eid].i=j, es[eid].j=i, es[eid].f=0, es[eid].c=-1;
es[eid].next=first[j], first[j]=eid, es[eid].op=eid-1; eid++;//here:bugs，开始写成了后减，精力有点不集中！
}
void Dicnic(int sv, int st){
while(true){
bfslevel(sv, st);
if(pre[st]==INT_MAX) return;
dfs_maxflow(sv, st);
}
}
for(int i=0; i<2*n; i++) pre[i]=INT_MAX;
int top=0, size=1; queue[0]=sv, pre[sv]=0;//here:bugs注意源点赋值
while(top<size){
int cn=queue[top++];//here!bugs队列的头处理
if(cn==st) return;
for(int e=first[cn]; e!=-1; e=es[e].next){
if(es[e].c>es[e].f||(es[e].c==-1&&es[e].f>0)){
if(pre[es[e].j]>pre[cn]+1){
queue[size++]=es[e].j, pre[es[e].j]=pre[cn]+1;
}
}
}
}
}
memcpy((void*)first1, (void*)first, sizeof(first));
memset((void*)visited, 0, sizeof(visited));
int top=0; queue[0]=sv;
while(top>-1){
if(queue[top]==st){
int fmin=INT_MAX, value;
for(int i=top; i>0; i–){
if(es[ptr[queue[i]]].c>es[ptr[queue[i]]].f){
if((value=es[ptr[queue[i]]].c-es[ptr[queue[i]]].f)<fmin) fmin=value;
}
if(es[ptr[queue[i]]].c==-1&&es[ptr[queue[i]]].f>0){
if((value=es[ptr[queue[i]]].f)<fmin) fmin=value;
}
}
//update the maxflow
for(int i=top; i>0; i–){
if(es[ptr[queue[i]]].c>es[ptr[queue[i]]].f)
es[ptr[queue[i]]].f+=fmin, es[es[ptr[queue[i]]].op].f+=fmin;
if(es[ptr[queue[i]]].c==-1&&es[ptr[queue[i]]].f>0)
es[ptr[queue[i]]].f-=fmin, es[es[ptr[queue[i]]].op].f-=fmin;
}
return;
}
else{//dfs for maxflow
int tp=queue[top], tmp=first1[tp];
for(;tmp!=-1;tmp=es[tmp].next){
if(!visited[es[tmp].j]){
if((es[tmp].c>es[tmp].f||(es[tmp].c==-1&&es[tmp].f>0))&&pre[es[tmp].j]==pre[tp]+1){
first1[tp]=es[tmp].next;
queue[++top]=es[tmp].j, ptr[es[tmp].j]=tmp;
break;
}//if
}//if
}//for
if(tmp==-1){visited[tp]=true; top–;}
}
}
}
ss[v]=true;
for(int e=first[v]; e!=-1; e=es[e].next){//here:bugs
if(!ss[es[e].j]&&es[e].c>es[e].f) dfsforS(es[e].j);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
createGraph();
bool bf=true;
for(int i=1; i<n; i++){
for(int j=i+1; j<n; j++){
assert(i!=j);
if(!map[i][j]){bf=false; break;}
}
if(!bf) break;
}
if(bf){//bi-connected graph
cout<<n-1<<endl;
for(int i=0; i<n; i++) cout<<i<<" ";
cout<<endl;
goto jmp;
}
else{//for k-connected graph
int ans=0;
for(int vs=n; vs<2*n; vs++){
for(int vt=0; vt<n; vt++){
if(vs-n!=vt&&!map[vs-n][vt]){//maxflow for between vs and vt
for(int i=0; i<eid; i++) es[i].f=0;
Dicnic(vs, vt);
int k=0;
for(int i=first[vs]; i!=-1; i=es[i].next) k+=es[i].f;
if(k>ans){
ans=k;
memset((void*)ss, 0, sizeof(ss));
dfsforS(vs);
int t=0;
for(int i=0; i<n; i++)
if(ss[i]&&!ss[i+n]) ansp[t++]=i;
}//if
}
}
}
cout<<ans<<endl;
for(int i=0; i<ans; i++) cout<<ansp[i]<<" ";
cout<<endl;
}
return 0;
}
- 设在无向图中，将原有边e(u,v)映射为e’=(u, v), e”=(v,u)，其容量均为1， 而有向图，则直接设置存在边容量为1。[这个和最大流模型是保持一致的]
- 排除特殊的完全图情况，求出最大流，进而dfs求出在原图中的桥集
#include <assert.h>
#include <iostream>
#include <fstream>
typedef struct Edge{
int i, j, next, op, c, f;
};
typedef struct Bridge{
int i, j;
};
Edge es[MAXE];
Bridge bs[MAXE];
int eid=0, nv, ev, first[MAXN], first1[MAXN], pre[MAXN], ptr[MAXN], queue[MAXN];
bool visited[MAXN], ss[MAXN], map[MAXN][MAXN];
void createGraph();
void addEdge(int i, int j, int c);
void Dicnic(int sv, int st);
void bfslevel(int sv, int st);
void dfs_maxflow(int sv, int st);
void dfsforS(int u);
void createGraph(){
ifstream in("input.txt");
if(!in) exit(EXIT_FAILURE);
cin.rdbuf(in.rdbuf());
cin>>nv>>ev;
int x, y;
eid=0, memset((void*)first, 0xff, sizeof(first)), memset((void*)map, 0, sizeof(map));
for(int i=0; i<ev; i++){
cin>>x>>y, x–, y–;
map[x][y]=map[y][x]=true, addEdge(x, y, 1), addEdge(y, x, 1);
}
}
void addEdge(int i, int j, int c){
es[eid].i=i, es[eid].j=j, es[eid].f=0, es[eid].c=c;
es[eid].next=first[i], first[i]=eid, es[eid].op=eid+1; eid++;
es[eid].i=j, es[eid].j=i, es[eid].f=0, es[eid].c=-1;
es[eid].next=first[j], first[j]=eid, es[eid].op=eid-1; eid++;
}
while(true){
bfslevel(sv, st);
if(pre[st]==INT_MAX) return;
dfs_maxflow(sv, st);
}
}
for(int i=0; i<nv; i++) pre[i]=INT_MAX;
int top=0, size=1; queue[0]=sv, pre[sv]=0;
while(top<size){
int cn=queue[top++];
if(cn==st) return;
for(int e=first[cn]; e!=-1; e=es[e].next){
if((es[e].c>es[e].f||(es[e].c==-1&&es[e].f>0))&&pre[es[e].j]>pre[cn]+1)//here: bugs
queue[size++]=es[e].j, pre[es[e].j]=pre[cn]+1;
}
}
}
memcpy((void*)first1, (void*)first, sizeof(first));
memset((void*)visited, 0, sizeof(visited));
int top=0; queue[0]=sv;
while(top>-1){
if(queue[top]==st){
int fmin=INT_MAX, value;
for(int i=top; i>0; i–){
if(es[ptr[queue[i]]].c>es[ptr[queue[i]]].f){
if((value=es[ptr[queue[i]]].c-es[ptr[queue[i]]].f)<fmin) fmin=value;
}
if(es[ptr[queue[i]]].c==-1&&es[ptr[queue[i]]].f>0){
if((value=es[ptr[queue[i]]].f)<fmin) fmin=value;
}
}
for(int i=top; i>0; i–){
if(es[ptr[queue[i]]].c>es[ptr[queue[i]]].f){
es[ptr[queue[i]]].f+=fmin, es[es[ptr[queue[i]]].op].f+=fmin;
}
if(es[ptr[queue[i]]].c==-1&&es[ptr[queue[i]]].f>0){
es[ptr[queue[i]]].f-=fmin, es[es[ptr[queue[i]]].op].f-=fmin;
}
}
return;
}
else{//for first1 comparsion
int tp=queue[top], tmp=first1[tp];
for(;tmp!=-1;tmp=es[tmp].next){
if(!visited[es[tmp].j])
if((es[tmp].c>es[tmp].f||(es[tmp].c==-1&&es[tmp].f>0))&&pre[es[tmp].j]==pre[tp]+1){
queue[++top]=es[tmp].j, ptr[es[tmp].j]=tmp;
break;
}
}//for
if(tmp==-1){visited[tp]=true; top–;}
}
}
}
ss[u]=true;
for(int e=first[u]; e!=-1; e=es[e].next){
if(!ss[es[e].j]&&es[e].c>es[e].f) dfsforS(es[e].j);
}
}
{
createGraph();
bool bf=true;
for(int i=0; i<nv; i++){
for(int j=i+1; j<nv; j++){
if(!map[i][j]){bf=false; break;}
}
}
if(bf){//full-connencted
cout<<nv-1<<endl;
for(int i=1; i<nv; i++) cout<<"0 "<<i<<endl;
goto jmp;
}
else{//for the intialization of edages
int ans=0;
for(int s=0; s<nv; s++){
for(int t=0; t<nv; t++){
if(s!=t&&!map[s][t]){//find non-adjancent two vertexs
for(int i=0; i<eid; i++) es[i].f=0;
Dicnic(s, t);
int k=0;
for(int e=first[s]; e!=-1; e=es[e].next) k+=es[e].f;
if(k>ans){//find the according bridge
ans=k;
memset((void*)ss, 0, sizeof(ss));
dfsforS(s); int t=0;
for(int i=0; i<nv; i++){
for(int j=0; j<nv; j++){
if(ss[i]&&!ss[j]&&map[i][j]) bs[t].i=i, bs[t++].j=j;
}
}
}//if
}//if
}//for vt
}//for vs
cout<<ans<<endl;
for(int i=0; i<ans; i++) cout<<bs[i].i<<" "<<bs[i].j<<endl;
}
return 0;
}
- Ford-Fulkerson增广最短路算法[Successive Shortest Path]：在最大流系统中加入单位流量的费用因子，然后求在最小费用基础上的最大流，输出为总的输送费用B(F)=Sum(Bij*Fij).这个思路挺典型的，感觉有点不像是最大流，倒像是最短路+增量算法的问题。
- 对于G求出其从S到T的最短路[Bellman-Ford]，初始时F=0。
- 在F(k-1)基础上进行流增量，实际上是求出可达最短路上的瓶颈流量。尤其最短路时已经求出了累积的最小费用，直接用l[t]*瓶颈流量即可。
代码框架：[实用上的框架]
Successive Shortest Path
1 Establish a feasible flow x when F=0
2 while ( Gx contains any shortest path in F(k-1) ) do
3 find the shortest path from s to t
4
5 add the cost from the shortest path from s to t in l[t]
6 find the bottleneck of flow(k-1) and the sum of cost is l[t]*|bottleneck|
- 消圈算法[Cycle Canceling]：网络G的最大流是G的一个最小费用流的充要条件是，最大流的残图中不含负费用圈。
伪代码框架：[引自 Zealint ‘s Minimum Cost Flow, Part 2: Algorithms ]
Cycle-Canceling
1 Establish a feasible flow x in the network
2 while ( Gx contains a negative cycle ) do
3 identify a negative cycle W
4
5 augment units of flow along the cycle W
6 update Gx
一个练手的基本题目：在如下图中，求出其最小费用最大流。
0 1 10 4
0 2 8 1
2 1 5 2
1 3 2 6
2 3 10 3
1 4 7 1
3 4 4 2
- Cycle cancel算法实现：实用的模型确实很强，那种模型的处理，使得正流和负流统一起来了！然后沿正向流的增加[残图中g的增加]和负流的处理都一致料。呵呵，最后的费用流只需要把正向流的集合跑一次即可！来分析下算法复杂度：Bellman-Ford的负圈测试O(VE),每条边的容量上限M，费用上限为C，因此最大流的费用为mCM,统一之复杂度为O(E^2VCM).
代码实现：[可用为模板]
#include <iostream>
#include <fstream>
using namespace std;
//Cycle-canceling Algorithm
//Code Skeleton
//1 Establish a feasible flow x in the network
//2 while ( Gx contains a negative cycle ) do
//3 identify a negative cycle W
//4
//5 augment units of flow along the cycle W
//6 update Gx
//declaration
typedef struct Edge{
int i, j, f, c, w, op, next;//using uniform Edge presetation
};
const int MAXN=20, MAXE=400;
Edge es[MAXE];
int eid=0, first[MAXN], hv[MAXN], ev[MAXN], l[MAXN], w[MAXN], pre[MAXN], ptr[MAXN];//for bellman-ford loop
int nv, ne;
//declaration
void createGraph();
void addEdge(int start, int end, int cap, int cost);
//maxflow algorithm
void highpreflow();
void initialize();
void discharge(int u);
bool relabel(int u);
bool push(int eid);
//implementation
void createGraph(){
ifstream in("input.txt");
if(!in) exit(EXIT_FAILURE);
cin.rdbuf(in.rdbuf());
//read in data and establish the graph
cin>>nv>>ne; eid=0, memset((void*)first, 0xff, sizeof(first));
int start, end, cap, cost;
for(int i=0; i<ne; i++)
cin>>start>>end>>cap>>cost, addEdge(start, end, cap, cost);
}
void addEdge(int start, int end, int cap, int cost){
if(!cap) return;
es[eid].i=start, es[eid].j=end, es[eid].f=0, es[eid].c=cap, es[eid].w=cost;
es[eid].next=first[start], first[start]=eid, es[eid].op=eid+1; eid++;
es[eid].i=end, es[eid].j=start, es[eid].f=0, es[eid].c=-1, es[eid].w=-cost;
es[eid].next=first[end], first[end]=eid, es[eid].op=eid-1; eid++;
}
void highpreflow(){
initialize();
int pos=0, u=l[pos];
while(u!=-1){
int oldh=hv[u];
discharge(u);
if(oldh!=hv[u]){
if(pos!=0) l[pos]^=l[0], l[0]^=l[pos], l[pos]^=l[0];
pos=0;
}
u=l[++pos];
}
}
void initialize(){
memset((void*)hv, 0, sizeof(hv)), memset((void*)ev, 0, sizeof(ev));
memset((void*)l, 0xff, sizeof(l));
for(int i=0; i<nv-2; i++) l[i]=i+1;
hv[0]=nv-1;
for(int i=first[0]; i!=-1; i=es[i].next){
if(es[i].c>0){
es[i].f+=es[i].c, es[es[i].op].f+=es[i].c;
ev[es[i].j]+=es[i].c, ev[0]-=es[i].c;
}
}
}
bool relabel(int u){
if(ev[u]<=0) return false;
int hmin=INT_MAX; bool minV=true;
for(int e=first[u]; e!=-1; e=es[e].next){
if(es[e].c>es[e].f||(es[e].c==-1&&es[e].f>0)){
if(hv[es[e].j]<hv[u]) minV=false;
if(hv[es[e].j]<hmin) hmin=hv[es[e].j];
}
}
if(minV&&hmin<=nv){hv[u]=hmin+1; return true;}
return false;
}
bool push(int eid){//es[eid].i->es[eid].j
if(ev[es[eid].i]<=0||hv[es[eid].i]!=hv[es[eid].j]+1) return false;
int dt;
if(es[eid].c>es[eid].f){
dt=min(ev[es[eid].i], es[eid].c-es[eid].f);
es[eid].f+=dt, es[es[eid].op].f+=dt;
ev[es[eid].i]-=dt, ev[es[eid].j]+=dt;
return true;
}
if(es[eid].c==-1&&es[eid].f>0){
dt=min(ev[es[eid].i], es[eid].f);
es[eid].f-=dt, es[es[eid].op].f-=dt;
ev[es[eid].i]-=dt, ev[es[eid].j]+=dt;
return true;
}
return false;
}
void discharge(int u){
int cur=first[u];
while(ev[u]>0){
if(cur==-1) relabel(u), cur=first[u];
else if((es[cur].c>es[cur].f||(es[cur].c==-1&&es[cur].f>0))&&hv[u]==hv[es[cur].j]+1)
push(cur);
else cur=es[cur].next;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
createGraph();
highpreflow();
//cycle cancel
bool cycle=false;
do{//cycle cancel logic
w[0]=0, memset((void*)pre, 0xff, sizeof(pre));
for(int i=1; i<nv; i++) w[i]=INT_MAX; cycle=false;
int start=-1, fmin=INT_MAX;
for(int i=1; i<nv; i++){
for(int e=0; e<eid; e++){
if(es[e].c>es[e].f||(es[e].c==-1&&es[e].f>0))//in the residental graph
if(w[es[e].i]!=INT_MAX&&w[es[e].i]+es[e].w<w[es[e].j]) w[es[e].j]=w[es[e].i]+es[e].w, pre[es[e].j]=es[e].i, ptr[es[e].j]=e;
}
}
for(int i=1; i<nv; i++){
for(int e=0; e<eid; e++){
if(es[e].c>es[e].f||(es[e].c==-1&&es[e].f>0))//in the residental graph
if(w[es[e].i]!=INT_MAX&&w[es[e].i]+es[e].w<w[es[e].j]){ start=es[e].j, cycle=true; break;}
}//Bellman-Ford一行不差的！
if(cycle) break;//existing one minus cycle
}
if(!cycle) break;//no-minus cycle in the existing system
//here: if self-loop? ignore this case
int nxt=pre[start], value;
do{
if(es[ptr[nxt]].c>es[ptr[nxt]].f){//here: w’s value
if((value=es[ptr[nxt]].c-es[ptr[nxt]].f)<fmin) fmin=value;
}
if(es[ptr[nxt]].c==-1&&es[ptr[nxt]].f>0){
if((value=es[ptr[nxt]].f)<fmin) fmin=value;
}//please check
}while(nxt!=pre[start]);
//update the minus cycle
nxt=pre[start];
do{//bugs : in the residental graph, decreas the flow on this direction, increase the opposite direction
if(es[ptr[nxt]].c>es[ptr[nxt]].f)
es[ptr[nxt]].f+=fmin, es[es[ptr[nxt]].op].f+=fmin;
else if(es[ptr[nxt]].c==-1&&es[ptr[nxt]].f>0)
es[ptr[nxt]].f-=fmin, es[es[ptr[nxt]].op].f-=fmin;
/*assert(es[ptr[nxt]].f>=0&&es[es[ptr[nxt]].op].f>=0);*/
nxt=pre[nxt];
}while(nxt!=pre[start]);//这个地方有点搞，呵呵！闪了一下，证明：存在圈那么从start开始一定有一个出，一个入，OK，用pre验证即可。
}while(cycle);
//MIT上说要再走一次dfs来看是否确实无圈！
//find the minmal cost flow along the forward-flow
int forwardflow=0;
for(int i=0; i<eid; i++){
if(es[i].c>0) forwardflow+=es[i].f*es[i].w;
}
cout<<forwardflow<<endl;
return 0;
}
- Successive Shortest Path算法实现：每次找出更新流后的最小费用路径，找出瓶颈流以及用w[st]表示其最短路径的费用长度，累计即是最小费用。算法复杂度：Bellman-Ford的负圈测试O(VE),每条边的容量上限M，费用上限为C，因此每次找最小路径O(S(m,n,C)),统一之复杂度为O(MS(m,n,C)).
代码实现：[可用为模板]
#include <iostream>
#include <fstream>
using namespace std;
/* template from Top coder, implementation refer to practical alogrithm.
Successive Shortest Path
1 Transform network G by adding source and sink
2 Initial flow x is zero
3 while ( Gx contains a path from s to t ) do
4 Find any shortest path P from s to t
5 Augment current flow x along P
6 update Gx
*/
const int MAXN=20, MAXE=400;
typedef struct Edge{
int i, j, next, op, f, c, w;
}Edge;
Edge es[MAXE];
int eid=0, first[MAXN], w[MAXN],/*accumulated value*/ pre[MAXN], ptr[MAXN];
int nv, ne;
//declaration
void addEdge(int i, int j, int c, int w);
int expandPath(int sv, int st);
void createGraph();
//implementation
void addEdge(int i, int j, int c, int w){
if(!c) return;
es[eid].i=i, es[eid].j=j, es[eid].c=c, es[eid].w=w, es[eid].f=0;
es[eid].next=first[i], first[i]=eid, es[eid].op=eid+1; eid++;
es[eid].i=j, es[eid].j=i, es[eid].c=-1, es[eid].w=-w, es[eid].f=0;
es[eid].next=first[j], first[j]=eid, es[eid].op=eid-1; eid++;
}
void createGraph(){
ifstream in("input.txt");
if(!in) exit(EXIT_FAILURE);
cin.rdbuf(in.rdbuf());
cin>>nv>>ne;eid=0, memset((void*)first, 0xff, sizeof(first));
int start, end, cap, costw;
for(int i=0; i<ne; i++)
cin>>start>>end>>cap>>costw, addEdge(start, end, cap, costw);
}
int expandPath(int sv, int st){
memset((void*)pre, 0xff, sizeof(int)*nv);
for(int i=0; i<nv; i++) w[i]=INT_MAX;
pre[sv]=sv,w[sv]=0; bool change=false;
do{
change=false;
for(int i=1; i<nv; i++){
for(int e=0; e<eid; e++){//flow may be changed during process
if(pre[es[e].i]!=-1){
if(es[e].c>es[e].f)
if(w[es[e].i]+es[e].w<w[es[e].j]) w[es[e].j]=w[es[e].i]+es[e].w, pre[es[e].j]=es[e].i, ptr[es[e].j]=e, change=true;
if(es[e].c==-1&&es[e].f>0)
if(w[es[e].i]+es[e].w<w[es[e].j]) w[es[e].j]=w[es[e].i]+es[e].w, pre[es[e].j]=es[e].i, ptr[es[e].j]=e, change=true;
}
}
}
}while(change);//if change then we continue change
//if we can’t from sv to st;
if(pre[st]==-1) return 0;
int i=st, a=INT_MAX, value;
for(;i!=sv;i=pre[i]){
if(es[ptr[i]].c>es[ptr[i]].f){//here:bugs i->ptr[i]
if((value=es[ptr[i]].c-es[ptr[i]].f)<a) a=value;
}
if(es[ptr[i]].c==-1&&es[ptr[i]].f>0){
if((value=es[ptr[i]].f)<a) a=value;
}
}
return a;
}
int _tmain(int argc, _TCHAR* argv[])
{
createGraph();
int a=expandPath(0, nv-1), aflow=0, sv=0, st=nv-1;
while(a){
for(int i=st;i!=sv;i=pre[i]){//change the flow
if(es[ptr[i]].c>es[ptr[i]].f) es[ptr[i]].f+=a, es[es[ptr[i]].op].f+=a;
if(es[ptr[i]].c==-1&&es[ptr[i]].f>0) es[ptr[i]].f-=a, es[es[ptr[i]].op].f-=a;
}
aflow+=w[st]*a;
a=expandPath(0, nv-1);
}
cout<<aflow<<endl;
return 0;
}
玫瑰花茶的下午 
Leave a comment