[UPC10622] Team

Description

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

Input is given from Standard Input in the following format:
N M
W1 W2 . . . W3N
A1 B1
.
.
.
AM BM
Constraints
1≤N, M≤103
1≤Wi≤109
1≤Ai, Bi≤3N (1≤i≤M, Ai≠Bi)
All inputs are integers.

Output

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.

Sample Input

2 1
1 2 3 4 5 6
3 4

Sample Output

4

Solution

Step 1. Disjoint Set
Step 2. Dynamic Programming

Code

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[1])
        count2 = len(team[2])
        dp = [[-1 for _ in range(count2 + 1)] for _ in range(count1 + 1)]
        dp[0][0] = 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[1][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[1][i],team[2][j]))
        print(dp[count1][count2])
Add New Comment