uvalive 3276 The Great Wall Game

题意：

一个n * n的棋盘上放着n个棋子，现在要求把这n个棋子用最少的步数移到同一条直线上，即同一列同一行或者同一对角线（两条）。输出最少的步数（只能往四个方向移动，即正东，正西，正南，正北）。

思路：

每个棋子唯一对应一个格子，每个棋子不能在同一个格子，那么就相当于一个二分图（强行二分图）。

因为n很小，所以可以枚举每一行，每一列，两条对角线，然后每个点移动到每一条直线的每一个格子都有一个距离，那么这个点就向格子连一条权值为距离的边，这个问题就转化成了求所有最佳完美的匹配中的最小值，用KM算法。

因为我们求的是最小步数，所以求的是带权二分图的最小匹配。

求最小匹配，就将每一条边的权值取反，然后求最大匹配，再将最后的结果取反就得到了最小匹配的结果。

复杂度为O(n^4)。

注意：输出很坑，每一个答案后都有一个换行，并不是两个中间输出一个，也就是说，最后一个后面也有换行。

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 20;
const int inf = 0x3f3f3f3f;

int love[N][N];
int lx[N],ly[N];
bool visx[N],visy[N];
int match[N];
int slack[N];

struct node
{
    int x,y;
    
    node(int aa,int bb)
    {
        x = aa;
        y = bb;
    }
};

vector<node> vn;

int mabs(int x)
{
    return x >= 0 ? x : -x;
}

bool dfs(int u,int n)
{
    visx[u] = 1;
    
    for (int i = 1;i <= n;i++)
    {
        if (visy[i]) continue;
        
        int gap = lx[u] + ly[i] - love[u][i];
        
        if (gap == 0)
        {
            visy[i] = 1;
            
            if (match[i] == -1 || dfs(match[i],n))
            {
                match[i] = u;
                return true;
            }
        }
        else
        {
            slack[i] = min(gap,slack[i]);
        }
    }
    
    return false;
}

int km(int n)
{
    memset(match,-1,sizeof(match));
    memset(ly,0,sizeof(ly));
    
    for (int i = 1;i <= n;i++)
    {
        lx[i] = love[i][1];
        
        for (int j = 2;j <= n;j++)
        {
            lx[i] = max(lx[i],love[i][j]);
        }
    }
    
    for (int i = 1;i <= n;i++)
    {
        memset(slack,inf,sizeof(slack));
        
        while (1)
        {
            memset(visx,0,sizeof(visx));
            memset(visy,0,sizeof(visy));
            
            if (dfs(i,n)) break;
            
            int d = inf;
            
            for (int j = 1;j <= n;j++)
            {
                if (!visy[j]) d = min(d,slack[j]);
            }
            
            for (int j = 1;j <= n;j++)
            {
                if (visx[j]) lx[j] -= d;
                
                if (visy[j]) ly[j] += d;
            }
        }

    }
        
    
    int res = 0;
    
    for (int i = 1;i <= n;i++)
    {
        res += love[match[i]][i];
    }
    
    return res;
}

int main()
{
    int n;
    int kase = 0;
    
    while (scanf("%d",&n) != EOF && n)
    {
        vn.clear();
        
        for (int i = 0;i < n;i++)
        {
            int a,b;
            
            scanf("%d%d",&a,&b);
            
            vn.push_back(node(a,b));
        }
        
        //if (kase) printf("
");
        
        int ans = 1e8;
        
        for (int i = 1;i <= n;i++)
        {
            for (int j = 0;j < vn.size();j++)
            {
                for (int k = 1;k <= n;k++)
                {
                    int dx = mabs(vn[j].x - i);
                    int dy = mabs(vn[j].y - k);
                    love[j+1][k] = -(dx + dy);
                }
            }
            
            int tmp = -km(n);
            
            //printf("%d **
",tmp);
            
            ans = min(tmp,ans);
        }
        
        for (int i = 1;i <= n;i++)
        {
            for (int j = 0;j < vn.size();j++)
            {
                for (int k = 1;k <= n;k++)
                {
                    int dy = mabs(vn[j].y - i);
                    int dx = mabs(vn[j].x - k);
                    love[j+1][k] = -(dx + dy);
                }
            }
            
            int tmp = -km(n);
            
            ans = min(tmp,ans);
            
            //printf("%d **
",tmp);
        }
        
        for (int i = 1;i <= n;i++)
        {
            for (int j = 0;j < vn.size();j++)
            {
                int dx = mabs(vn[j].x - i);
                int dy = mabs(vn[j].y - i);
                
                love[j+1][i] = -(dx + dy);
            }
        }
        
        ans = min(ans,-km(n));
        
        for (int i = 1;i <= n;i++)
        {
            for (int j = 0;j < vn.size();j++)
            {
                int dx = mabs(vn[j].x - i);
                int dy = mabs(vn[j].y - (n - i + 1));
                
                love[j+1][i] = -(dx + dy);
            }
        }
        
        ans = min(ans,-km(n));
        
        printf("Board %d: %d moves required.

",++kase,ans);
    }
    
    return 0;
}