去年哈尔滨网络预选赛的一道题目,当初题目没有读懂，Yi大牛用浙大KM板子A掉此题。心中一直留有遗憾，回头再看，发现建模是如此重要。数与图的结合还是很紧密的。
题意:给出一个集合U,和一些搜索引擎对该集合的排序，要求出一个最酷的引擎，该搜索引擎的结果满足条件
其中
。解法:该搜索引擎的结果总数是集合U大小的排列，集合U最大有100，所以枚举是肯定不行的。此题的建模我觉得还是挺巧妙地，因为题目中要求的值F(A,B1,...,Bm)是A的排序结果和其它B的排序结果的差值总和，这样对于集合U中的每个元素建立一个节点，建立二分图，左边代表所有B的第i个列,右边为集合U的数值(从0到n-1),对于左边的每一列求出对应的所有的B的i列与右边节点所有值的差的绝对值,然后用KM求出该图的最小匹配即可。理解:只需要求出F(A,B1,...,Bm)的最小值，无需求出A的排列结果，所以对应A中的每一个元素都和B有一个差值，所以只需求出这个最小的差值即可。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 105
#define INF 1 << 28
#define MAX(a, b) (a > b ? a : b)
#define MIN(a, b) (a < b ? a : b)
inline int ABS(int x)
{
return x > 0 ? x:-x;
}
int match[N], x[N], y[N];
int lx[N], ly[N], g[N][N];
bool dfs(int u, int n)
{
x[u] = 1;
for(int i = 0; i < n; i++)
{
int wt = lx[u] + ly[i] - g[u][i];
if(!y[i] && !wt)
{
y[i] = 1;
if(match[i] == -1 || dfs(match[i], n))
{
match[i] = u;
return 1;
}
}
}
return 0;
}
int KM(int n)
{
memset(ly, 0, sizeof(ly));
memset(match, -1, sizeof(match));
for(int i = 0; i < n; i++)
{
lx[i] = -INF;
for(int j = 0; j < n; j++)
lx[i] = MAX(lx[i], g[i][j]);
}
for(int k = 0; k < n; k++)
{
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
while(!dfs(k, n))
{
int d = INF;
for(int i = 0; i < n; i++)
if(x[i])
for(int j = 0; j < n; j++)
if(!y[j])
d = MIN(d, lx[i] + ly[j] - g[i][j]);
for(int i = 0; i < n; i++)
{
if(x[i]) lx[i] -= d, x[i] = 0;
if(y[i]) ly[i] += d, y[i] = 0;
}
}
}
int sum = 0;
for(int i = 0; i < n; i++)
sum += g[match[i]][i];
return sum;
}
int main()
{
int t, n, m, b[N][N];
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
{
scanf("%d", &b[i][j]);
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
g[i][j] = 0;
for(int k = 0; k < m; k++)
{
g[i][j] -= ABS(b[k][i] - j);
}
}
}
int ans = -KM(n);
printf("%d\n", ans);
}
return 0;
}