题解 P4304 【[TJOI2013]攻击装置】

· · 题解

这道题要用到匈牙利算法，如果不会的话请去P3386学习一下

1.这题首先要想到染色，就是把矩阵像棋盘一样黑白染色。代码实现考虑行列和奇偶性（向上一格不同色，向上二个同色；斜上方，也就是横一竖一同色）。

判断黑白代码如下:

x+y&1//x是行，y是列

然后发现装置只能攻击不同色区域（这才是染色的目的：将矩阵转化为二分图）

2.建模转换

最后能放的装置数 = 初始没有放障碍的位置数 - 最后不能放装置的位置数

由于这是个二分图，所以显然有二分图最小顶点覆盖 = 二分图最大匹配。

转换为二分图最大匹配，匈牙利算法或网络流均可解决，这里介绍匈牙利算法。

3.算法过程

(1)读入的同时累加点的编号/计算无障碍点的个数/前向星连边

(2)判断行列和的奇偶性，如果为奇就跑一遍find函数。

(3)输出

4.算法细节

(1)读入矩阵用scanf，类型%1d就可以解决了。

(2)连边只需要向下边连，因为上面的已经读入了；还有连边时判一下边界。

5.代码(c++)

#include<cstdio>
#include<cstring>
using namespace std;
struct edge{int to,next;}e[400010];
bool book[40050],map[205][205];
int cnt,num[205][205],head[40050],match[40050];
int dir1[4]={1,2,2,1},dir2[4]={2,1,-1,-2};
void add(int x,int y)
{
    e[++cnt].next=head[x];
    e[cnt].to=y;
    head[x]=cnt;
}
bool dfs(int x)
{
    int y,i;
    for(i=head[x];i;i=e[i].next)
    {
        y=e[i].to;
        if(book[y])continue;
        book[y]=1;
        if(!match[y]||dfs(match[y]))
        {
            match[y]=x;
            return 1;
        }
    }
    return 0;
}
int main()
{
    int n,sum=0,ans=0,tot=0,i,j,k;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
    for(j=1;j<=n;++j)
    {
        scanf("%1d",&map[i][j]);
        num[i][j]=++tot;sum+=(!map[i][j]);
        if(!map[i][j])
        for(k=0;k<4;++k)
        if((i>dir1[k])&&(j>dir2[k])&&(j-dir2[k]<=n)&&(!map[i-dir1[k]][j-dir2[k]]))
        {
            add(num[i][j],num[i-dir1[k]][j-dir2[k]]);
            add(num[i-dir1[k]][j-dir2[k]],num[i][j]);
        }
    }
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    if((i+j&1)&&!map[i][j])
    {
        memset(book,0,sizeof(book));
        ans+=dfs(num[i][j]);
    }
    printf("%d",sum-ans);
    return 0;
}