题干：
 

众所周知，在各种对抗类游戏里装备都是很重要的一环，不同的出装方案会给玩家带来不同的强度。

dalao手里有N件装备，现在dalao要把装备分给N个队友，每个队友只能分一件装备，而每个队友穿上不同的装备会有不同程度的强度提升。

现在给出每个队友对每件装备的强度提升的值，请问dalao的所有分配方案里，最多能让团队的总强度提升多少呢？

输入描述:


 

第一行有一个整数T，表示数据的组数（不会超过150组）

每组数据第一行包含一个整数N，接下来会有N行，每行有N个整数，其中第 a 行的第 b 个数字表示第 a 个队友穿上第 b 件装备的强度提升。任何队员穿任何装备的强度提升都不会超过20000。

 

输出描述:

对于每组数据在一行内输出一个整数表示强度能够提升的最大值

示例1

输入

复制

2
4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 3 5
2 4 6
7 9 11

输出

复制

34
16

解题报告：

   不难发现其实就是个二分最优匹配，可以选择KM算法或者费用流来解决这个问题。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
using namespace std;

const int MAXN = 70000;
const int MAXM = 100005;
const int INF = 0x3f3f3f3f;
struct Edge {
	int to,next,cap,flow,cost;
} edge[MAXM];
int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N;
void init(int n) {
	N = n;
	tol = 0;
	memset(head, -1,sizeof(head));
}
void addedge(int u,int v,int cap,int cost) {
	edge[tol].to = v;
	edge[tol].cap = cap;
	edge[tol].cost = cost;
	edge[tol].flow = 0;
	edge[tol].next = head[u];
	head[u] = tol++;
	edge[tol].to = u;
	edge[tol].cap = 0;
	edge[tol].cost = -cost;
	edge[tol].flow = 0;
	edge[tol].next = head[v];
	head[v] = tol++;
}
bool spfa(int s,int t) {
	queue<int>q;
	for(int i = 0; i <= N; i++) {
		dis[i] = INF;
		vis[i] = false;
		pre[i] = -1;
	}
	dis[s] = 0;
	vis[s] = true;
	q.push(s);
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		vis[u] = false;
		for(int i = head[u]; i !=-1; i = edge[i].next) {
			int v = edge[i].to;
			if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge
			        [i].cost ) {
				dis[v] = dis[u] + edge[i].cost;
				pre[v] = i;
				if(!vis[v]) {
					vis[v] = true;
					q.push(v);
				}
			}
		}
	}
	if(pre[t] ==-1)return false;
	else return true;
}
int minCostMaxflow(int s,int t,int &cost) {
	int flow = 0;
	cost = 0;
	while(spfa(s,t)) {
		int Min = INF;
		for(int i = pre[t]; i !=-1; i = pre[edge[i^1].to]) {
			if(Min > edge[i].cap-edge[i].flow)
				Min = edge[i].cap-edge[i].flow;
		}
		for(int i = pre[t]; i !=-1; i = pre[edge[i^1].to]) {
			edge[i].flow += Min;
			edge[i^1].flow-= Min;
			cost += edge[i].cost * Min;
		}
		flow += Min;
	}
	return flow;
}
int main()
{
	int n;
	int t;
	cin>>t;
	while(t--) {
	scanf("%d",&n);
		//int st=0,ed=n1+n2+1;
		int st = 0,ed=n*2+1;
		init(ed+1);
		int a,b,w;
		for(int i = 1; i<=n; i++) {
			for(int j = n+1; j<=2*n; j++) {
				scanf("%d",&w);
				addedge(i,j,1,-w);
			}
		}
		for(int i = 1; i<=n; i++) addedge(st,i,1,0);
		for(int i = n+1; i<=2*n; i++) addedge(i,ed,1,0);
		int cost;
		int ans = minCostMaxflow(st,ed,cost);
		printf("%d\n",-cost);
	}
	return 0 ;
}