No.2914 Positive Cycle Detection
タグ : / 解いたユーザー数 29
作問者 : 👑
Problem Statement
At the beginning of the input, $2$ positive integers $N, M$ are given.
A village has $N$ squares and $M$ bidirectional roads connecting them.
The squares are numbered by the positive integers $i$ not exceeding $N$, and each is called square $i$.
The roads are numbered by the positive integers $j$ not exceeding $M$, and each is called road $j$. Road $j$ connects square $u_j$ and square $v_j$ ($u_j, v_j$ are distinct positive integers not exceeding $N$).
Chokushin Daisuki Bot is a bot that loves going straight along the roads of this village. An integer value called the refreshment level of Chokushin Daisuki Bot changes according to which road it goes along and in which direction.
Specifically, for any positive integer $j$ not exceeding $M$, when Chokushin Daisuki Bot goes along road $j$ from square $u_j$ toward square $v_j$, its refreshment level increases by $w_j$, and when it goes in the opposite direction, its refreshment level decreases by $w_j$ ($w_j$ is a non-negative integer).
Chokushin Daisuki Bot is searching for routes that start from some square of this village, go only straight along roads, and return to the original square, and that satisfy the following $2$ conditions. It calls such a route a refreshing route.
- The route does not pass through the same road twice, regardless of direction.
- The refreshment level at the time of return is higher than the refreshment level at the time of departure.
Find a refreshing route on behalf of Chokushin Daisuki Bot.
Input
The input is given from standard input in $1 + M$ lines in the following format:
- Line $1$ contains $N, M$ separated by a half-width space.
- For each positive integer $j$ not exceeding $M$, line $1 + j$ contains $u_j , v_j , w_j$ separated by half-width spaces.
$N$ $M$ $u_1$ $v_1$ $w_1$ $\vdots$ $u_M$ $v_M$ $w_M$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $2 \leq N \leq 10^5$.
- $M$ is an integer satisfying $1 \leq M \leq 10^5$.
- For any positive integer $j$ not exceeding $M$,
- $u_j, v_j$ are integers satisfying $u_j \neq v_j$, $1 \leq u_j \leq N$, and $1 \leq v_j \leq N$.
- $w_j$ is an integer satisfying $0 \leq w_j \leq 10^5$.
Output
If no refreshing route exists, output -1.
-1
If a refreshing route exists, output $1$ of them in $3$ lines in the following format:
- On line $1$, output the positive integer $L$ representing the number of roads passed through.
- On line $2$, output the number of the starting square.
- On line $3$, output the numbers of the $L$ roads in the order they are passed through, separated by half-width spaces.
$L$ (出発する広場に対応する番号) ($1$ 本目に通る道に対応する番号) $\cdots$ ($L$ 本目に通る道に対応する番号)
This is a special judge problem. If there are multiple correct answers, you may output any of them.
However, follow the output format described above. For example, the behavior of the judge is not guaranteed if you add extra trailing whitespace.
Print a newline at the end.
Sample
Sample 1
Input
2 1 1 2 1
Output
-1
No refreshing route exists. Road $1$ connects square $1$ and square $2$, but since there are no other roads, whichever square you start from, you cannot return to the original square without passing through the same road twice.
Sample 2
Input
2 2 1 2 0 2 1 1
Note that, as in this case, multiple roads may connect the same pair of squares.
Output
2 1 1 2
Road $1$ connects square $1$ and square $2$, and going along road $1$ in either direction does not change the refreshment level.
Road $2$ connects square $2$ and square $1$. Going along road $2$ from square $2$ toward square $1$ increases the refreshment level by $1$, and going in the opposite direction decreases it by $1$.
Therefore, by starting from square $1$ and going along road $1$ and then road $2$, it is possible to return to square $1$ with the refreshment level increased by $1$.
Other correct outputs include, for example, the following:
2 2 2 1
This output is also accepted.
Sample 3
Input
3 3 1 2 1 2 3 2 1 3 3
Output
-1
No refreshing route exists. For example, even if you start from square $1$, go along road $1$, road $2$, and road $3$ in this order, and return to square $1$, the final change in the refreshment level is $1 + 2 - 3 = 0$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。