hdu 5520 Number Link(费用流)

Problem Description
Number Link is a famous game available in platforms including iOS and Android. Given a board with n rows and m columns, the target of the game is to connect pairs of grids with the same numbers. Once two numbers are paired, the path connecting them will occupy the corresponding grids. The path can only go vertically or horizontally. Note that, no two paths could intersect (by sharing the same grid) in any grid. In this problem, you are going to play a modified version, called Number Link ++. See the picture below for an example.

In this new game, you can use two types of paths. Type I is to connect two number grids with different parities (i.e., connect odd number with any other even number). It might be hard to cover the entire grid with only type I path, so we allow type II path, which is a circle path covers only the empty grids (the only special case of type II path is a path only connecting two adjacent empty grids; see the figure above). Since there is no free lunch, we have no free path either. When goes from grid (a,b)to an adjacent grid (c,d), you have to pay for a certain amount of tolls. The cost is the same when goes back from (c,d) to (a,b). Usually the cost of a path is the sum of tolls you paid by traveling along the grids on this path. The only exception is for the special case of type II path. In that case, you have to pay twice the cost (since it is a circle).
The total cost of the game is the sum of costs for all the paths. Can you help me figure out the paths so that each grid is on exactly one path? If there exists such solution, what is the minimum possible cost?

 

Input
The first line of input consists of an integer T, which is the number of test cases.
Each case begins with two integers, n and m, in a line (1n,m50).
The next n lines describe the board. Each line consists of m nonnegative numbers, which describe the status of each column from left to right. If the number is zero, then the grid is empty; otherwise it indicates the number on the corresponding grid.
The next n1 lines each have m nonnegative numbers, which describe the cost of vertical connection. The j-th number in i-th line is the cost when travels from grid (i,j) to (i+1,j).
The next n lines each have m1 nonnegative numbers, which describe the cost of horizontal connection. The j-th number in i-th line is the cost for a path to go from grid (i,j) to (i,j+1).
All the numbers, including the answer, can be represented using 32-bit signed integer.

 

Output
For each test case, first output the case number, then output a single number, which is the minimum cost possible to finish the game. When there is no solution available, simply output -1.

 

Sample Input
3 3 3 1 0 0 1 0 0 2 0 2 1 2 1 2 1 1 3 1 5 6 1 4 1 4 1 1 2 2 1 2 3 3 5 0 0 0 0 0 0 5 0 6 0 0 0 0 0 0 1 1000 1000 1000 1 1 1000 1000 1000 1 1 1 1 1 1000 1 1 1000 1 1 1 1

 

Sample Output
Case #1: 10 Case #2: -1 Case #3: 14

Hint

Below are the solutions corresponding to case 1 and case 3 respectively. In case 1, you should double pay the red path, since it is a special case of type II path.

训练的时候看到这个题,感觉非常网络流的样子,但是思考了半天发现不会建图,不知道该怎么处理路径和环,而且题目描述里面也没有讲到底可不可以奇数到偶数的路径上有数字格子。
后来看了看题解发现应该不能出现数字格子。。。
建图非常神奇,也是开阔思路了。以往这种每个格子必须要经过也只能经过一次的题,我们都是拆点解决。这倒也不例外,但是这道题格子的入点和出点并不连边。具体来说就是:超级源S向奇数格子和所有空格子的入点连(1,0)的边,偶数点和所有空格子的出点向汇点连(1,0)的边,然后每个点的入点向相邻格子的出点连(1,cost)的边,然后MCMF。
我们思考一下这样建图的意义,那么此时一单位流量,必然是从一个入点到另外一个相邻点的出点,相当于一个格子向相邻格子连了一条有向边。环的本质也就是每个点都有一个入度一个出度,而我们有解的话也就是所有入边都满流了的话,那么一定是保证了出度和入度的。而路径是奇数为起点,偶数为终点,同理也是保证了奇数只有一个入度,偶数只有一个出度。
据说还可以上下界,但是不大会QAQ,bzoj 上倒是有个类似的题目,只是费用计算的方式不大一样,回来歇一歇。。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注