Responsive image

问题 J: Rikka with K-Match

问题 J: Rikka with K-Match

时间限制: 25 Sec  内存限制: 128 MB
提交: 3  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Yuta has a graph G with n nodes (i,j)(1≤i≤n,1≤j≤m). There is an edge between (a,b) and (c,d) if and only if |a−c|+|b−d|=1. Each edge has its weight.

Now Yuta wants to calculate the minimum weight K-matching of G.

It is too difficult for Rikka. Can you help her?  

An edge set S is a match of G=⟨V,E⟩ if and only if each nodes in V connects to at most one edge in S. A match S is a K-match if and only if |S|=K. The weight of a match S is the sum of the weights of the edges in S. And finally, the minimum weight K-matching of G is defined as the K-match of G with the minimum weight.

输入描述

The first line contains a number t(1≤t≤1000), the number of the testcases. And there are no more than 3 testcases with n>100.

For each testcase, the first line contains three numbers n,m,K(1≤n≤4×104,1≤m≤4),1≤K≤⌊nm2⌋.

Then n−1 lines follow, each line contains m numbers Ai,j(1≤Ai,j≤109) -- the weight of the edge between (i,j) and (i+1,j).

If m>1, then n lines follow, each line contains m−1 numbers Bi,j(1≤Bi,j≤109) -- the weight of the edge between (i,j) and (i,j+1).

输出描述

For each testcase, print a single line with a single number -- the answer.
It is guaranteed that there exists at least one K-match.

样例输入

3
3 3 1
3 4 5
8 9 10
1 2
6 7
11 12
3 3 2
3 4 5
8 9 10
1 2
6 7
11 12
3 3 3
3 4 5
8 9 10
1 2
6 7
11 12

样例输出

1
5
12
[提交][状态]
ACM算法攻关部