A Huster

0%

网络流初步

Posted on Valine:

其实网络流很久之前已经学过,但是因为一些原因搁置了很久,于是想再系统地复习一下.

由于博主能力有限,所以关于网络流知识也是了解个大概,这里只是简单介绍,并且说一下博主的感性理解

最大流

　　EK増广路算法

　　　　很容易理解的一个算法,也就是我们不断地bfs找出一条増广路然后更新剩余容量,直到更新完毕,类似于SPFA做法.时间复杂度$O(nm^{2})$;

　　　　这里不再附上代码,因为后面的费用流就要用EK+SPFA,而只是求最大流,推荐Dinic.

　　Dinic算法

　　　　与EK不同的是,Dinic算法增加了一些优化,这里引进了深度这个概念,通过在同一深度图中増广,一个点可以向多个点进行多流増广,并有减枝;

　　　　于是Dinic就可以达到$O(n^{2}m)$的优秀时间复杂度,可以代替匈牙利算法跑二分图匹配,时间复杂度$O(n\sqrt{n})$;

　　　　PS:关于二分图匹配时间复杂度可以这么想,由于一个点多流推进,同时増广多个点,而且深度小,所以时间复杂度就十分优秀;

　　　　Code:

　　　　

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
#define maxn 10008
using namespace std;
int n,m,head[maxn],s,t,cent=1,d[maxn],maxflow;
int min(int a,int b){return a<b?a:b;}
const int inf=1<<30;
struct node{
    int next,to,w;
}edge[maxn<<5];
queue<int >q;

void add(int u,int v,int w){
    edge[++cent]=(node){head[u],v,w};head[u]=cent;
    edge[++cent]=(node){head[v],u,0};head[v]=cent;
}

bool bfs(){
    memset(d,0,sizeof d);
    while(q.size()) q.pop();
    q.push(s),d[s]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=edge[i].next){
            int y=edge[i].to;
            if(edge[i].w&&!d[y]){
                q.push(y);d[y]=d[x]+1;
                if(y==t) return 1;
            }
        }
    }
    return 0;
}

int Dinic(int x,int flow){
    if(x==t) return flow;
    int rest=flow,k,y;
    for(int i=head[x];i;i=edge[i].next){
        if(edge[i].w&&d[y=edge[i].to]==d[x]+1){
            k=Dinic(y,min(rest,edge[i].w));
            edge[i].w-=k;
            edge[i^1].w+=k;
            rest-=k;
        }
    }
    return flow-rest;
}

int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1,a,b,w;i<=m;i++){
        scanf("%d%d%d",&a,&b,&w);
        add(a,b,w);
    }
    int flow=0;
    while(bfs())
        while(flow=Dinic(s,inf)) maxflow+=flow;
    printf("%d",maxflow);
}

费用流

　　费用流应该是我们见得最多的,而费用流跑二分图最大带权匹配极其优秀,费用流采用EK算法,不过每一次要跑一次SPFA,时间复杂度上升,如果要卡图了话,可能会崩;

　　但是由于图一般比较小,而且Dijkstra处理负权值问题有些复杂(要牵扯到势的辅助),所以还是普遍用SPFA求费用流;

　　Code

　　

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
#define maxn 50007
#define N 5007
#define inf 2139062143
using namespace std;
int n,m,s,t,incf[N],head[N],cent=1,dis[N];
int vis[N],maxflow,mincost,pre[N];
struct node{
    int next,to,w,cost;
}edge[maxn<<3];

inline void add(int u,int v,int w,int c){
    edge[++cent]=(node){head[u],v,w,c};head[u]=cent;
    edge[++cent]=(node){head[v],u,0,-c};head[v]=cent;
}

bool spfa(){
    queue<int >q;
    memset(pre,0,sizeof(pre)); 
    memset(dis,127,sizeof dis);
    memset(vis,0,sizeof vis);
    q.push(s);dis[s]=0;vis[s]=1;
    incf[s]=1<<30;
    while(!q.empty()){
        int x=q.front();q.pop();
        vis[x]=0;
        for(int i=head[x],y;i;i=edge[i].next){
            if(!edge[i].w) continue;
            if(dis[y=edge[i].to]>dis[x]+edge[i].cost){
                dis[y]=dis[x]+edge[i].cost;
                incf[y]=min(incf[x],edge[i].w);
                pre[y]=i;
                if(!vis[y]) q.push(y),vis[y]=1;
            }
        }
    }
    if(dis[t]==2139062143) return 0;
    return 1;
}

void update(){
    int x=t;
    while(x!=s){
        int i=pre[x];
        edge[i].w-=incf[t];
        edge[i^1].w+=incf[t];
        x=edge[i^1].to;
    }
    maxflow+=incf[t];
    mincost+=dis[t]*incf[t];
//    cerr<<mincost<<endl;
}

int main(){
//    freopen("cin.in","r",stdin);
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1,a,b,c,d;i<=m;i++){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a,b,c,d);
    }
    while(spfa()) update();
    printf("%d %d",maxflow,mincost);
}
本站访问次数：