시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 55 | 12 | 11 | 37.931% |
We are considering a maximum flow problem on an infinite network.
You are given a bipartite graph $G$ with $n$ vertices in both parts and $m$ directed edges. Each edge goes from the left part to the right part, and has its capacity specified. We want to construct a family of networks $\{F_k\}$.
Here are the steps to construct the network $F_k$.
Let $f_k$ be the maximum flow in the network $F_k$.
We want to know what the sequence $\{f_k\}$ looks like when $k$ goes to infinity. If $\{f_k\}$ does not converge to a constant, output $-1$. Otherwise, output $\lim\limits_{k \to +\infty} f_k$.
The first line contains two integers $n$ and $m$ ($1 \leq n \leq 2000$, $1 \leq m \leq 4000$).
Each of the following $m$ lines contains three integers $u$, $v$, and $w$ ($1 \leq u, v \leq n$, $1 \leq w \leq 10^5$) which indicate that there is a directed edge from the $u$-th vertex in the left part to the $v$-th vertex in the right part with capacity $w$.
If the sequence $\{f_k\}$ does not converge to a constant, output $-1$. Otherwise, output $\lim\limits_{k \to +\infty} f_k$.
5 5 1 2 3 2 3 4 3 1 2 4 5 6 5 4 3
12