#include <cstdio>
#include <cstring>
#define min(x,y) (x>y?y:x)
int pre[],q[];
int F[][];
int n,nc,np,m,s,t,all;
int MaxFlow(int s, int t){
int ans=;
while(){
memset(pre,,sizeof(pre));
int head=,tail=;
q[++tail]=s;
while(head<tail&&pre[t]==){
int cur=q[++head];
for(int i=; i<=n; i++)
if(F[cur][i]>&&pre[i]==){
pre[i]=cur;
q[++tail]=i;
}
}
if(pre[t]==) break;
int minF=;
for(int i=t; i!=s; i=pre[i])
minF=min(minF,F[pre[i]][i]);
for(int i=t; i!=s; i=pre[i])
{
F[pre[i]][i]-=minF;
F[i][pre[i]]+=minF;
}
ans+=minF;
}
return ans;
}
int main()
{
int x,y,z;
while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF){
all=;
memset(F,,sizeof(F));
s=n+;
t=n+;
n=n+;
for(int i=; i<m; i++){
while(getchar()!='(') ;
scanf("%d,%d)%d",&x,&y,&z);
F[x+][y+]=z;
}
for(int i=; i<np; i++){
while(getchar()!='(') ;
scanf("%d)%d",&x,&z);
F[s][x+]=z;
}
for(int i=; i<nc; i++){
while(getchar()!='(') ;
scanf("%d)%d",&x,&z);
F[x+][t]=z;
}
printf("%d\n",MaxFlow(s,t));
}
return ;
}
Dinic用DFS实现：360ms
#include <cstdio>
#include <cstring>
#define min(x,y) ((x)>(y)?(y):(x))
#define N 105
#define M 10005
int n,np,nc,m,all,s,t;
int d[N],be[N];
struct Edge{
int x,y,c,next;
}e[M*];
void add(int x, int y, int z)//需保证相反边第一个为偶数
{
e[all].x=x; e[all].y=y; e[all].c=z;
e[all].next=be[x];
be[x]=all;
all++;
e[all].x=y; e[all].y=x; e[all].c=;
e[all].next=be[y];
be[y]=all;
all++;
}
bool BFS(int s, int t)
{
memset(d,-,sizeof(d));
int head=,tail=,q[N];
q[++tail]=s;
d[s]=;
while(head<tail){
int cur=q[++head];
for(int i=be[cur]; i!=-; i=e[i].next)
if(e[i].c> && d[e[i].y]==-){
d[e[i].y]=d[cur]+;
q[++tail]=e[i].y;
}
}
return d[t]!=-;
}
int DFS(int cur, int minc)
{
if(cur==t) return minc;//表示路径上该点前方最小容量
int ans=,tmp;//ans表示该点要增大的流
for(int i=be[cur]; i!=-; i=e[i].next)
if(e[i].c> && d[e[i].y]==d[cur]+ && (tmp=DFS(e[i].y,min(minc-ans,e[i].c))))//多路增广很快 因为不用返回到s 容易证明能保证minc>0
{
e[i].c-=tmp;
e[i^].c+=tmp;
ans+=tmp;
}
if(ans==) d[cur]=-;//关键的一句话 否则超时 用于多路增广
return ans;
}
int Dinic(int s, int t)
{
int ans=,tmp;
while(BFS(s,t)){
while(tmp=DFS(s,))
ans+=tmp;
}
return ans;
}
int main()
{
int x,y,z;
while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF){
all=;
memset(be,-,sizeof(be));
s=n;
t=n+;
n=n+;
for(int i=; i<m; i++){
while(getchar()!='(') ;
scanf("%d,%d)%d",&x,&y,&z);
add(x,y,z);
}
for(int i=; i<np; i++){
while(getchar()!='(') ;
scanf("%d)%d",&x,&z);
add(s,x,z);
}
for(int i=; i<nc; i++){
while(getchar()!='(') ;
scanf("%d)%d",&x,&z);
add(x,t,z);
}
printf("%d\n",Dinic(s,t));
}
return ;
}
Dinic用栈模拟递归实现：63ms
#include <cstdio>
#include <cstring>
#define min(x,y) ((x)>(y)?(y):(x))
#define N 105
#define M 10005
int n,np,nc,m,all,s,t;
int d[N],be[N];
struct Edge{
int x,y,c,next;
}e[M*];
void add(int x, int y, int z)//需保证相反边第一个为偶数
{
e[all].x=x; e[all].y=y; e[all].c=z;
e[all].next=be[x];
be[x]=all;
all++;
e[all].x=y; e[all].y=x; e[all].c=;
e[all].next=be[y];
be[y]=all;
all++;
}
bool BFS(int s, int t)
{
memset(d,-,sizeof(d));
int head=,tail=,q[N];
q[++tail]=s;
d[s]=;
while(head<tail){
int cur=q[++head];
for(int i=be[cur]; i!=-; i=e[i].next)
if(e[i].c> && d[e[i].y]==-){
d[e[i].y]=d[cur]+;
q[++tail]=e[i].y;
}
}
return d[t]!=-;
}
int Dinic(int s, int t)//防止爆栈 用stack模拟递归
{
int ans=;
int stack[N],top;
int begin[N];
while(BFS(s,t))
{
memcpy(begin,be,sizeof(be));
int cur=s;
top=;//dfs开始 清空栈
while()
{
if(cur==t){
int minc=,mini;
for(int i=; i<top; i++)
if(minc>e[stack[i]].c)
{
minc=e[stack[i]].c;
mini=i;//以便之后回到这继续增广
}
for(int i=; i<top; i++)
{
e[stack[i]].c-=minc;
e[stack[i]^].c+=minc;//第一个二进制取反 即取相反边
}
ans+=minc;
top=mini;
cur=e[stack[mini]].x;
}
for(int i=begin[cur]; i!=-; begin[cur]=i=e[begin[cur]].next)
if(e[i].c> && d[e[i].y]==d[e[i].x]+) break;
if(begin[cur]!=-){
stack[top++]=begin[cur];
cur=e[begin[cur]].y;
}else{
if(top==) break;
d[cur]=-;//当前节点不在增广路中 删除
cur=e[stack[--top]].x;//回溯
}
}
}
return ans;
}
int main()
{
int x,y,z;
while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF){
all=;
memset(be,-,sizeof(be));
s=n;
t=n+;
n=n+;
for(int i=; i<m; i++){
while(getchar()!='(') ;
scanf("%d,%d)%d",&x,&y,&z);
add(x,y,z);
}
for(int i=; i<np; i++){
while(getchar()!='(') ;
scanf("%d)%d",&x,&z);
add(s,x,z);
}
for(int i=; i<nc; i++){
while(getchar()!='(') ;
scanf("%d)%d",&x,&z);
add(x,t,z);
}
printf("%d\n",Dinic(s,t));
}
return ;
}
之前一题poj1459是经典最大流题目,倒是想要回顾一下，顺便将书中证明简要摘出：（哈哈）
而网络流的增广路与二分图还是有相当的差别的,那么如何来判断网络流的流量最大呢,那么得清楚如何使得当前网络流的流量再次增大,首先显而易见的就是直接用bfs找出前进路径中所能增加的最大流量,这个是毋庸置疑的.只有这种情况吗?我们只考虑了前向边,而后向边得想想是否能够增加的余地.
先看看这个图 (时间不够先粗略画这)
仔细看s-1-2-t,是否能增加,用s-1的流量顶替2-1的流量后2-t的流量自然增加,
故我们只需不断的找出这两种增广路径,然后更新即可.
因此：
(前向边:路径上边方向是从s指向t的边;后向边:路径上边方向从t指向s的边)
对于路径上所有前向边(u,v)满足f(u,v)<c(u,v)且所有后向边(v,u)满足f(v,u)>0,则该路径称为增广路径.
证明:只要当前网络中不存在从s到t的增广路径,则当前流为最大流.
要证明这个定理,我们得先引入最大流最小割定理.
割的概念:对于网络流图D=(V,E,C)的所有节点集,将该节点集分为集合S和T,且其中源点s∈集合S,汇点t属于T,对于图上满足u∈S,v∈T的所有边(u,v)的集合称为割,其中割中每条边的容量和称为割的容量.而容量最小的割称为最小割.
最大流最小割定理即:在一个给定的网络流图上,最大流等于最小割的容量.
证明:
设网络流图D的网络流f使得流量达到最大.
定义割(S,T):
1.源点s∈S
2.若u∈S,且f(u,v)<c(u,v),则v∈S
3.若u∈S,且f(v,u)>0,则u∈S
显然,源点t∈T,否则若t∈S,则由割的定义,必然从s到t中存在一条增广路径,则与f为最大流矛盾,因此t∈T.故从s到t间的所有路径必然都需要从S到T即需要经过割中的边,又由割(S,T)的定义,f(u,v)=c(u,v),c(v,u)=0因此sigama(f)=sigama(c(u,v)-c(v,u))=sigama(c(u,v))(其中u∈S,v∈T),即最大流的总流量等于割(S,T)的边容量,现在只需证明割(S,T)为最小割.
假设割(S,T)不为最小割,则f就不是最大流,因为总流量必然小于最小割的容量,因为从s到t的所有路径必然需要经过从S到T的过程,故总流量必然小于任意S与T的割的容量,即小于最小割的容量,故f非最大流,矛盾,故割(S,T)为最小割
得证.
而在最大流的情况下,最小割(即上述割(S,T))的定义,即无增广路径.
因此只要当前网络中不存在从s到t的增广路径,则当前流为最大流.
而至于流程我们只需重复进行：
1.找增广路径,找出最大可增量a=min(前向边c(u,v)-f(u,v),后向边f(v,u))
2.修改增广路径上每条前向边f(u,v)+a;后向边f(v,u)-a;
原来Ford-Fulkerson即上面1~2的思想，是用来求最大流的“方法”，若朴素查找增广路即一次增加1流量，复杂度为O(N*F)
而通过广搜来实现查找增广路径的“算法”是Edmonds-Karp算法O(N*M^2)
而Dinic算法，每次更新层次图广搜一遍O(M)，而进行增广时每增广一次删除一个点，最多删除n个点，因此为O(N^2)，因此总复杂度为O(N^2*M)