|
#2
figo16882007-11-16 11:13
|
Problem F:分珠
Time Limit:1000MS Memory Limit:65536K
Total Submit:2 Accepted:0
Language: not limited
Description
如下图所示，有若干珠子，每颗珠子重量不同，珠子之间有一些细线将它们连在一起。现要求切断一些细线，将它们分成两部分，分割后，单独每一部分的珠子仍保持相连，且要求尽量做到两部分总重相等或相差最少。
请编一程序，给定珠子个数、每颗珠子的重量以及珠子之间的连接情况，输出按上述要求分割后两部分总重的差值的绝对值。
Input
第一行有两个数N与M（1<=N,M<=10），N为珠子个数（珠子编号依次为1，2，3，...，N），M为连接珠子的细线数目。第二行为N个正整数，分别为N个珠子的重量。此后M行，每行两个数X与Y，表示珠子X与珠子Y由细线相连。
Output
按要求分割后两部分总重的差值的绝对值。
Sample Input
5 5
1 2 3 4 1
1 2
1 3
2 3
3 4
4 5
Sample Output
1