p402.cpp
======================
#include <bits/stdc++.h>
#define endl '\n'

#pragma GCC optimize("O333")
#pragma GCC target("sse4")

using namespace std;
template<class T, class T2>
inline void chkmax(T& x, const T2& y) {
    if(x < y) {
        x = y;
    }
}
template<class T, class T2>
inline void chkmin(T& x, const T2& y) {
    if(x > y) {
        x = y;
    }
}
const int MAXN = (1 << 20);

template<class FlowT>
struct max_flow {
    const static FlowT finf = 1e9 + 42 + 17;
    const static FlowT feps = 0;

    struct edge {
        FlowT flow, cap;
        int idx, rev, to;
        edge() {
            flow = 0;
            cap = 0;
            rev = 0;
            idx = 0;
            to = 0;
        }
        edge(int _to, int _rev, FlowT _flow, FlowT _cap, int _idx) {
            to = _to;
            rev = _rev;
            flow = _flow;
            cap = _cap;
            idx = _idx;
        }
    };

    vector<edge> G[MAXN];
    int n, dist[MAXN], po[MAXN];

    bool bfs(int s, int t) {
        dist[s] = -1, po[s] = 0;
        dist[t] = -1, po[t] = 0;
        for(int v = 0; v <= n; v++) {
            dist[v] = -1, po[v] = 0;
        }

        queue<int> Q;
        Q.push(s);
        dist[s] = 0;

        while(!Q.empty()) {
            int u = Q.front();
            Q.pop();

            for(edge e: G[u]) {
                if(dist[e.to] == -1 && e.flow < e.cap) {
                    dist[e.to] = dist[u] + 1;
                    Q.push(e.to);
                }
            }
        }

        return dist[t] != -1;
    }

    FlowT dfs(int u, int t, FlowT fl = finf) {
        if(u == t) {
            return fl;
        }

        for(; po[u] < (int)G[u].size(); po[u]++) {
            auto& e = G[u][po[u]];
            if(dist[e.to] == dist[u] + 1 && e.flow < e.cap) {
                FlowT f = dfs(e.to, t, min(fl, e.cap - e.flow));

                e.flow += f;
                G[e.to][e.rev].flow -= f;

                if(f > 0) {
                    return f;
                }
            }
        }

        return 0;
    }

    void init(int _n) {
        n = _n;
        for(int i = 0; i <= n; i++) {
            G[i].clear();
        }
    }

    void add_edge(int u, int v, FlowT w, int idx = -1) {
        G[u].push_back(edge(v, G[v].size(), 0, w, idx));
        G[v].push_back(edge(u, G[u].size() - 1, 0, 0, -1));
    }

    bool used_cut[MAXN];

    void dfs_min_cut(int u) {
        used_cut[u] = 1;
        for(auto e: G[u]) {
            if(!used_cut[e.to] && e.cap > e.flow) {
                dfs_min_cut(e.to);
            }
        }
    }

    void find_cut(int s) {
        for(int i = 0; i <= n; i++) {
            used_cut[i] = 0;
        }
        dfs_min_cut(s);
    }

    FlowT flow(int s, int t) {
        if(s == t) {
            return finf;
        }

        FlowT ret = 0, to_add;
        while(bfs(s, t)) {
            while((to_add = dfs(s, t))) {
                ret += to_add;
            }
        }

        return ret;
    }
};

int n, m;
pair<int, pair<int, int> > ed[MAXN];
vector<int> adj[MAXN];

void read() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        cin >> ed[i].first >> ed[i].second.first >> ed[i].second.second;
        adj[ed[i].first].push_back(ed[i].second.first);
        adj[ed[i].second.first].push_back(ed[i].first);
    }
}

int answer;
vector<int> ans;
max_flow<int> mf;

void check(int t, int S, int T) {
    mf.init(n);
    for(int i = 1; i <= m; i++) {
        if(ed[i].first != t && ed[i].second.first != t) {
            mf.add_edge(
                ed[i].first, ed[i].second.first, ed[i].second.second, i
            );
            mf.add_edge(
                ed[i].second.first, ed[i].first, ed[i].second.second, i
            );
        }
    }

    int curr = mf.flow(S, T);
    if(answer == -1 || curr < answer) {
        mf.find_cut(S);

        answer = curr;
        ans.clear();
        for(int i = 0; i <= n; i++) {
            for(auto it: mf.G[i]) {
                if(mf.used_cut[i] && !mf.used_cut[it.to] && it.idx != -1) {
                    ans.push_back(it.idx);
                }
            }
        }

        sort(ans.begin(), ans.end());
        ans.erase(unique(ans.begin(), ans.end()), ans.end());
    }
}

void solve_ap(int r) {
    for(int u: adj[r]) {
        for(int v: adj[r]) {
            if(u < v && r != u && r != v) {
                check(r, u, v);
            }
        }
    }
}

void solve() {
    for(int i = 1; i <= n; i++) {
        adj[0].push_back(i);
    }

    answer = -1;
    for(int i = 0; i <= n; i++) {
        solve_ap(i);
    }

    cout << answer << endl;
    cout << ans.size() << endl;
    for(auto it: ans) {
        cout << it << " ";
    }
    if(ans.size()) {
        cout << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    read();
    solve();
    return 0;
}

=================
statement.txt
======================
402. Terrorists in Berland
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Many countries dream of capturing great and glorious country of Berland. Berland is a big country consisting of N cities, some of them are connected by bidirectional roads. Each pair of cities is connected by no more then one road. A traveler can get from one city to any other city traveling by the roads only.

Invaders plan to use these roads during their operation, but Berland military forces are strong enough to destroy an enemy trying to move along the roads. The treacherous plan was developed to make the invasion easier: Berland should be divided into two parts. To make the plan more effective the decision was made to use terrorists from the Berland opposition. Several groups agreed to participate in the plan. The terrorists' resources are limited, so they can only destroy roads, not cities. The procedure of the road destruction is a costly operation. The security precautions on different roads can vary, so the cost of the road destruction can be different.

Invaders want to suddenly attack Berland without declaring the war and quickly capture one of the cities. Berland troops can't move through the captured city as they can't move along the destroyed roads.

Your task is to find cheapest plan of roads destruction, so that at least one city exists which can be captured and allow invaders to divide the country into two parts. Berland is considered divided, if two such cities exist, that there is no way along non-destroyed roads and through non-captured cities from one to another.

Input
The first line of the input contains two integer numbers N and M (3 ≤ N ≤ 50; 1 ≤ M ≤ 500), where N is the number of cities and M is the number of roads. The following M lines contain the description of the roads given as three integer numbers ai, bi, wi (1 ≤ ai < bi ≤ N; 1 ≤ wi ≤ 10). The cost of destruction of the the road from ai to bi is wi.

Output
Write to the first line the total amount of money required to destroy roads in the optimal plan. Write to the second line K — number of roads to be destroyed according to the plan. Write to the third line numbers of roads to be destroyed divided by one space. The roads are numbered in order of appearance in the input. If there are several solutions, choose any of them.

Example(s)
sample input
sample output
3 3
1 2 1
2 3 2
1 3 2
1
1
1

sample input
sample output
4 6
1 2 1
1 3 1
2 3 2
1 4 1
2 4 2
3 4 3
2
2
2 4

=================
