记录编号	433133	评测结果	AAAAA
题目名称	[Tyvj国庆欢乐赛] 武器分配	最终得分	100
用户昵称	AAAAAAAAAA	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-08-04 22:02:58	内存使用	0.21 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define MAXN 200
#define INF 0x3f3f3f3f
using namespace std;
struct Edge {
	int f, t, next, v, c;
}e[MAXN*MAXN];
int N, A, B, cnt = 1, head[MAXN], dis[MAXN], pre[MAXN], f[MAXN], S, T, ans;
bool vis[MAXN];
void Add_Edge(int from, int to, int cap, int cost) {
	e[++cnt].t = to;e[cnt].f = from;e[cnt].next = head[from];head[from] = cnt;e[cnt].v = cap;e[cnt].c = cost;
	e[++cnt].t = from;e[cnt].f = to;e[cnt].next = head[to];head[to] = cnt;e[cnt].v = 0;e[cnt].c = -cost;
}
bool SPFA() {
	memset(dis, INF, sizeof(dis));
	queue<int>q;
	q.push(S);f[S] = INF;vis[S] = 1;dis[S] = 0;
	while (!q.empty()) {
		int u = q.front();q.pop();vis[u] = 0;
		for (int i = head[u];i;i = e[i].next) {
			if (e[i].v&&dis[e[i].t] > dis[u] + e[i].c) {
				dis[e[i].t] = dis[u] + e[i].c;
				pre[e[i].t] = i;
				f[e[i].t] = min(f[u], e[i].v);
				if (!vis[e[i].t])q.push(e[i].t), vis[e[i].t] = 1;
			}
		}
	}
	if (dis[T] == INF)return 0;
	return 1;
}
void Mcmf() {
	for (int i = pre[T];i;i = pre[e[i].f]) e[i].v -= f[T], e[i ^ 1].v += f[T];
	ans += f[T] * dis[T];
}
int a[MAXN], b[MAXN];
int sb() {
	freopen("weapon.in", "r", stdin);
	freopen("weapon.out", "w", stdout);
	scanf("%d%d%d", &N, &A, &B);
	S = 0;T = A + B + 2;
	for (int i = 1;i <= A;i++) {
		scanf("%d", &a[i]); 
		Add_Edge(S, i, 1, 0);
	}
	for (int i = 1;i <= B;i++) {
		scanf("%d", &b[i]);
		Add_Edge(i + A, T - 1, 1, 0);
	}
	for (int i = 1;i <= A;i++) {
		for (int j = 1;j <= B;j++) {
			Add_Edge(i, j + A, 1, (a[i] - b[j])*(a[i] - b[j]));
		}
	}
	Add_Edge(T - 1, T, N, 0);
	while (SPFA()) Mcmf();
	printf("%d", ans);
	return 0;
}
int chh = sb();
int main() { ; }