去年哈爾濱網(wǎng)絡(luò)預(yù)選賽的一道題目,當(dāng)初題目沒有讀懂，Yi大牛用浙大KM板子A掉此題。心中一直留有遺憾，回頭再看，發(fā)現(xiàn)建模是如此重要。數(shù)與圖的結(jié)合還是很緊密的。
題意:給出一個集合U,和一些搜索引擎對該集合的排序，要求出一個最酷的引擎，該搜索引擎的結(jié)果滿足條件
其中
。解法:該搜索引擎的結(jié)果總數(shù)是集合U大小的排列，集合U最大有100，所以枚舉是肯定不行的。此題的建模我覺得還是挺巧妙地，因為題目中要求的值F(A,B1,...,Bm)是A的排序結(jié)果和其它B的排序結(jié)果的差值總和，這樣對于集合U中的每個元素建立一個節(jié)點，建立二分圖，左邊代表所有B的第i個列,右邊為集合U的數(shù)值(從0到n-1),對于左邊的每一列求出對應(yīng)的所有的B的i列與右邊節(jié)點所有值的差的絕對值,然后用KM求出該圖的最小匹配即可。理解:只需要求出F(A,B1,...,Bm)的最小值，無需求出A的排列結(jié)果，所以對應(yīng)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;
}