P3731 [HAOI2017]新型城市化（tarjan+网络流）

题意：

给出两个最大团的补图，现在要求增加一条边，使得最大最大团个数增加至少\(1\)。

思路：

我们求出团的补图，问题可以转换为：对于一个二分图，选择删掉一条边，能够增大其最大独立集的点集数。
然后做法就是考虑在最大流的残余网络上，对容量为\(1\)的边求强连通分量（包含源点、汇点）。
若存在一条边\((x,y)\)为匹配边，并且\(x,y\)在不同的强连通分量中，那么\((x,y)\)这条边为必经边，即最大匹配中包含这条边；若\((x,y)\)为非匹配边并且\(x,y\)在同一强连通分量中，那么\((x,y)\)为最大匹配的可行边，即这条边存在于至少一个最大匹配中。
证明的话，就拿必经边来说，若\((x,y)\)在同一强连通分量中，我们去掉\(x,y\)这条边，还是有增广路径能从\(x\)到\(y\)，此时最大匹配没变并且\((x,y)\)流量为\(0\)。所以\((x,y)\)不能在同一强连通分量中。

注意一开始要对图进行二分图染色。

代码如下：

#include <bits/stdc++.h>

#define MP make_pair

#define fi first

#define se second

#define sz(x) (int)(x).size()

#define all(x) (x).begin(), (x).end()

#ifdef Local

#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)

void err() { std::cout << '\n'; }

template<typename T, typename...Args>

void err(T a, Args...args) { std::cout << a << ' '; err(args...); }

#else

#define dbg(...)

#endif

void pt() {std::cout << '\n'; }

template<typename T, typename...Args>

void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

//head

const int N = 5e4 + 5, M = 1e6 + 5;

#define INF 0x3f3f3f3f

template <class T>

struct Dinic{

    struct Edge{

        int v, next;

        T flow;

        Edge(){}

        Edge(int v, int next, T flow) : v(v), next(next), flow(flow) {}

    }e[M << 1];

    int head[N], tot;

    int dep[N];

    void init() {

        memset(head, -1, sizeof(head)); tot = 0;

    }

    void adde(int u, int v, T w, T rw = 0) {

        e[tot] = Edge(v, head[u], w);

        head[u] = tot++;

        e[tot] = Edge(u, head[v], rw);

        head[v] = tot++;

    }

    bool BFS(int _S, int _T) {

        memset(dep, 0, sizeof(dep));

        queue <int> q; q.push(_S); dep[_S] = 1;

        while(!q.empty()) {

            int u = q.front(); q.pop();

            for(int i = head[u]; ~i; i = e[i].next) {

                int v = e[i].v;

                if(!dep[v] && e[i].flow > 0) {

                    dep[v] = dep[u] + 1;

                    q.push(v);

                }

            }

        }

        return dep[_T] != 0;

    }

    T dfs(int _S, int _T, T a) {

        T flow = 0, f;

        if(_S == _T || a == 0) return a;

        for(int i = head[_S]; ~i; i = e[i].next) {

            int v = e[i].v;

            if(dep[v] != dep[_S] + 1) continue;

            f = dfs(v, _T, min(a, e[i].flow));

            if(f) {

                e[i].flow -= f;

                e[i ^ 1].flow += f;

                flow += f;

                a -= f;

                if(a == 0) break;

            }

        }

        if(!flow) dep[_S] = -1;

        return flow;

    }

    T dinic(int _S, int _T) {

        T max_flow = 0;

        while(BFS(_S, _T)) max_flow += dfs(_S, _T, INF);

        return max_flow;

    }

    stack <int> s;

    int dfs_T, num;

    int scc[N], dfn[N], low[N];

    void Tarjan(int u){

        dfn[u] = low[u] = ++dfs_T;

        s.push(u);

        for(int i = head[u]; i != -1;i = e[i].next){

            int v = e[i].v;

            if(e[i].flow == 0) continue;

            if(!dfn[v]){

                Tarjan(v);

                low[u] = min(low[u], low[v]);

            }else if(!scc[v]){

                low[u] = min(low[u], dfn[v]);

            }

        }

        if(low[u] == dfn[u]){

            num++; int now;

            do{

                now = s.top(); s.pop();

                scc[now] = num;

            }while(!s.empty() && now!=u);

        }

    }

};

Dinic <int> solve;

int n, m;

vector <int> g[N];

int col[N];

void color(int u, int c) {

    col[u] = c;

    for(auto v : g[u]) {

        if(!col[v]) color(v, 3 - c);

    }

}

void run() {

    solve.init();

    for(int i = 1; i <= m; i++) {

        int u, v; cin >> u >> v;

        g[u].push_back(v);

        g[v].push_back(u);

    }

    for(int i = 1; i <= n; i++) {

        if(!col[i]) color(i, 1);

    }

    int t = 2 * n + 1;

    for(int i = 1; i <= n; i++) {

        if(col[i] == 1) {

            solve.adde(0, i, 1);

            for(auto j : g[i]) {

                solve.adde(i, j + n, 1);

            }

        } else {

            solve.adde(i + n, t, 1);

        }

    }

    int flow = solve.dinic(0, t);

    dbg(flow);

    for(int i = 0; i <= t; i++) {

        if(!solve.dfn[i]) {

            solve.Tarjan(i);

        }

    }

    dbg(solve.num);

    vector <pii> ans;

    for(int u = 1; u <= n; u++) {

        for(int i = solve.head[u]; i != -1; i = solve.e[i].next) {

            int v = solve.e[i].v;

            if(solve.e[i].flow == 1) continue;

            if(v > n && solve.scc[u] != solve.scc[v]) {

                int x = u, y = v - n;

                if(x > y) swap(x, y);

                ans.push_back(MP(x, y));

            }

        }

    }

    sort(all(ans), [&](pii A, pii B) {

        if(A.fi == B.fi) return A.se < B.se;

        return A.fi < B.fi;

    });

    pt(sz(ans));

    for(auto it : ans) cout << it.fi << ' ' << it.se << '\n';

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    cout << fixed << setprecision(20);

#ifdef Local

    freopen("../input.in", "r", stdin);

    freopen("../output.out", "w", stdout);

#endif

    while(cin >> n >> m) run();

    return 0;

}

巴特西

P3731 [HAOI2017]新型城市化（tarjan+网络流）

最新文章

热门文章