Untitled
unknown
java
4 years ago
1.9 kB
6
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...