最大流

发表于

网络流很令人费解，至今还未学会…
刚接触一点，先写上blog,未完待续!
XM-025

FordFulkerson 算法 (效率非常低)

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
struct edge{
    int to;   //终点
    int cap;  //c-f 
    int rev;  //反向边
};
vector<edge> G[MAXN];
bool used[MAXN];
void addEdge(int from,int to,int cap)
{
    G[from].push_back((edge){to,cap,(int)G[to].size()});
    G[to].push_back((edge){from,0,(int)G[from].size()-1});
}
int dfs(int v,int t,int f)
{
    if(v==t) return f;
    used[v]=true;
    for(int i=0;i<(int)G[v].size();i++){
        edge &e=G[v][i];
        if(!used[e.to]&&e.cap>0){
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
int maxFlow(int s,int t)
{
    int flow=0;
    for(;;){
        memset(used,0,sizeof(used));
        int f=dfs(s,t,INF);
        if(f==0) return flow;
        flow+=f;
    }
}

Hdu 3549 Flow Problem

链接

Flow Problem

分析

做的网络流的第一道题，最基本的最大流，直接套模板就ok
不过上述代码效率超级低，第一遍直接TLE
改成bfs勉强过了吧
下次学学Dinic算法

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
#include<stdio.h>
#include<string.h>
#include<queue>
#define INF 99999999
const int N=1010;
using namespace std;
int m,n,edge[N][N],pre[N];
bool vis[N];
int bfs(int s,int t)
{
    queue<int> q;
    memset(vis,0,sizeof(vis));
    memset(pre,0,sizeof(pre));
    q.push(s);
    vis[s]=true;
    while(!q.empty()){
        int pos=q.front();
        q.pop();
        if(pos==t)
            return true;
        for(int i=1;i<=n;i++){
            if(!vis[i]&&edge[pos][i]>0){
                pre[i]=pos;
                q.push(i);
                vis[i]=true;
            }
        }
    }
    return false;
}
int maxFlow(int s,int t)
{
    int flow=0;
    while(bfs(s,t)){
        int d=INF;
        for(int i=t;i!=s;i=pre[i])
            d=min(d,edge[pre[i]][i]);
        for(int i=t;i!=s;i=pre[i]){
            edge[pre[i]][i]-=d;
            edge[i][pre[i]]+=d;
        }
        flow+=d;
    }
    return flow;
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int k=1;k<=T;k++){
        scanf("%d%d",&n,&m);
        memset(edge,0,sizeof(edge));
        int x,y,c;
        while(m--){
            scanf("%d%d%d",&x,&y,&c);
            edge[x][y]+=c;
        }
        int flow=maxFlow(1,n);
        printf("Case %d: %d\n",k,flow);
    }
    return 0;
}