問題概要

$G$ 人の女の子と、 $B$ 人の男の子がいて、「女の子同士」「男の子同士」はすべて互いに知り合いである。

それとは他に、 $M$ 組の「女の子 $i$ と男の子 $j$ は知り合い」という関係が与えられる。

$G + B$ 人の部分集合のうち、「どの 2 人も知り合いである」という条件を満たすような最大サイズを求めよ。

制約

$1 \le G, B \le 200$

解法

「最大クリークを求めなさい」という問題である。一般には NP-hard で解けないが今回は特殊なグラフである。

一般に補グラフをとると

クリーク (どの 2 頂点間にも辺がある)
独立集合 (どの 2 頂点間にも辺がない)

は互いに移り合う。今回の「知り合いグラフ」を補グラフ上で考えると、

「女の子」と「男の子」を左右にノードにもつ二部グラフになる
最大クリークを求める問題が、最大独立集合を求める問題になる

というわけで、問題は「二部グラフの最大独立集合問題」に帰着される。この記事で書いた通りの方法で求めることができる。

コード

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

template<class FLOWTYPE> struct Edge {
    int rev, from, to;
    FLOWTYPE cap, icap;
    Edge(int r, int f, int t, FLOWTYPE c) : rev(r), from(f), to(t), cap(c), icap(c) {}
};

template<class FLOWTYPE> struct Graph {
    vector<vector<Edge<FLOWTYPE> > > list;
    
    Graph(int n = 0) { init(n); }
    void init(int n = 0) { list.clear(); list.resize(n); }
    void reset() { for (int i = 0; i < (int)list.size(); ++i) for (int j = 0; j < list[i].size(); ++j) list[i][j].cap = list[i][j].icap; }
    inline vector<Edge<FLOWTYPE> >& operator [] (int i) { return list[i]; }
    const int size() const { return (int)list.size(); }
    
    Edge<FLOWTYPE> &redge(Edge<FLOWTYPE> e) {
        if (e.from != e.to) return list[e.to][e.rev];
        else return list[e.to][e.rev + 1];
    }
    
    void addedge(int from, int to, FLOWTYPE cap) {
        list[from].push_back(Edge<FLOWTYPE>((int)list[to].size(), from, to, cap));
        list[to].push_back(Edge<FLOWTYPE>((int)list[from].size() - 1, to, from, 0));
    }
    
    void addbiedge(int from, int to, FLOWTYPE cap) {
        list[from].push_back(Edge<FLOWTYPE>((int)list[to].size(), from, to, cap));
        list[to].push_back(Edge<FLOWTYPE>((int)list[from].size() - 1, to, from, cap));
    }
};

template<class FLOWTYPE> struct Dinic {
    vector<int> level;
    vector<int> iter;
    Graph<FLOWTYPE> G;
    static const FLOWTYPE INF = 1<<29; // to be set
    
    Dinic(const Graph<FLOWTYPE> &G_) : G(G_), level(vector<int>((int)G_.size())), iter(vector<int>((int)G_.size())) { }

    void dibfs(int s) {
        for (int i = 0; i < (int)level.size(); ++i) level[i] = -1;
        level[s] = 0;
        queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (int i = 0; i < G[v].size(); ++i) {
                Edge<FLOWTYPE> &e = G[v][i];
                if (level[e.to] < 0 && e.cap > 0) {
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    
    FLOWTYPE didfs(int v, int t, FLOWTYPE f) {
        if (v == t) return f;
        for (int &i = iter[v]; i < G[v].size(); ++i) {
            Edge<FLOWTYPE> &e = G[v][i], &re = G.redge(e);
            if (level[v] < level[e.to] && e.cap > 0) {
                FLOWTYPE d = didfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    re.cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    
    FLOWTYPE solve(int s, int t) {
        FLOWTYPE res = 0;
        while (true) {
            dibfs(s);
            if (level[t] < 0) return res;
            for (int i = 0; i < (int)iter.size(); ++i) iter[i] = 0;
            FLOWTYPE flow = 0;
            while ((flow = didfs(s, t, INF)) > 0) {
                res += flow;
            }
        }
    }
};

bool isconnect[210][210];
int main() {
    int G, B, M;
    int CASE = 0;
    while (cin >> G >> B >> M) {
        if (G == 0) break;
        memset(isconnect, 0, sizeof(isconnect));
        for (int i = 0; i < M; ++i) {
            int a, b; cin >> a >> b; --a, --b;
            isconnect[a][b] = true;
        }
        Graph<int> graph(G+B+2);
        int s = G+B, t = G+B+1;
        for (int i = 0; i < G; ++i) graph.addedge(s, i, 1);
        for (int i = 0; i < B; ++i) graph.addedge(i+G, t, 1);
        for (int i = 0; i < G; ++i)
            for (int j = 0; j < B; ++j)
                if (!isconnect[i][j])
                    graph.addedge(i, j+G, 1);
        Dinic<int> d(graph);
        int res = d.solve(s, t);
        cout << "Case " << CASE+1 << ": " << G + B - res << endl;
        ++CASE;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

POJ 3692 Kindergarten

問題概要

制約

解法

コード