백준16046 Rainbow Graph

문제 링크

http://icpc.me/16046

문제 출처

2018 NAIPC G번

사용 알고리즘

Matroid Intersection

풀이

무향 연결 그래프 $G(V, E)$ 에서 $\mathcal{I}_G = \lbrace I : I \subset E, E\setminus I\text{ can connects all vertex in } G \rbrace$ 라고 정의하면 $\mathcal{M} = (S, \mathcal{I}_G)$ 는 Matroid입니다.

$\mathcal{I}{G}’ = \lbrace I : I \subset E, E\setminus I\text{ can connects all vertex in } G \text{ using edge colored with R or G} \rbrace $,$ \mathcal{I}{G}’’ = \lbrace I : I \subset E, E\setminus I\text{ can connects all vertex in } G \text{ using edge colored with G or B} \rbrace $라고 정의합시다.$ \mathcal{M}’ = (S, \mathcal{I}_G’) $와$ \mathcal{M}’’ = (S, \mathcal{I}_G’’)$ 역시 Matroid입니다.

그러므로 $\mathcal{M}’$ 과 $\mathcal{M}’‘$ 의 Cardinality가 $K$ 인 Maximum Weight Common Independent Set을 구하면 됩니다.

전체 코드

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;

template<size_t vertex_cnt>
struct UnionFind{
    array<int, vertex_cnt> P;
    UnionFind(){ clear(); }
    void clear(){ iota(all(P), 0); }
    int find(int v){ return v == P[v] ? v : P[v] = find(P[v]); }
    bool merge(int u, int v){
        u = find(u); v = find(v);
        if(u == v) return false;
        P[u] = v; return true;
    }
};

template<size_t vertex_cnt>
struct GraphicMatroid{
    UnionFind<vertex_cnt> uf;
    vector<PII> edges;
    bool noCycle;
    GraphicMatroid(){ clear(); }
    GraphicMatroid(const vector<PII> &edges) : edges(edges) { clear(); }
    void clear(){ uf.clear(); noCycle = true; }
    bool check(){ return noCycle; }
    void add(int i){ uf.merge(edges[i].x, edges[i].y); }
};

template<size_t vertex_cnt>
struct GraphicMatroidDual{
    int n; // vertex
    UnionFind<vertex_cnt> uf;
    vector<PII> edges;
    GraphicMatroidDual(){ clear(); }
    GraphicMatroidDual(int n, const vector<PII> &edges) : n(n), edges(edges) { clear(); }
    void clear(){ uf.clear(); }
    bool check(){
        for(int i=1; i<n; i++) if(uf.find(0) != uf.find(i)) return false;
        return true;
    }
    void add(int i){ uf.merge(edges[i].x, edges[i].y); }
};

template<typename M1, typename M2, typename weight_t, weight_t max_w>
struct MatroidIntersection{
    int n; // 0 ~ n-1 : elements of S, n : source, n+1 : sink
    vector<char> use;
    vector<weight_t> w;
    M1 m1; M2 m2;
    vector<vector<pair<int, weight_t>>> g;
    MatroidIntersection() = delete;
    MatroidIntersection(int n, M1 m1, M2 m2, const vector<weight_t> &w) : n(n), m1(m1), m2(m2), w(w), use(n), g(n+2) {}
    bool SPFA(int S, int T){
        vector<char> inq(n+2, false);
        vector<int> prv(n+2, -1);
        vector<weight_t> dst(n+2, max_w*(max_w+1)*n);
        queue<int> q; q.push(S); dst[S] = 0; inq[S] = true;
        while(q.size()){
            int v = q.front(); q.pop(); inq[v] = false;
            for(auto i : g[v]){
                if(dst[i.x] > dst[v] + i.y){
                    dst[i.x] = dst[v] + i.y; prv[i.x] = v;
                    if(!inq[i.x]) inq[i.x] = true, q.push(i.x);
                }
            }
        }
        if(prv[T] == -1) return false;
        for(int i=T; i!=S; i=prv[i]) if(i < n) use[i] ^= 1;
        return true;
    }
    bool augmentPath(){
        const int S = n, T = n+1;
        for(int i=0; i<n+2; i++) g[i].clear();
        for(int i=0; i<n; i++){
            if(!use[i]){
                use[i] = true;
                m1.clear(); m2.clear();
                for(int k=0; k<n; k++) if(!use[k]) m1.add(k), m2.add(k);
                if(m1.check()) g[S].emplace_back(i, -w[i]*max_w+1);
                if(m2.check()) g[i].emplace_back(T, 1);
                use[i] = false;
            }
            for(int j=0; j<n; j++){
                if(use[i] && !use[j]){
                    use[i] = false; use[j] = true;
                    m1.clear(); m2.clear();
                    for(int k=0; k<n; k++) if(!use[k]) m1.add(k), m2.add(k);
                    if(m1.check()) g[i].emplace_back(j, -w[j]*max_w+1);
                    if(m2.check()) g[j].emplace_back(i, w[i]*max_w+1);
                    use[i] = true; use[j] = false;
                }
            }
        }
        return SPFA(S, T);
    }
    tuple<vector<int>, int, weight_t> solve(){
        int cardinality = 0;
        weight_t weight;
        for(int i=0; i<n; i++) if(m1.check(i) && m2.check(i)) use[i] = 1, m1.add(i), m2.add(i);
        while(augmentPath()) cardinality++;
        vector<int> ans;
        for(int i=0; i<n; i++) if(use[i]) ans.push_back(i), weight += w[i];
        return make_tuple(ans, cardinality, weight);
    }
};

template<size_t vertex_cnt>
struct GraphicMatroidDual2{
    int n; // vertex
    UnionFind<vertex_cnt> uf;
    vector<PII> edges;
    vector<char> color;
    char c1, c2;
    GraphicMatroidDual2(){ clear(); }
    GraphicMatroidDual2(int n, const vector<PII> &edges) : n(n), edges(edges) { clear(); }
    void set(char _c1, char _c2, const vector<char> _color){ c1 = _c1; c2 = _c2; color = _color; }
    void clear(){ uf.clear(); }
    bool check(){
        for(int i=1; i<n; i++) if(uf.find(0) != uf.find(i)) return false;
        return true;
    }
    void add(int i){ if(color[i] == c1 || color[i] == c2) uf.merge(edges[i].x, edges[i].y); }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N, M; cin >> N >> M;
    vector<pair<int, int>> edges(M);
    vector<int> w(M);
    vector<char> color(M);
    for(int i=0; i<M; i++) cin >> edges[i].x >> edges[i].y >> w[i] >> color[i];
    for(int i=0; i<M; i++) edges[i].x--, edges[i].y--;

    vector<int> res(M+1, -1);
    GraphicMatroidDual2<111> m1(N, edges), m2(N, edges);
    m1.set('R', 'G', color);
    m2.set('G', 'B', color);

    for(int i=0; i<M; i++) m1.add(i), m2.add(i);
    if(!m1.check() || !m2.check()){
        for(int i=1; i<=M; i++) cout << res[i] << "\n";
        return 0;
    }

    MatroidIntersection<GraphicMatroidDual2<111>, GraphicMatroidDual2<111>, int, 1000> mat(M, m1, m2, w);
    res[M] = accumulate(all(w), 0);
    for(int i=M-1; i>=1; i--){
        if(!mat.augmentPath()) break;
        res[i] = 0;
        for(int j=0; j<M; j++) if(!mat.use[j]) res[i] += w[j];
    }
    for(int i=1; i<=M; i++) cout << res[i] << "\n";
}

Happy April Fools' Day! (Click Here!)

문제 링크

문제 출처

사용 알고리즘

풀이

전체 코드