25927번 - Parity Constraint Maximum Flow 서브태스크스페셜 저지

flow network $(G, c, s, t)$는 다음과 같이 정의된다.

• $G$는 방향 그래프 $(V, E)$를 의미한다.
• $c : E \rightarrow \mathbb{R}^+$는 간선의 capacity를 나타내는 함수다.
• $s, t \in V$는 각각 source와 sink를 의미하고, $s \ne t$를 만족한다.

주어진 flow network $(G, c, s, t)$에 대한 $s$-$t$ flow $f$는 다음과 같이 정의된다.

• 모든 $e \in E$에 대해서 $0 \le f(e) \le c(e)$를 만족한다.
• 모든 $v \in V-\{s, t\}$에 대해서 $\displaystyle \sum_{(u,v) \in E} f(u,v)= \sum_{(v,w) \in E} f(v,w)$를 만족해야 한다.

이때, flow $f$의 값은 $\displaystyle |f| = \sum_{(s,v) \in E} f(s,v) - \sum_{(v,s) \in E} f(v,s) = \sum_{(v,t) \in E} f(v,t) - \sum_{(t,v) \in E} f(t,v)$로 정의된다.

maximum flow는 주어진 flow network $(G, c, s, t)$에 대한 $s$-$t$ flow 중 값이 최대인 $s$-$t$ flow를 의미한다. 모든 $c(e)$가 정수라면, 모든 $f(e)$가 정수인 maximum flow $f$를 다항 시간에 구할 수 있음이 알려져 있다. 이에 대한 다항 시간 알고리즘의 예시로, 시간 복잡도 $O(VE^2)$의 Edmonds-Karp Algorithm과 시간 복잡도 $O(V^2 E)$의 Dinic's Algorithm이 있다.

여기에 추가로 함수 $p : E \rightarrow \{ 0, 1 \}$이 주어진다. 이 때, 우리는 다음 조건을 만족하는 $s$-$t$ flow $f$를 parity constraint flow라고 할 것이다.

• 모든 $e \in E$에 대해서 $f(e)$는 정수여야 한다.
• $f(e) \equiv p(e)$ $mod$ $2$

parity constraint flow 중 값이 최대인 것을 parity constraint maximum flow라고 할 것이다.

flow network $(G, c, s, t)$와 함수 $p$가 주어졌을 때, 이에 대한 parity constraint maximum flow를 구해보자.

$N$과 $M$은 주어진 그래프 $G=(V, E)$의 정점의 개수와 간선의 개수를 의미한다

$u_i$와 $v_i$는 $u_i$에서 $v_i$로 향하는 간선이 있음을 의미하고, $c_i$와 $p_i$는 각각 $c(u_i, v_i)$와 $p(u_i, v_i)$를 의미한다.

이때, 입력은 다음과 같이 주어진다.

첫 번째 줄에는 parity constraint maximum flow $f$의 값을 출력한다. 만약에 parity constraint flow가 존재하지 않는다면 -1을 출력한다.

만약에 parity constraint flow가 존재한다면, $i = 1, \cdots, M$에 대해서 $(i+1)$번째 줄에 $f(u_i, v_i)$의 값을 출력한다.

답이 여러 개가 있는 경우, 그중 아무것이나 출력하면 된다.

• $2 \le N \le 300$
• $\displaystyle 1 \le M \le 23\,000$
• $1 \le s, t \le N$, $s \ne t$
• $1 \le u_i, v_i \le N$, $u_i \ne v_i$
• $u_i \ne t$, $v_i \ne s$
• $1 \le c_i \le 1\,000\,000\,000$
• $p_i \in \{0, 1\}$
• 두 정점 사이에 두 개 이상의 간선이 있는 그래프는 주어지지 않는다.
• 입력에 주어진 수들은 전부 정수다.