Untitled
unknown
java
3 years ago
1.9 kB
4
Indexable
import java.io.*; import java.util.*; public class equalizing_money { static int N = 1005; static int[] bal = new int[N]; static boolean[] vis = new boolean[N]; static int sz, tot; public static void main(String[] args) { Scanner input = new Scanner(System.in); int T = input.nextInt(); for (int t = 1; t <= T; ++t) { int n = input.nextInt(); int m = input.nextInt(); int need = 0; for (int i = 1; i <= n; ++i) { bal[i] = input.nextInt(); vis[i] = false; need += bal[i]; } System.out.printf("Case %d: ", t); if (n == 0) tle(); if (need % n != 0) { System.out.println("No"); } else { Graph G = new Graph(n); for (int i = 0; i < m; ++i) { int u = input.nextInt(); int v = input.nextInt(); G.add(u, v); } need /= n; boolean ye = true; for (int i = 1; i <= n; ++i) { if (!vis[i]) { sz = 0; tot = 0; G.dfs(i); if (tot % sz != 0) { ye = false; break; } else { if (need != tot / sz) { ye = false; break; } } } } System.out.println(ye ? "Yes" : "No"); } } } static class Graph { private final int n; private final LinkedList<Integer>[] adj; public Graph(int _n) { n = _n + 2; adj = new LinkedList[N]; for (int i = 0; i < N; ++i) { adj[i] = new LinkedList<>(); } } void add(int u, int v) { adj[u].add(v); adj[v].add(u); } void dfs(int v) { ++sz; tot += bal[v]; vis[v] = true; for (int u : adj[v]) { if (!vis[u]) { dfs(u); } } } } }
Editor is loading...