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.
1842: Rikka with K-Match
时间限制: 25 Sec 内存限制: 128 MB提交: 3 解决: 1
[提交][状态][讨论版][命题人:]
题目描述
输入描述
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, 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.
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来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版