POJ 1087

情報工学工房で「1087 -- A Plug for UNIX」という問題を解いたのですが,他の人の解法を聞いてなるほどと思ったので記事を書きます.

問題文は長いです.私の解法は最大流問題に帰着する方法です.なるほどと思った解法は二部グラフの最大マッチング問題に帰着する方法なのですがグラフの作成の部分に推移閉包を用いています.それぞれについて説明を行います.

[問題内容]

n個のコンセントのプラグ受けの形状とm個のデバイスの差込プラグの形状が与えられます.また,k個の変換プラグの種類が与えられます.それぞれの変換プラグは無限個あるとします.
デバイスをできる限り充電(差し込むコンセントを決める)したときの充電できなかったデバイスの数を答える問題です.この時,変換プラグの差込プラグとプラグ受けの形状が合えば連結して使用することができます.

制約:  1 \le m \le 100, 1 \le n \le 100, 1 \le k \le 100

[解法1(最大流問題)]

私の解法で最大流問題に帰着する方法です.
説明を書いている途中で思ったのですが弧の向きを逆にすればコンセントの差込プラグとプラグ受けの形状のイメージが合うと思って反省をしましたが,書いてしまったのでそのままで説明します.
次の図のようにグラフを作成してs-t最大流を求めます.
f:id:tatanaideyo:20151209141056p:plain

弧の付け方は次の通りで,すべての弧の容量は1です.
1. コンセント側とデバイス側で同じ形状
2. コンセント側と変換プラグの差込プラグが同じ形状
3. デバイス側と変換プラグのプラグ受けが同じ形状
4. 変換プラグのプラグ受けと変換プラグの差込プラグが同じ形状

mから求めた流量を引いた値が充電出来なかったデバイスの個数で答えとなります.この例では,phoneは上から3番目のcのコンセント,pagerは上から1番目のaのコンセント,clockは上から2番目のコンセント,combは上から4番目のコンセントに充電することが出来ます.充電出来なかったデバイスはlaptopだけで出力する答えは1になります.
f:id:tatanaideyo:20151209143025p:plain

[解法2(二部グラフの最大マッチング)]

次は聞いてなるほどと思った解法について紹介をします.二部グラフの最大マッチング問題に帰着しています.
まずは変換プラグのことを忘れて二部グラフを作成します.
n個のコンセントとm個のデバイスをそれぞれ二部グラフの部集合として,コンセントのプラグ受けとデバイスの差込プラグの形状が等しい場合に辺を張ります.
f:id:tatanaideyo:20151209144152p:plain

次に,この二部グラフに変換プラグを考慮して辺を張っていきます.
変換プラグのプラグ受けと差込プラグの形状を頂点として,二項関係(x,y)をプラグ受けの形状xと差込プラグの形状をyとする変換プラグが存在するとして弧を張ったグラフを考えます.
次に,「(x,z)かつ(z,y)ならば(x,y)」という推移関係が存在しなくなるまで弧を付け加えていきます.
この操作は,下の図で言うと(b,x)の変換プラグを(x,a)の変換プラグに差し込んでプラグ受けの形状をb,差込プラグの形状をaとする変換プラグを作ることになります.
f:id:tatanaideyo:20151209152042p:plain

このように,推移関係が存在しなくなるまで弧を付け加えたものを推移閉包と呼びます.すなわち,変換プラグを直列に接続して作ることの出来る可能な全ての変換プラグを作成したことに等しくなります.
推移閉包のきちんとした定義等は次の資料を参考にしてください.

離散数学 第13回 関係(4) 関係の閉包 岡本吉央」http://dopal.cs.uec.ac.jp/okamotoy/lect/2015/discretemath/handout13.pdf

この推移閉包はワーシャル–フロイド法 - Wikipediaで求めることが出来ます.

この推移閉包を用いて二部グラフの辺を加えていきます.
推移閉包の関係(x,y)に対して,二部グラフのデバイスの形状がxでコンセントの形状がyとなるデバイスとコンセントの間に辺を張ります.
そして,このようにして構成できた二部グラフに対して最大マッチングを求めて,mからその値を引いたものが答えになります.
f:id:tatanaideyo:20151209155906p:plain

[まとめ]

「ワーシャルフロイド法 = 全点対最短距離を求める」という感じで覚えており,ソースコードも短いから見ないでも書ける!!けどアルゴリズムの大事なところを覚えてないという残念な感じなので反省します.
推移閉包を用いる問題に出会ったことがなかったので良かったです.

[ソースコード]

解法1(最大流問題)のソースコードを載せます.

// Time: 788K   Memory: 63MS
#include <iostream>
#include <vector>
 
using namespace std;
 
typedef int Weight;
const Weight INF = 1e8;
 
struct Edge {
    int src, dst;
    Weight cap, rev;
    Edge(int f, int t, Weight c, Weight r) :
        src(f), dst(t), cap(c), rev(r) {}
};
 
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
 
void AddEdge(Graph &g, int from, int to, int cap) {
    g[from].push_back(Edge(from, to, cap, g[to].size()));
    g[to].push_back(Edge(to, from, 0, g[from].size() - 1));
}
 
Weight Dfs(Graph &g, vector<bool> &used, int v, int t, Weight f) {
    if (v == t)
        return f;
    used[v] = true;
    for (int deg = 0; deg < g[v].size(); ++deg) {
        Edge &e = g[v][deg];
        if (!used[e.dst] && e.cap > 0) {
            int d = Dfs(g, used, e.dst, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                g[e.dst][e.rev].cap += d;
 
                return d;
            }
        }
    }
    return 0;
}
 
// 最大流問題:計算量 O(FE + V^2), F: 最大流量
Weight FordFulkerson(Graph g, int s, int t) {
    const int n = g.size();
    Weight flow = 0;
    while (true) {
        vector<bool> used(n, false);
        Weight f = Dfs(g, used, s, t, INF);
        if (f <= 0)
            break;
        flow += f;
    }
    return flow;
}
 
// グラフを作成
Graph MakeGraph(int &n, int &m, int &s, int &t) {
    int k;
    string tmp_s;
 
    // Input: n_name[1:n], m_name[n+1:n+m],k_name[n+m+1:n+m+k]
    cin >> n;
    vector<string> n_name(n);
    for (int i = 0; i < n; ++i)
        cin >> n_name[i];
 
    cin >> m;
    vector<string> m_name(m);
    for (int i = 0; i < m; ++i)
        cin >> tmp_s >> m_name[i];
 
    cin >> k;
    vector<pair<string, string> > k_name(k);
    for (int i = 0; i < k; ++i)
        cin >> k_name[i].second >> k_name[i].first;
 
    s = 0; // source
    t = n + m + k + 1; // sink
    Graph g(t + 1);
 
    // Make Graph
    // s -> n_name
    for (int to = 1; to <= n; ++to)
        AddEdge(g, s, to, 1);
    // m_name -> t
    for (int from = n + 1; from <= n + m; ++from)
        AddEdge(g, from, t, 1);
    // n_name -> m_name, k_name
    for (int from = 1; from <= n; ++from) {
        // n_name -> m_name
        for (int to = n + 1; to <= n + m; ++to)
            if (n_name[from - 1] == m_name[to - n - 1])
                AddEdge(g, from, to, 1);
        // n_name -> k_name
        for (int to = n + m + 1; to <= n + m + k; ++to)
            if (n_name[from - 1] == k_name[to - n - m - 1].first)
                AddEdge(g, from, to, 1);
    }
    // k_name -> k_name, m_name
    for (int from = n + m + 1; from <= n + m + k; ++from) {
        for (int to = n + m + 1; to <= n + m + k; ++to)
            if (from != to && k_name[from - n - m - 1].second == k_name[to - n - m - 1].first)
                AddEdge(g, from, to, 1);
        for (int to = n + 1; to <= n + m; ++to)
            if (k_name[from - n - m - 1].second == m_name[to - n - 1])
                AddEdge(g, from, to, 1);
    }
 
    return g;
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    int n, m, s, t;
 
    Graph g = MakeGraph(n, m, s, t);
 
    cout << m - FordFulkerson(g, s, t) << endl;
 
    return 0;
}