問題概要

頂点数 $N$ 、辺数 $M$ の単純有向グラフが与えられる (すべての辺の容量は 1)。2 点 $s, t$ 間の最大フロー (辺素パスの本数) について考える。

今、いくつかの辺を選んで向きを反転することができる。その結果 $s$ - $t$ 間の最大フロー値が最大となるようにせよ (それを実現する辺集合を出力せよ)。

制約

$2 \le N \le 300$
$1 \le M \le \min(1000, \frac{1}{2}N(N-1))$

考えたこと

辺を 1 本反転させるだけの問題とは設定が大きく異なる。これはもう、すべての有向辺を無向辺として一度最大流を流してしまうのがよさそう。たとえば普段は辺 $e = (u, v)$ を扱うとき

$u$ から $v$ 方向には容量 $1$ の辺
$v$ から $u$ 方向には容量 0 の辺

を張っている。でも今回は

$u$ から $v$ 方向に容量 $1$ の辺
$v$ から $u$ 方向に容量 $1$ の辺

を張っておく。そうした状態でフローを流せば理論最大値が出る。そしてその結果に基づいて、

元のグラフの各辺 $e = (u, v)$ について
容量がむしろ増加していたら、逆辺にフローが流れたことを意味するので
辺 $(u, v)$ を出力する

というようにすれば OK。計算量は最大フローを一回流す程度。

コード

#include <bits/stdc++.h>
using namespace std;

// edge class (for network-flow)
template<class FLOWTYPE> struct Edge {
    int rev, from, to, id;
    FLOWTYPE cap, icap;
    Edge(int r, int f, int t, FLOWTYPE c, int id) : rev(r), from(f), to(t), cap(c), icap(c), id(id) {}
    friend ostream& operator << (ostream& s, const Edge& E) {
        if (E.cap > 0) return s << E.from << "->" << E.to << '(' << E.cap << ')';
        else return s;
    }
};

// graph class (for network-flow)
template<class FLOWTYPE> struct Graph {
    vector<vector<Edge<FLOWTYPE> > > list;
    
    Graph(int n = 0) : list(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]; }
    inline const size_t size() const { return list.size(); }
    
    inline 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, int id) {
        list[from].push_back(Edge<FLOWTYPE>((int)list[to].size(), from, to, cap, id));
        list[to].push_back(Edge<FLOWTYPE>((int)list[from].size() - 1, to, from, 0, -1));
    }
    
    void add_undirected_edge(int from, int to, FLOWTYPE cap, int id) {
        list[from].push_back(Edge<FLOWTYPE>((int)list[to].size(), from, to, cap, id));
        list[to].push_back(Edge<FLOWTYPE>((int)list[from].size() - 1, to, from, cap, -1));
    }
};

template<class FLOWTYPE> struct Dinic {
    const FLOWTYPE INF = 1<<30; // to be set
    vector<int> level, iter;

    Dinic() { }
    void dibfs(Graph<FLOWTYPE> &G, int s) {
        level.assign((int)G.size(), -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(Graph<FLOWTYPE> &G, 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(G, e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    re.cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    
    FLOWTYPE solve(Graph<FLOWTYPE> &G, int s, int t) {
        level.assign((int)G.size(), -1); iter.assign((int)G.size(), 0);
        FLOWTYPE res = 0;
        while (true) {
            dibfs(G, 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(G, s, t, INF)) > 0) {
                res += flow;
            }
        }
    }
};

using pint = pair<int,int>;
int main() {
    int N, M, s, t;
    cin >> N >> M;
    Graph<int> oriG(N), G(N);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        oriG.addedge(u, v, 1, i);
        G.add_undirected_edge(u, v, 1, i);
    }
    cin >> s >> t;
    --s, --t;
    Dinic<int> din;
    int base = din.solve(oriG, s, t);
    int maxflow = din.solve(G, s, t);

    vector<int> res;
    if (maxflow > base) {
        for (int u = 0; u < N; ++u) {
            for (auto e : G[u]) {
                if (e.id == -1 || e.cap != 2) continue;
                res.push_back(e.id);
            }
        }
    }
    cout << maxflow << endl;
    cout << res.size() << endl;
    for (auto id : res) cout << id + 1 << endl;
}