最高のカレーを作れ！

またCodeIQです。
TCO algoも参加逃したし死にたい。

問題文ざっと読んだ感じ最小カットを求めればいいというのはすぐ解る。
任意の異なる2頂点間で最大流求めてその最小値答えればいいかなぁと思ったものの
最小カット直接求めるアルゴリズムあるんじゃないの？と思って調べると
Stoer-Wagnerのアルゴリズムという無向グラフの全域最小カットを求めるアルゴリズムがあるようだ。

あるグラフの最大隣接順序(maximum adjacency ordering, MA ordering)を計算し、
その最後の頂点とそれ以外の頂点のカットの容量を求めて、最後の頂点と1つ前の頂点を縮約する

という手順を頂点が1つになるまで繰りかえすと、反復中に求めたカットの容量の最小値=
元のグラフの全域最小カット　として求まる。

なのでまず与えられた組み合わせのリストから隣接行列を作って計算させていけばよい。

#include <iostream>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <cassert>
using namespace std;

int main(){
    ifstream fin("./matrix.in");
    ifstream gin("./indexes.in");
    int n = 128;
    int adj[n][n];
    int _adj[n][n];
    vector<int> shrinked[n];
    vector<int> bestCut;
    vector<int> V(n);
    vector<string> names;
    map<int,string> numToName;

    /* 名前読み込み*/
    string str;
    while(getline(gin, str)){
        istringstream iss(str);
        int num;
        string name;
        iss >> num >> name;
        numToName[num] = name;
    }

    /* 隣接行列読み込み */
    int minCut = 1 << 29;
    for(int i=0;i<n;i++){
        V[i] = i;
        shrinked[i].push_back(i);
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            fin >> adj[i][j];
            _adj[i][j] = adj[i][j];
        }
    }

    /* stoer-wagner */
    for(int x=n;x>1;x--){
        vector<int> ws(x,0);
        int u,v,w;
        /* calc MA ordering */
        for(int k=0;k<x;k++){
            u = v;
            v = max_element(ws.begin(), ws.end()) - ws.begin();
            w = ws[v];
            ws[v] = -1;
            for(int i=0;i<x;i++){
                if(ws[i] >= 0){
                    ws[i] += adj[V[v]][V[i]];
                }
            }
        }

        /* shrink */
        for(int i=0;i<x;i++){
            adj[V[i]][V[u]] += adj[V[i]][V[v]];
            adj[V[u]][V[i]] += adj[V[v]][V[i]];
        }

        cout << "shrink " << v << " -> " << u << endl;

        /* update */
        if(minCut >= w){
            minCut = w;
            for(int i=0;i<(int)shrinked[v].size();i++){
                if(i) cout << " ";
                cout << shrinked[v][i];
            }
            cout << " :" << w << endl;
            bestCut = shrinked[v];
        }

        /* store shrinked nodes */
        for(int i=0;i<(int)shrinked[v].size();i++){
            shrinked[u].push_back(shrinked[v][i]);
        }
        for(int i=0;i<x-1;i++){
            if(i >= v){
                shrinked[i] = shrinked[i+1];
            }
        }
        V.erase(V.begin()+v);

    }

    /* output answer */
    cout << minCut << endl;
    int yes=0, no=0, all=0;
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            if(_adj[i][j] > 0){
                all++;
                if(find(bestCut.begin(), bestCut.end(), i) != bestCut.end() &&  
                   find(bestCut.begin(), bestCut.end(), j) != bestCut.end()){
                    yes++;
                }else if(
                    (find(bestCut.begin(), bestCut.end(), i) != bestCut.end() && find(bestCut.begin(), bestCut.end(), j) == bestCut.end()) ||
                    (find(bestCut.begin(), bestCut.end(), i) == bestCut.end() && find(bestCut.begin(), bestCut.end(), j) != bestCut.end())
                    ){
                    //do nothing
                }else{
                    no++;
                }
            }
        }
    }
    cout << "all = " << all << ", yes = " << yes << ", no = " << no << endl;
    if(yes > no){
        for(int i=0;i<(int)bestCut.size();i++){
            names.push_back(numToName[bestCut[i]]);
        }
    }else{
        for(int i=0;i<n;i++){
            if(find(bestCut.begin(), bestCut.end(), i) == bestCut.end()){
                names.push_back(numToName[i]);
            }
        }
        assert(names.size() + bestCut.size() == 128);
    }
    sort(names.begin(), names.end());

    for(int i=0;i<(int)names.size();i++){
        if(i) cout << " ";
        cout << names[i];
    }
    cout << endl;
}

単に最小カットを求めればよいというものではなかったので
事前の処理(名前-indexの対応付け)と事後処理(どのnodeがどっちの集合か)が
若干面倒だったけど面白かった。(小並感)
Kargerのアルゴリズムも実装してみたいなぁ。