首页 > 代码库 > 网络流

网络流

2024-07-05 10:04:57   230人阅读

大神博客：

1 2

hdu-1532 | poj - 1237

给出 n 条边，m 个点，端点及边的最大流量， 求最大流

 

1.EK模板 时间复杂度 O(VE2)

+ View 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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// CHEATBEATER 2014.5.20
 
#include <stdio.h>
#include <queue>
#include<string.h>
using namespace std;
#define arraysize 201
int maxData = http://www.mamicode.com/0x7fffffff;
int capacity[arraysize][arraysize]; //记录残留网络的容量
int flow[arraysize];                //标记从源点到当前节点实际还剩多少流量可用
int pre[arraysize];                 //标记在这条路径上当前节点的前驱,同时标记该节点是否在队列中
int n,m;
queue<int> myqueue;
int BFS(int src,int des)
{
    int i,j;
    while(!myqueue.empty())       //队列清空
        myqueue.pop();
    for(i=1; i<m+1; ++i)
    {
        pre[i]=-1;
    }
    pre[src]=0;
    flow[src]= maxData;
    myqueue.push(src);
    while(!myqueue.empty())
    {
        int index = myqueue.front();
        myqueue.pop();
        if(index == des)            //找到了增广路径
            break;
        for(i=1; i<m+1; ++i)
        {
            if(i!=src && capacity[index][i]>0 && pre[i]==-1)
            {
                pre[i] = index; //记录前驱
                flow[i] = min(capacity[index][i],flow[index]);   //关键：迭代的找到增量
                myqueue.push(i);
            }
        }
    }
    if(pre[des]==-1)      //残留图中不再存在增广路径
        return -1;
    else
        return flow[des];
}
int maxFlow(int src,int des)
{
    int increasement= 0;
    int sumflow = 0;
    while((increasement=BFS(src,des))!=-1)
    {
        int k = des;          //利用前驱寻找路径
        while(k!=src)
        {
            int last = pre[k];
            capacity[last][k] -= increasement; //改变正向边的容量
            capacity[k][last] += increasement; //改变反向边的容量
            k = last;
        }
        sumflow += increasement;
    }
    return sumflow;
}
int main()
{
    int i,j;
    int start,end,ci;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        memset(capacity,0,sizeof(capacity));
        memset(flow,0,sizeof(flow));
        for(i=0; i<n; ++i)
        {
            scanf("%d%d%d", &start, &end, &ci);
            if(start == end)               //考虑起点终点相同的情况
                continue;
            capacity[start][end] +=ci;     //此处注意可能出现多条同一起点终点的情况
        }
        printf("%d\n", maxFlow(1, m));
    }
    return 0;
}

 

2.大神写的ISAP + GAP + BFS 的非递归版本代码，网络采用邻接表 + 反向弧指针：据说很快

+ View 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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
//辉夜(tadvent)  2009.4.6
 
#include<cstdio>
#include<memory>
#include<string.h>
using namespace std;
 
const int maxnode = 1024;
const int infinity = 2100000;
 
struct edge{
    int ver;    // vertex
    int cap;    // capacity
    int flow;   // current flow in this arc
    edge *next; // next arc
    edge *rev;  // reverse arc
    edge(){}
    edge(int Vertex, int Capacity, edge *Next)
        :ver(Vertex), cap(Capacity), flow(0), next(Next), rev((edge*)NULL){}
    void* operator new(size_t, void *p){
        return p;
    }
}*Net[maxnode];
int dist[maxnode]= {0}, numbs[maxnode] = {0}, src, des, n;
 
void rev_BFS(){
    int Q[maxnode], head = 0, tail = 0;
    for(int i=1; i<=n; ++i){
        dist[i] = maxnode;
        numbs[i] = 0;
    }
 
    Q[tail++] = des;
    dist[des] = 0;
    numbs[0] = 1;
    while(head != tail){
        int v = Q[head++];
        for(edge *e = Net[v]; e; e = e->next){
            if(e->rev->cap == 0 || dist[e->ver] < maxnode)continue;
            dist[e->ver] = dist[v] + 1;
            ++numbs[dist[e->ver]];
            Q[tail++] = e->ver;
        }
    }
}
 
int maxflow(){
    int u, totalflow = 0;
    edge *CurEdge[maxnode], *revpath[maxnode];
    for(int i=1; i<=n; ++i)CurEdge[i] = Net[i];
    u = src;
    while(dist[src] < n){
        if(u == des){    // find an augmenting path
            int augflow = infinity;
            for(int i = src; i != des; i = CurEdge[i]->ver)
                augflow = min(augflow, CurEdge[i]->cap);
            for(int i = src; i != des; i = CurEdge[i]->ver){
                CurEdge[i]->cap -= augflow;
                CurEdge[i]->rev->cap += augflow;
                CurEdge[i]->flow += augflow;
                CurEdge[i]->rev->flow -= augflow;
            }
            totalflow += augflow;
            u = src;
        }
 
        edge *e;
        for(e = CurEdge[u]; e; e = e->next)
            if(e->cap > 0 && dist[u] == dist[e->ver] + 1)break;
        if(e){    // find an admissible arc, then Advance
            CurEdge[u] = e;
            revpath[e->ver] = e->rev;
            u = e->ver;
        } else {    // no admissible arc, then relabel this vertex
            if(0 == (--numbs[dist[u]]))break;    // GAP cut, Important!
            CurEdge[u] = Net[u];
            int mindist = n;
            for(edge *te = Net[u]; te; te = te->next)
                if(te->cap > 0)mindist = min(mindist, dist[te->ver]);
            dist[u] = mindist + 1;
            ++numbs[dist[u]];
            if(u != src)
                u = revpath[u]->ver;    // Backtrack
        }
    }
    return totalflow;
}
 
int main(){
    int m, u, v, w;
    while(scanf("%d%d", &m, &n) != EOF){
        memset(Net, 0, sizeof(Net));
        memset(dist, 0, sizeof(dist));
        memset(numbs, 0, sizeof(numbs));
 
        edge *buffer = new edge[2*m];
        edge *data = http://www.mamicode.com/buffer;
        src = http://www.mamicode.com/1; des = n;
        while(m--){
            scanf("%d%d%d", &u, &v, &w);
            if (u == v) continue;
            Net[u] = new((void*) data++) edge(v, w, Net[u]);
            Net[v] = new((void*) data++) edge(u, 0, Net[v]);
            Net[u]->rev = Net[v];
            Net[v]->rev = Net[u];
        }
        rev_BFS();
        printf("%d\n", maxflow());
        delete [] buffer;
    }
    return 0;
}

　　


联系
我们