UESTC 1143 传输数据 网络流 最大流 Dinic

最大流的Dinic算法  O(N^2 *M)   N vertices and M edges

#include 
#include 
#include 
#include 
using namespace std;
const int inf = 1000000000;
const int maxn = 200, maxm = 200;         //the max number of vertices and edges

struct Edge
{
    int v, f, nxt;
};

int n, src, sink;
int g[maxn+8];
int nume;
Edge e[maxm*2+8];

void addedge(int u, int v, int c)
{
    e[++nume].v = v;
    e[nume].f = c;
    e[nume].nxt = g[u];
    g[u] = nume;
    e[++nume].v = u;
    e[nume].f = 0;
    e[nume].nxt = g[v];
    g[v] = nume;
}

void init()
{
    memset(g, 0, sizeof(g));
    nume = 1;
}

queue que;
bool vis[maxn+8];
int dist[maxn+8];    //distance

void bfs()
{
    memset(dist, 0, sizeof(dist));
    while(!que.empty()) que.pop();
    vis[src] = true;
    que.push(src);
    while(!que.empty()){
        int u = que.front();
        que.pop();
        for(int i = g[u]; i; i = e[i].nxt) {
            if(e[i].f && !vis[e[i].v]) {
                que.push(e[i].v);
                dist[e[i].v] = dist[u] + 1;
                vis[e[i].v] = true;
            }
        }
    }
}

int dfs(int u, int delta)
{
    if(u == sink){
        return delta;
    }
    else{
        int ret = 0;
        for(int i = g[u]; delta && i; i = e[i].nxt) {
            if(e[i].f && dist[e[i].v] == dist[u] + 1) {
                int dd = dfs(e[i].v, min(e[i].f, delta));
                e[i].f -= dd;
                e[i^1].f += dd;
                delta -= dd;
                ret += dd;
            }
        }
        return ret;
    }
}

int maxflow()
{
    int ret = 0;
    while(true) {
        memset(vis, 0, sizeof(vis));
        bfs();
        if(!vis[sink]) return ret;
        ret += dfs(src, inf);
    }
}

int main()
{
    int N, M, S, E, C;
    scanf("%d%d", &N, &M);
    src = 1;sink = M;
    while(N--){
        scanf("%d%d%d", &S, &E, &C);
        addedge(S, E, C);
    }
    printf("%d", maxflow());
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx