ACM-ICPC is a interesting game. A team takes part in this game must consist of exactly (no more and no less) three players. Every year, many new members will join the FZU ACM team. How to form teams becomes a big problem.
There are 3N members this year. Each member has a power Wi. If three distinct members x, y, z form a team, the power of this team is the minimum value of Wx, Wy, Wz.
There are M pairs of relationship called best friend. If member A and member B are best friend, they must be in the same team.
We want to form N teams, and get the maximum sum of the power of these N teams. Can you help us?
Input is given from Standard Input in the following format:
W1 W2 . . . W3N
1≤Ai, Bi≤3N (1≤i≤M, Ai≠Bi)
All inputs are integers.
If it is possible to form N teams, print one integer denotes the maximum sum of the power of these N teams. Otherwise print -1.
2 1 1 2 3 4 5 6 3 4
Step 1. Disjoint Set
Step 2. Dynamic Programming
class UnionFindSet(object): def __init__(self, n): self.father = [i for i in range(n + 1)] self.count = [1 for _ in range(n + 1)] self.value = [0 for _ in range(n + 1)] def union(self, p, q): proot = self.find(p) qroot = self.find(q) if proot != qroot: self.father[qroot] = proot self.count[proot] += self.count[qroot] self.value[proot] = min(self.value[proot], self.value[qroot]) def find(self, p): if self.father[p] == p: return p self.father[p] = self.find(self.father[p]) return self.father[p] if __name__ == '__main__': while(True): n, m = map(int, input().split(' ')) ufs = UnionFindSet(3 * n) for i, value in enumerate(map(int, input().split(' '))): ufs.value[i + 1] = value for i in range(m): a, b = map(int, input().split(' ')) ufs.union(a, b) team = [ for _ in range(4)] for i in range(1, 3 * n + 1): if(ufs.count[i] > 3): print(-1) break if(ufs.father[i] == i): team[ufs.count[i]].append(ufs.value[i]) for i in range(1,4): team[i].sort(reverse = False) count1 = len(team) count2 = len(team) dp = [[-1 for _ in range(count2 + 1)] for _ in range(count1 + 1)] dp = sum(team(3)) for i in range(count1): for j in range(count2 + 1): if(dp[i][j] != -1): if(i + 3 <= count1): dp[i + 3][j] = max(dp[i + 3][j],dp[i][j]+team[i]) if(i + 1 <= count1 and j + 1 <= count2): dp[i + 1][j + 1] = max(dp[i + 1][j + 1],dp[i][j]+min(team[i],team[j])) print(dp[count1][count2])