N개의 정점과 M개의 간선으로 구성된 무방향 단순 연결 그래프가 있다. 그래프의 정점들에는 1 이상 N 이하의 서로 다른 자연수 번호가 붙어 있고, 간선들에는 1 이상 M 이하의 서로 다른 자연수 번호가 붙어 있다.

j (1 ≤ j ≤ M)번 간선은 a_j번 정점과 b_j번 정점을 연결하며, 정수 가중치 c_j가 붙어 있다.

당신은 모든 정점에 정수 가중치를 부여해야 한다. i (1 ≤ i ≤ N)번 정점에 부여할 가중치를 x_i라고 하자.

정점에 가중치를 부여하는 총 비용은 각 정점의 가중치의 절댓값의 합, 즉 \left|x_1\right|+\left|x_2\right|+\cdots\left|x_N\right| = \displaystyle \sum^N_{i=1}\left|x_i\right|과 같다.

그래프의 균형이 맞으려면, 각 간선이 연결하고 있는 두 정점의 가중치의 합이 간선의 가중치와 같아야 한다. 즉, 모든 j (1 ≤ j ≤ M)에 대해, x_{a_j} + x_{b_j}이 c_j와 같아야 한다.

예를 들어, 아래와 같이 5개의 정점과 4개의 간선으로 이루어진 그래프를 생각하자. 그림에서 정점을 나타내는 원 안에 적힌 수는 정점의 번호이고, 간선을 나타내는 선에 적힌 수는 간선에 붙은 가중치이다.

아래의 그림과 같이 각 정점에 [2, -7, 3, -5, 0]의 가중치를 부여해서, 각 간선이 연결하고 있는 두 정점의 가중치의 합이 간선의 가중치와 같게 할 수 있다. 아래 그림에서 정점을 나타내는 원 안에 적힌 수는 정점의 가중치이다.

총 비용은 |2| + |−7| + |3| + |−5| + |0| = 2 + 7 + 3 + 5 + 0 = 17이다. 총 비용을 17보다 작게 할 수 있는 방법은 없기 때문에, 위 방법은 총 비용을 최소화하는 방법이다.

아래와 같이 각 정점에 [6, -3, -1, -9, 4]의 가중치를 부여해도 균형이 맞는 그래프가 되지만, 이 경우 총 비용은 17보다 큰 23이 되기 때문에 아래 방법은 총 비용을 최소화하는 방법이 아니다.

그래프의 균형이 맞도록 정점에 가중치를 부여하는 것이 가능한지 확인하고, 가능하다면 그 중 총 비용을 최소화하는 방법을 하나 구하는 프로그램을 작성하라.

|x|는 x < 0이면 −x, x ≥ 0이면 x인 절댓값 기호이다.

그래프 균형 맞추기 timer 2s memory 1024MB

그래프 균형 맞추기 2s 1024MB