NKNET - Mạng truyền tin

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
#define ii pair<int, int>
#define iii pair<int, ii>
#define X first
#define Y second

const int N = 111;
const int oo = trunc(1e9);
const int V = N * N;
using namespace std;
vector<iii> e;
vector<int> a[N];
int c[N][N], f[N][N], T[N], Q[N];
int m, n, s, t, res, ans;

void Enter() {
    //freopen("NKNET.in", "r", stdin);
    scanf("%d %d\n", &n, &m);
    int u, v, c;
    for(int i=1; i<=m; i++) {
        scanf("%d %d %d\n", &u, &v, &c);
        e.push_back(iii(c, ii(u, v)));
        a[u].push_back(v);
        a[v].push_back(u);
    }
    scanf("%d %d", &s, &t);
}

void Init(int lim) {
    //initialize network
    int i, j, u, v;
    for(i=1; i<=n; i++) {
        a[i].clear();
        for(j=1; j<=n; j++) {
            f[i][j] = 0;
            c[i][j] = V;
        }
    }
    for(i=0; i<m; i++)
    if (e[i].X > lim) {
        u = e[i].Y.X;
        v = e[i].Y.Y;
        a[u].push_back(v);
        a[v].push_back(u);
    }
}

void Init2(int lim) {
    int i, j, u, v;
    for(i=1; i<=n; i++) {
        a[i].clear();
        for(j=1; j<=n; j++) {
            f[i][j] = 0;
            c[i][j] = V;
        }
    }
    for(i=0; i<m; i++) {
        u = e[i].Y.X;
        v = e[i].Y.Y;
        a[u].push_back(v);
        a[v].push_back(u);

        if (e[i].X <= lim)
            c[u][v] = c[v][u] = 1;
    }
}

bool FindPath() {
    int l=1, r=1, u, v, i;
    Q[1] = s;
    for(i=1; i<=n; i++) T[i] = 0;
    while (l <= r) {
        u = Q[l++];
        for(i=0; i<a[u].size(); i++) {
            v = a[u][i];
            if (T[v] == 0 && c[u][v] > f[u][v]) {
                Q[++r] = v;
                T[v] = u;
                if (v == t) return true;
            }
        }
    }
    return false;
}

void IncFlow() {
    int u, v, delta = oo;
    v = t;
    while (v != s) {
        u = T[v];
        delta = min(delta, c[u][v] - f[u][v]);
        v = u;
    }
    v = t;
    while (v != s) {
        u = T[v];
        f[u][v] += delta;
        f[v][u] -= delta;
        v = u;
    }
}

int maxFlow() {
    while (FindPath()) IncFlow();
    int flow = 0;
    for(int i=0; i<a[s].size(); i++)
        flow += f[s][a[s][i]];
    return flow;
}

int main()
{
    Enter();
    //BinarySearch the answer
    int l = 0, r = V, mid;
    while (l <= r) {
        mid = (l + r) / 2;
        Init(mid);
        if (FindPath()) {
            l = mid + 1;
        }
        else {
            res = mid;
            r = mid - 1;
        }
    }
    Init2(res);
    ans = maxFlow();
    printf("%d\n", ans);
    for(int i=1; i<=n; i++)
    if (i == s || T[i] > 0) {
        for(int j=0; j<a[i].size(); j++) {
            int v = a[i][j];
            if (T[v] == 0) printf("%d %d\n", i, v);
        }
    }
    return 0;
}

Download