POJ 1637 Sightseeing tour

オイラー閉路にtwo-wayなエッジを追加した問題. 最大流で解けます。考え方は以下の通り

• まずtwo-wayなエッジであろうと入力そのまま有向なエッジとしてグラフに追加していく。
• 出るエッジについて-1,入るエッジについて+1を各ノードで計算しておく。通常のオイラー閉路ならば、各ノードで0ならOK?
• 今回はtwo-wayなものをそのままグラフに追加したので、0にはならないが、必ず2の倍数になる。なぜなら、正解のグラフの向きにしたときには各ノードで0であり、正解と逆向きにすると入るところが+2,出るところが-2となるからである。
• inoutをすべて/2する。これは流量を丁度1とするためである。(実際には2を流したいが、1だけ流してしまうのを防ぐ)
• 流れないならば、決め打ちしたエッジはそのままで良く、流れるのならば、丁度-1+2=1となって逆向きのエッジを張ることに相当する
• 最初にtwo-wayなエッジで決め打ちしたのと逆方向に流量1のエッジをつける
• inoutがプラスとなっているところにsuper sourceからプラス分流し、マイナスとなっているところにsuper sinkからマイナス分流す
• プラスの総量分がsuper sourceからsuper sinkから流れたらOK.

#include <vector>
#include <iostream>
#include <queue>

using namespace std;

// ----- lib start
struct Edge{
    int to,cap,rev;
    Edge(int _to,int _cap,int _rev) : to(_to),cap(_cap),rev(_rev) {};
};

void add_edge(vector<vector<Edge> >& E,int from,int to,int cap){
    E[from].push_back(Edge(to,cap,E[to].size()));
    E[to].push_back(Edge(from,0,E[from].size()-1));
}

vector<int> levels(vector<vector<Edge> > &E,int s){
    vector<int> level(E.size(),-1);
    level[s] = 0;
    queue<int> Q;
    Q.push(s);
    while(!Q.empty()){
        int v = Q.front();
        Q.pop();
        for(size_t i=0;i<E[v].size();i++){
            Edge &e = E[v][i];
            if(e.cap > 0 and level[e.to] == -1){
                level[e.to] = level[v]+1;
                Q.push(e.to);
            }
        }
    }
    return level;
}

int good_path(vector<vector<Edge> > &E,
        vector<int> &iter,
        vector<int> &level,
        int v,int t,int f){
    if(v == t) return f;
    for(int &i=iter[v];i<(int)E[v].size();i++){
        Edge &e = E[v][i];
        if(e.cap > 0 and level[v] < level[e.to]){
            int d = good_path(E,iter,level,e.to,t,min(f,e.cap));
            if(d > 0){
                e.cap -= d;
                E[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(vector<vector<Edge> > E,int s,int t){
    int flow = 0;
    const int INF = 1 << 30;
    while(true){
        vector<int> level = levels(E,s);
        if(level[t] < 0) return flow;
        vector<int> iter(E.size());
        int f;
        while((f=good_path(E,iter,level,s,t,INF)) > 0){
            flow += f;
        }
    }
}
// ----- lib end.

struct Street {
    int x,y,di;
    Street() {}
    Street(int _x,int _y,int _di) : x(_x),y(_y),di(_di) {}
};


bool solve(const vector<Street> &s,int m){
    vector<int> inout(m);
    // m is super source.
    // m+1 is super sink
    int source = m;
    int sink = m+1;
    vector<vector<Edge> > E(m+2);
    for(size_t i=0;i<s.size();i++){
        inout[s[i].x]--;
        inout[s[i].y]++;
        // two-way
        if(s[i].di == 0){
            add_edge(E,s[i].y,s[i].x,1);
        }
    }
    for(int i=0;i<m;i++){
        if(inout[i] % 2 == 1) return false;
        inout[i] /= 2;
    }
    int send=0;
    for(int i=0;i<m;i++){
        if(0 < inout[i]){
            add_edge(E,source,i,inout[i]);
            send += inout[i];
        }else if(inout[i] < 0){
            add_edge(E,i,sink,-inout[i]);
        }
    }
    return max_flow(E,source,sink) == send;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for(int test=0;test<n;test++){
        int m,s;
        cin >> m >> s;
        vector<Street> st(s);
        for(int i=0;i<s;i++){
            cin >> st[i].x >> st[i].y >> st[i].di;
            st[i].x--;
            st[i].y--;
        }
        if(solve(st,m)){
            cout << "possible" << endl;
        }else{
            cout << "impossible" << endl;
        }
    }
    return 0;
}