[BZOJ3175]&&[Tjoi2013] 攻击装置

2014-11-27
竞赛题解 / 图论
BZOJTJOI二分图

描述 Description

给定一个 01 矩阵，其中你可以在 0 的位置放置攻击装置。每一个攻击装置（x,y）都可以按照 “日” 字攻击其周围的 8 个位置（x-1,y-2）,(x-2,y-1),(x+1,y-2),(x+2,y-1),(x-1,y+2),(x-2,y+1), (x+1,y+2),(x+2,y+1)

求在装置互不攻击的情况下，最多可以放置多少个装置。

输入格式 InputFormat

第一行一个整数 N，表示矩阵大小为 N*N。接下来 N 行每一行一个长度 N 的 01 串，表示矩阵。

输出格式 OutputFormat

一个整数，表示在装置互不攻击的情况下最多可以放置多少个装置。

样例输入 SampleInput

3
010
000
100
## 样例输出 SampleOutput 4

BZOJ 3175

构建二分图，找最大独立点集。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=205*205;
const int dx[9]={0,-1,-2,1,2,-1,-2,1,2};
const int dy[9]={0,-2,-1,-2,-1,2,1,2,1};
int i,j,t,n,m,l,r,k,z,y,x;
struct edge
{
    int to,nx,vl;
}e[maxn*9];
int head[maxn],match[maxn],id[205][205];
bool used[maxn];
int sum,cnt,mat;
char ch[maxn];
inline void ins(int u,int v)
{
    e[++cnt].to=v;e[cnt].nx=head[u];
    head[u]=cnt;
}
inline void jud(int s,int x,int y)
{
    if (x<=0 || y<=0 || x>n || y>n || id[x][y]==0) return ;
    ins(s,id[x][y]);
}
bool crosspath(int s)
{
    int i,j,t,u,v,w;
    for (i=head[s];i;i=e[i].nx)
    {
        v=e[i].to;
        if (!used[v])
        {
            used[v]=true;
            if (!match[v] || crosspath(match[v]))
            {
                match[v]=s;
                return true;
            }
        }
    }
    return false;
}
inline void hungary()
{
    int i,j,t;
    for (i=1;i<=sum;i++)
    {
        memset(used,false,sizeof(used));
        if (crosspath(i)) mat++;
    }
}
int main()
{
    sum=cnt=mat=0;
    memset(id,0,sizeof(id));
    memset(head,0,sizeof(head));
    memset(match,0,sizeof(match));
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%s",ch);
        for (j=1;j<=n;j++) if (ch[j-1]=='0')
        {
            id[i][j]=++sum;
        }
    }
    for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (id[i][j]) for (k=1;k<=8;k++) jud(id[i][j],i+dx[k],j+dy[k]);
    hungary();
    printf("%d\n",sum-mat/2);
    return 0;
}