最大流 Dinic

一个图， 每条边都有一个容量限制，一般有一个起点，一个终点，求达到平衡状态时，最多有多少流量从起点流向终点。 难点在于建图，建好图直接套模板

HDU 3549 Flow Problem

#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 100;
const int maxm = 30000 + 5;
const long long INF = 0x3f3f3f;

struct Edge {
    int from, to, cap, flow;
    Edge(){}
    Edge(int from, int to, int cap, int flow) {
        this->from = from;
        this->to = to;
        this->cap = cap;
        this->flow = flow;
    }
};

struct Dinic {
    int n, m, s, t;
    Edge edges[maxm];
    int head[maxn];
    int nxt[maxm];
    bool vis[maxn];
    int d[maxn];
    int cur[maxn];

    void init(int n) {
        this -> n = n;
        memset(head, -1, sizeof(head));
        m = 0;
    }

    void AddEdge(int u, int v, int c) {
        edges[m] = Edge(u, v, c, 0);
        nxt[m] = head[u];
        head[u] = m++;
        edges[m] = Edge(v, u, 0, 0);
        nxt[m] = head[v];
        head[v] = m++;
    }

    bool BFS() {
        memset(vis, 0, sizeof(vis));
        queue<int>Q;
        Q.push(s);
        d[s] = 0;
        vis[s] = 1;
        while (!Q.empty()) {
            int x = Q.front(); Q.pop();
            for (int i = head[x]; i != -1; i = nxt[i]) {
                Edge& e = edges[i];
                if (!vis[e.to] && e.cap > e.flow) {
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int DFS(int x, int a) {
        if (x == t || a == 0) return a;
        int flow = 0, f;
        for (int& i = cur[x]; i != -1; i = nxt[i]) {
            Edge& e = edges[i];
            if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > 0) {
                e.flow += f;
                edges[i^1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0) break;
            }
        }
        return flow;
    }

    int Maxflow(int s, int t) {
        this -> s = s; this -> t = t;
        int flow = 0;
        while (BFS()) {
            for (int i = 0; i < n; i++)
                cur[i] = head[i];
            flow += DFS(s, INF);
        }
        return flow;
    }
} H;

int main() {
    //freopen("in.txt", "r", stdin);
    int n, m, u, v, c, i, t;
    scanf("%d", &t);
    for (int ii = 1; ii <= t; ii++) {
        scanf("%d%d", &n, &m);
        H.init(n + 1);
        for(i=1; i<=m; ++i) {
            scanf("%d%d%d", &u, &v, &c);
            H.AddEdge(u, v, c);
        }
        printf("Case %d: %d\n", ii, H.Maxflow(1, n));
    }
    return 0;
}

HDU 5352 MZL's City

题意有点难：有N个点的一个无向图，最开始每个点都是不可用的，每两点之间都没有边，然后会有M个操作：

1 x ,   可以把和x直接相连或间接相连的点变成可用的，但最多修复K个
2 x, y  可以在x和y之间连一条无向边
3 p     后面有p对数，每对两个数x， y代表x，y之间的边被损毁了

对于每次1操作，输出要修复的点的数量，使总共修复的点的数量最多，在这基础上输出字典序最小的解

每次1操作的时候都会得到一个图，既然想求总共修复的点的数量最多，那么用贪心的思想，每次1操作的时候都尽量修复最多的点： 然后想了一组样例： 先进性操作2建边：1-3 1-4 1-5 1-6 2-5 2-6 然后1开始修复，限制为3，然后拆除 1-5 1-6，然后2开始修复，限制为3，求最多修复多少个城市

正解应该是1先修复1，3和4，然后2修复2，5和6，这样最多修复了1,2,3,4,5,6这6个城市，但是如果第一次先修复了1，5和6，然后题目把边1-5,1-6断掉了，这样第二次只能修复2号点了，最终修复了1,2,5,6这4个点，这样是不对的，所以难的地方在于题目会删边，如果不删边，在建完这个图的时候跑个最大流就行了，然后考虑字典序的关系让越靠后的询问先跑，这样就能保证字典序最小了。

然后删边的问题怎么解决呢？想想删边带来的影响：删边可能会使原本可达的点变的不可达了，减少了总方案数，所以，直接模拟这个删边过程，最终结果就是进行1操作时，（设此点的编号为s），每次我们都能达到s能到达的所有点组成的连通分量，这个连通分量是在上次1操作之后进行添边减边得到的，那么题意就简化成了官方题解那样：左右两排点，每个左边的点可以匹配一些右边的点，最多匹配K次，求最大匹配次数

#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;

const int maxn = 1000;
const int maxm = 100000;
const long long INF = 0x3f3f3f;

struct Edge {
    int from, to, cap, flow;
    Edge(){}
    Edge(int from, int to, int cap, int flow) {
        this->from = from;
        this->to = to;
        this->cap = cap;
        this->flow = flow;
    }
};

struct Dinic {
    int n, m, s, t;
    Edge edges[maxm];
    int head[maxn];
    int nxt[maxm];
    bool vis[maxn];
    int d[maxn];
    int cur[maxn];

    void init(int n) {
        this -> n = n;
        memset(head, -1, sizeof(head));
        m = 0;
    }

    void AddEdge(int u, int v, int c) {
        edges[m] = Edge(u, v, c, 0);
        nxt[m] = head[u];
        head[u] = m++;
        edges[m] = Edge(v, u, 0, 0);
        nxt[m] = head[v];
        head[v] = m++;
    }

    bool BFS() {
        memset(vis, 0, sizeof(vis));
        queue<int>Q;
        Q.push(s);
        d[s] = 0;
        vis[s] = 1;
        while (!Q.empty()) {
            int x = Q.front(); Q.pop();
            for (int i = head[x]; i != -1; i = nxt[i]) {
                Edge& e = edges[i];
                if (!vis[e.to] && e.cap > e.flow) {
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int DFS(int x, int a) {
        if (x == t || a == 0) return a;
        int flow = 0, f;
        for (int& i = cur[x]; i != -1; i = nxt[i]) {
            Edge& e = edges[i];
            if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > 0) {
                e.flow += f;
                edges[i^1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0) break;
            }
        }
        return flow;
    }

    int Maxflow(int s, int t) {
        this -> s = s; this -> t = t;
        int flow = 0;
        while (BFS()) {
            for (int i = 0; i < n; i++)
            cur[i] = head[i];
            flow += DFS(s, INF);
        }
        return flow;
    }
} H;

int n, m, k, id;
int g[maxn][maxn], vis[maxn][maxn], ans[maxn];
vector<int>G[maxn];

void init() {
    memset(g, 0, sizeof(g));
    memset(vis, 0, sizeof(vis));
    id = 0;
}

void dfs(int id, int u) {
    vis[id][u] = 1;
    G[id].push_back(u);
    for (int i = 1; i <= n; i++) {
        if (vis[id][i] || !g[u][i]) continue;
        dfs(id, i);
    }
}

void solve() {
    int s = 0, t = n + id + 1;
    H.init(t + 1);
    for (int i = 1; i <= id; i++) {
        H.AddEdge(s, i, k);
    }
    for (int i = 1; i <= n; i++) {
        H.AddEdge(i + id, t, 1);
    }
    int sum = 0;
    for (int i = id; i >= 1; i--) {
        for (int j = 0; j < (int)G[i].size(); j++) {
            int v = G[i][j];
            H.AddEdge(i, v + id, 1);
        }
        sum += H.Maxflow(s, t);
    }

    for (int i = H.head[s]; i != -1; i = H.nxt[i]) {
        int w = H.edges[i].flow;
        int v = H.edges[i].to;
        ans[v] = w;
    }

    printf("%d\n", sum);
    for (int i = 1; i <= id; i++) {
        printf("%d%c", ans[i], i == id ? '\n' : ' ');
    }
    for (int i = 0; i <= id; i++) G[i].clear();
}

int main() {
    //freopen("in.txt", "r", stdin);
    int tcase;
    scanf("%d", &tcase);
    while (tcase--) {
        scanf("%d%d%d", &n, &m, &k);
        int op, x, y, p;
        init();
        for (int i = 0; i < m; i++) {
            scanf("%d", &op);
            if (op == 1) {
                scanf("%d", &x);
                id++;
                dfs(id, x);
            } else if (op == 2) {
                scanf("%d%d", &x, &y);
                g[x][y] = 1;
                g[y][x] = 1;
            } else if (op == 3) {
                scanf("%d", &p);
                while (p--) {
                    scanf("%d%d", &x, &y);
                    g[x][y] = 0;
                    g[y][x] = 0;
                }
            }
        }
        solve();
    }
    return 0;
}