http://www.lydsy.com/JudgeOnline/problem.php?id=4808
题意:
思路:
这图中的两个马只能选一个,二选一,很像二分图吧,对能互吃的两个棋子连线,在所选的任意两个棋子中,都不能互相有连线,这不就是最大点独立集吗?
最大独立集 = 顶点个数 - 最大匹配。记得把坏了的格子去掉。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; int n,m,tot;
int mp[][], head[], mark[];
bool vis[]; struct node
{
int v,next;
}e[*]; int dx[] = {-,-,-,-,,,,};
int dy[] = {,-,,-,,-,,-}; void addEdge(int u, int v)
{
e[tot].v = v;
e[tot].next = head[u];
head[u] = tot++;
} bool match(int u)
{
for(int i=head[u];i!=-;i=e[i].next)
{
int v = e[i].v;
if(!vis[v])
{
vis[v] = true;
if(mark[v]==- || match(mark[v]))
{
mark[v] = u;
return true;
}
}
}
return false;
} int main()
{
//freopen("in.txt","r",stdin);
int num = ;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&mp[i][j]);
if(mp[i][j]) num++;
}
tot = ;
memset(head,-,sizeof(head));
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
if(!mp[i][j])
{
for(int k=;k<;k++)
{
int x = i+dx[k];
int y = j+dy[k];
if(x< || x>n || y< || y>m) continue;
if(mp[x][y]==) continue;
int p1 = (i-)*m+j;
int p2 = (x-)*m+y;
addEdge(p1,p2);
}
}
}
int sum = ;
memset(mark,-,sizeof(mark));
for(int i=;i<=n*m;i++)
{
memset(vis,false,sizeof(vis));
if(match(i)) sum++;
}
printf("%d\n",n*m-num-sum/);
return ;
}