# hdu 5933 ArcSoft’s Office Rearrangement（贪心）

Problem Description
ArcSoft, Inc. is a leading global professional computer photography and computer vision technology company.

There are N working blocks in ArcSoft company, which form a straight line. The CEO of ArcSoft thinks that every block should have equal number of employees, so he wants to re-arrange the current blocks into K new blocks by the following two operations:

– merge two neighbor blocks into a new block, and the new block’s size is the sum of two old blocks’.
– split one block into two new blocks, and you can assign the size of each block, but the sum should be equal to the old block.

Now the CEO wants to know the minimum operations to re-arrange current blocks into K block with equal size, please help him.

Input
First line contains an integer T, which indicates the number of test cases.

Every test case begins with one line which two integers N and K, which is the number of old blocks and new blocks.

The second line contains N numbers a1, a2, , aN, indicating the size of current blocks.

Limits
1T100
1N105
1K105
1ai105

Output
For every test case, you should output ‘Case #x: y’, where x indicates the case number and counts from 1 and y is the minimum operations.

If the CEO can’t re-arrange K new blocks with equal size, y equals -1.

Sample Input
3
1 3
14
3 1
2 3 4
3 6
1 2 3
Sample Output
Case #1: -1
Case #2: 2
Case #3: 3

# BZOJ 1050: [HAOI2006]旅行comf（并查集+kruskal）

## Description

给你一个无向图，N(N<=500)个顶点, M(M<=5000)条边，每条边有一个权值Vi(Vi<30000)。给你两个顶点S和T
，求一条路径，使得路径上最大边和最小边的比值最小。如果S和T之间没有路径，输出”IMPOSSIBLE”，否则输出

## Input

第一行包含两个正整数，N和M。下来的M行每行包含三个正整数：x，y和v。表示景点x到景点y之间有一条双向

1<N<=500,1<=x,y<=N，0<v<30000，0<M<=5000

## Output

如果景点s到景点t没有路径，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一

【样例输入1】
4 2
1 2 1
3 4 2
1 4
【样例输入2】
3 3
1 2 10
1 2 5
2 3 8
1 3
【样例输入3】
3 2
1 2 2
2 3 4
1 3

【样例输出1】
IMPOSSIBLE
【样例输出2】
5/4
【样例输出3】
2

5 6
3 2
2 0
0 3
0 4
3 2
3 2

4