Problem:


Reverse Roads

ICP city has an express company whose trucks run from the crossing S to the crossing T.
The president of the company is feeling upset because all the roads in the city are one-way, and are severely congested.
So, he planned to improve the maximum flow (edge disjoint paths) from the crossing S to the crossing T by reversing the traffic direction on some of the roads.

Your task is writing a program to calculate the maximized flow from S to T by reversing some roads, and the list of the reversed roads.

Input

The first line of a data set contains two integers N (2 \leq N \leq 300) and M (0 \leq M \leq {\rm min} (1\,000,\ N(N-1)/2)).
N is the number of crossings in the city and M is the number of roads.

The following M lines describe one-way roads in the city.
The i-th line (1-based) contains two integers X_i and Y_i (1 \leq X_i, Y_i \leq N, X_i \neq Y_i).
X_i is the ID number (1-based) of the starting point of the i-th road and Y_i is that of the terminal point.
The last line contains two integers S and T (1 \leq S, T \leq N, S \neq T, 1-based).

The capacity of each road is 1.

You can assume that i \neq j implies either X_i \neq X_j or Y_i \neq Y_j,
and either X_i \neq Y_j or X_j \neq Y_i.

Output

In the first line, print the maximized flow by reversing some roads.
In the second line, print the number R of the reversed roads.
In each of the following R lines, print the ID number (1-based) of a reversed road.
You may not print the same ID number more than once.

If there are multiple answers which would give us the same flow capacity, you can print any of them.

Sample Input 1

2 1
2 1
2 1

Output for the Sample Input 1

1
0

Sample Input 2

2 1
1 2
2 1

Output for the Sample Input 2

1
1
1

Sample Input 3

3 3
3 2
1 2
3 1
1 3

Output for the Sample Input 3

2
2
1
3



Sample input:
2 1
2 1
2 1


Sample output:
1
0

Submission status: Wrong Answer

Solution code:
# AOJ 2304 Reverse Roads
# Python3 2018.7.21 bal4u

# *******************************************
# Dinic's Max Flow Algorithm
# *******************************************
INF = 0x7fffffff

class Donic:
    def __init__(self, V):
        self.V = V
        self.level = [0] * V
        self.iter = [0] * V
        self.edge = [[] for i in range(V)]

    def add_edge(self, frm, to, cap):
        f, t = len(self.edge[frm]), len(self.edge[to])
        self.edge[frm].append([to, cap, t])
        self.edge[to].append([frm, cap, f])

    def bfs(self, s):
        self.level = [-1] * self.V
        self.level[s] = 0
        Q = []
        Q.append(s)
        while Q:
            v = Q.pop()
            for to, cap, rev in self.edge[v]:
                if cap > 0 and self.level[to] < 0:
                    self.level[to] = self.level[v] + 1
                    Q.append(to)

    def dfs(self, v, t, f):
        if v == t: return f
        k = self.iter[v]
        while k < len(self.edge[v]):
            to, cap, rev = self.edge[v][k]
            if cap > 0 and self.level[v] < self.level[to]:
                d = self.dfs(to, t, f if f <= cap else cap)
                if d > 0:
                    self.edge[v][k][1] -= d
                    self.edge[to][rev][1] += d
                    return d
            self.iter[v] += 1
            k += 1
        return 0

    def maxFlow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0: break
            self.iter = [0] * self.V
            while True:
                f = self.dfs(s, t, INF)
                if f <= 0: break
                flow += f
        return flow

N, M = map(int, input().split())
dir = [[0 for j in range(N)] for i in range(N)]
id =  [[0 for j in range(N)] for i in range(N)]
d = Donic(N)
for i in range(M):
	x, y = map(int, input().split())
	x, y = x-1, y-1
	dir[y][x] = 1
	id[y][x] = i+1
	d.add_edge(x, y, 1)
S, T = map(int, input().split())
print(d.maxFlow(S-1, T-1))

ans = []
for i in range(N):
	for to, cap, rev in d.edge[i]:
		if cap < 1 and dir[i][to]: ans.append(id[i][to])
ans.sort()
print(len(ans))
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
# AOJ 2304 Reverse Roads
# Python3 2018.7.21 bal4u

# *******************************************
# Dinic's Max Flow Algorithm
# *******************************************
INF = 0x7fffffff

class Donic:
    def __init__(self, V):
        self.V = V
        self.level = [0] * V
        self.iter = [0] * V
        self.edge = [[] for i in range(V)]

    def add_edge(self, frm, to, cap):
        f, t = len(self.edge[frm]), len(self.edge[to])
        self.edge[frm].append([to, cap, t])
        self.edge[to].append([frm, cap, f])

    def bfs(self, s):
        self.level = [-1] * self.V
        self.level[s] = 0
        Q = []
        Q.append(s)
        while Q:
            v = Q.pop()
            for to, cap, rev in self.edge[v]:
                if cap > 0 and self.level[to] < 0:
                    self.level[to] = self.level[v] + 1
                    Q.append(to)

    def dfs(self, v, t, f):
        if v == t: return f
        k = self.iter[v]
        while k < len(self.edge[v]):
            to, cap, rev = self.edge[v][k]
            if cap > 0 and self.level[v] < self.level[to]:
                d = self.dfs(to, t, f if f <= cap else cap)
                if d > 0:
                    self.edge[v][k][1] -= d
                    self.edge[to][rev][1] += d
                    return d
            self.iter[v] += 1
            k += 1
        return 0

    def maxFlow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0: break
            self.iter = [0] * self.V
            while True:
                f = self.dfs(s, t, INF)
                if f <= 0: break
                flow += f
        return flow

N, M = map(int, input().split())
dir = [[0 for j in range(N)] for i in range(N)]
id =  [[0 for j in range(N)] for i in range(N)]
d = Donic(N)
for i in range(M):
	x, y = map(int, input().split())
	x, y = x-1, y-1
	dir[y][x] = 1
	id[y][x] = i+1
	d.add_edge(x, y, 1)
S, T = map(int, input().split())
print(d.maxFlow(S-1, T-1))

ans = []
for i in range(N):
	for to, cap, rev in d.edge[i]:
		if cap < 1 and dir[i][to]: ans.append(id[i][to])
ans.sort()
print(len(ans))
if len(ans) > 0: print(*ans, sep='\n')

Submission status: Accepted

Solution code:
# AOJ 2304 Reverse Roads
# Python3 2018.7.21 bal4u

# *******************************************
# Dinic's Max Flow Algorithm
# *******************************************
class MaxFlow:
    def __init__(self, V):
        self.V = V
        self.level = [0] * V
        self.iter = [0] * V
        self.edge = [[] for i in range(V)]

    def add_edge(self, fr, to, cap):
        f, t = len(self.edge[fr]), len(self.edge[to])
        self.edge[fr].append([to, cap, t])
        self.edge[to].append([fr, cap, f])

    def bfs(self, s):
        self.level = [-1] * self.V
        self.level[s] = 0
        Q = []
        Q.append(s)
        while Q:
            v = Q.pop()
            for to, cap, rev in self.edge[v]:
                if cap > 0 and self.level[to] < 0:
                    self.level[to] = self.level[v] + 1
                    Q.append(to)

    def dfs(self, v, t, f):
        if v == t: return f
        for i in range(self.iter[v], len(self.edge[v])):
            to, cap, rev = self.edge[v][i]
            if cap > 0 and self.level[v] < self.level[to]:
                d = self.dfs(to, t, min(f, cap))
                if d > 0:
                    self.edge[v][i][1] -= d
                    self.edge[to][rev][1] += d
                    return d
            self.iter[v] = i
        return 0

    def maxFlow(self, s, t, INF=10**8):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0: break
            self.iter = [0] * self.V
            while True:
                f = self.dfs(s, t, INF)
                if f <= 0: break
                flow += f
        return flow

N, M = map(int, input().split())
dir = [[0 for j in range(N)] for i in range(N)]
id =  [[0 for j in range(N)] for i in range(N)]
d = MaxFlow(N)
for i in range(M):
	x, y = map(int, input().split())
	x, y = x-1, y-1
	dir[y][x] = 1
	id[y][x] = i+1
	d.add_edge(x, y, 1)
S, T = map(int, input().split())
print(d.maxFlow(S-1, T-1))

ans = []
for i in range(N):
	for to, cap, rev in d.edge[i]:
		if cap < 1 and dir[i][to]: ans.append(id[i][to])
ans.sort()
print(len(ans))
if len(ans) > 0: print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import collections


class MaxFlow:
    """Dinic Algorithm: find max-flow
       complexity: O(EV^2)
       used in GRL6A(AOJ)
    """
    class Edge:
        def __init__(self, to, cap, rev):
            self.to, self.cap, self.rev = to, cap, rev

    def __init__(self, V):
        """ V: the number of vertexes
            E: adjacency list
            source: start point
            sink: goal point
        """
        self.V = V
        self.E = [[] for _ in range(V)]

    def add_edge(self, fr, to, cap):
        self.E[fr].append(self.Edge(to, cap, len(self.E[to])))
        self.E[to].append(self.Edge(fr, 0, len(self.E[fr])-1))

    def dinic(self, source, sink, INF=10**9):
        """find max-flow"""
        maxflow = 0
        while True:
            self.bfs(source)
            if self.level[sink] < 0:
                return maxflow
            self.itr = [0] * self.V
            while True:
                flow = self.dfs(source, sink, INF)
                if flow > 0:
                    maxflow += flow
                else:
                    break

    def dfs(self, vertex, sink, flow):
        """find augmenting path"""
        if vertex == sink:
            return flow
        for i in range(self.itr[vertex], len(self.E[vertex])):
            self.itr[vertex] = i
            e = self.E[vertex][i]
            if e.cap > 0 and self.level[vertex] < self.level[e.to]:
                d = self.dfs(e.to, sink, min(flow, e.cap))
                if d > 0:
                    e.cap -= d
                    self.E[e.to][e.rev].cap += d
                    return d
        return 0

    def bfs(self, start):
        """find shortest path from start"""
        que = collections.deque()
        self.level = [-1] * self.V
        que.append(start)
        self.level[start] = 0

        while que:
            fr = que.popleft()
            for e in self.E[fr]:
                if e.cap > 0 and self.level[e.to] < 0:
                    self.level[e.to] = self.level[fr] + 1
                    que.append(e.to)
N, M = map(int, input().split())
mf = MaxFlow(N)
rev_edge = []
for i in range(M):
    s, t = [int(x)-1 for x in input().split()]
    mf.add_edge(s, t, 1)
    mf.add_edge(t, s, 1)
    rev_edge.append((i+1, t, len(mf.E[t])-1))
source, sink = [int(x)-1 for x in input().split()]
print(mf.dinic(source, sink))
ans = []
for i, t, idx in rev_edge:
    e = mf.E[t][idx]
    if mf.E[e.to][e.rev].cap == 1:
        ans.append(i)
print(len(ans))
if ans:
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import collections
class Dinic:
    refs = {}
    def __init__(self, n):
        self.n = n
        self.g = [[] for i in xrange(n)]
    def add_edge(self, fr, to, cap):
        self.g[fr].append([to, cap, len(self.g[to])])
        self.g[to].append([fr, 0, len(self.g[fr])-1])
    def add_multi_edge(self, v1, v2, cap1, cap2):
        ref = [v2, cap1, len(self.g[v2])]
        self.g[v1].append(ref)
        self.g[v2].append([v1, cap2, len(self.g[v1])-1])
        self.refs[v1, v2] = ref
    def bfs(self, s):
        level = [-1]*self.n
        deq = collections.deque()
        level[s] = 0
        deq.append(s)
        while deq:
            v = deq.popleft()
            for e in self.g[v]:
                if e[1]>0 and level[e[0]]<0:
                    level[e[0]] = level[v] + 1
                    deq.append(e[0])
        self.level = level
    def dfs(self, v, t, f):
        if v==t: return f
        es = self.g[v]
        level = self.level
        for i in xrange(self.it[v], len(self.g[v])):
            e = es[i]
            if e[1]>0 and level[v]<level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d>0:
                    e[1] -= d
                    self.g[e[0]][e[2]][1] += d
                    self.it[v] = i
                    return d
        self.it[v] = len(self.g[v])
        return 0
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0: break
            self.it = [0]*self.n
            while True:
                f = self.dfs(s, t, 10**9+7)
                if f>0:
                    flow += f
                else:
                    break
        return flow
n, m = map(int, raw_input().split())
dinic = Dinic(n)
es = []
for i in xrange(m):
    x, y = map(int, raw_input().split())
    dinic.add_multi_edge(x-1, y-1, 1, 1)
    es.append((x-1, y-1))
s, t = map(int, raw_input().split())
f = dinic.max_flow(s-1, t-1)
print f
ans = []
for i, e in enumerate(es):
    if dinic.refs[e][1]>1:
        ans.append(i+1)
print len(ans)
if ans:
    print "\n".join(map(str, ans))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class Flow():
    def __init__(self, e, N):
        self.E = e
        self.N = N

    def max_flow(self, s, t):
        r = 0
        e = self.E

        def f(c):
            v = self.v
            v[c] = 1
            if c == t:
                return 1
            for i in range(self.N):
                if v[i] == 0 and e[c][i] > 0 and f(i) > 0:
                    e[c][i] -= 1
                    e[i][c] += 1
                    return 1
            return 0

        while True:
            self.v = [0] * self.N
            if f(s) == 0:
                break
            r += 1

        return r

def main():
    rr = []

    def f(n,m):
        a = [LI_() for _ in range(m)]
        s,t = LI_()
        e = [[0]*n for _ in range(n)]
        for x,y in a:
            e[x][y] = 1
            e[y][x] = 1
        fl = Flow(e, n)
        r = fl.max_flow(s,t)
        re = []
        for i in range(m):
            x,y = a[i]
            if e[y][x] == 0:
                re.append(i+1)
        return [r,len(re)] + re

    while 1:
        n,m = LI()
        if n == 0:
            break
        rr.extend(f(n,m))
        # print('rr', rr[-1])
        break

    return '\n'.join(map(str,rr))


print(main())