BZOJ3175[Tjoi2013]攻击装置——二分图最大独立集
2024-10-14 04:08:12
题目描述
给定一个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)
求在装置互不攻击的情况下,最多可以放置多少个装置。
输入
第一行一个整数N,表示矩阵大小为N*N。接下来N行每一行一个长度N的01串,表示矩阵。
输出
一个整数,表示在装置互不攻击的情况下最多可以放置多少个装置。
样例输入
3
010
000
100
010
000
100
样例输出
4
提示
100%数据 N<=200
将矩阵黑白染色(就是相邻格子染不同颜色),可以发现每个攻击装置能攻击到的格子和它所在格子染色不同,将源点连向白色格子,黑色格子连向汇点,每个白点连向能攻击到的黑点,跑二分图最大匹配,然后用总格子数-最大匹配-矩阵中1的个数。这个为什么是对的?因为相连的点表示能互相攻击到,去掉二分图最大匹配的边之后剩下的点之间一定不相连就一定不会互相攻击到。同时给这个残留的二分图加上之前任何一个删除的点都会有匹配边,所以这样是最大的。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int next[1000001];
int to[1000001];
int val[1000001];
int head[1000001];
int tot=1;
int q[100001];
int n,k;
int S,T;
int ans=0;
int x,y;
int d[100001];
char s[1001][1001];
int c[1001][1001];
const int dx[]={-2,-1,1,2,2,1,-1,-2};
const int dy[]={1,2,2,1,-1,-2,-2,-1};
void add(int x,int y,int v)
{
tot++;
next[tot]=head[x];
head[x]=tot;
to[tot]=y;
val[tot]=v;
tot++;
next[tot]=head[y];
head[y]=tot;
to[tot]=x;
val[tot]=0;
}
bool bfs(int S,int T)
{
int r=0;
int l=0;
memset(q,0,sizeof(q));
memset(d,-1,sizeof(d));
q[r++]=S;
d[S]=0;
while(l<r)
{
int now=q[l];
for(int i=head[now];i;i=next[i])
{
if(d[to[i]]==-1&&val[i]!=0)
{
d[to[i]]=d[now]+1;
q[r++]=to[i];
}
}
l++;
}
if(d[T]==-1)
{
return false;
}
else
{
return true;
}
}
int dfs(int x,int flow)
{
if(x==T)
{
return flow;
}
int now_flow;
int used=0;
for(int i=head[x];i;i=next[i])
{
if(d[to[i]]==d[x]+1&&val[i]!=0)
{
now_flow=dfs(to[i],min(flow-used,val[i]));
val[i]-=now_flow;
val[i^1]+=now_flow;
used+=now_flow;
if(now_flow==flow)
{
return flow;
}
}
}
if(used==0)
{
d[x]=-1;
}
return used;
}
void dinic()
{
while(bfs(S,T)==true)
{
ans+=dfs(S,0x3f3f3f);
}
}
int main()
{
scanf("%d",&n);
S=n*n+1;
T=n*n+2;
for(int i=1;i<=n;i++)
{
scanf("%s",s[i]+1);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(s[i][j]=='0')
{
c[i][j]=(i-1)*n+j;
if((i+j)%2==0)
{
add(S,c[i][j],1);
}
else
{
add(c[i][j],T,1);
}
}
else
{
k++;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(s[i][j]!='1'&&(i+j)%2==0)
{
for(int m=0;m<=7;m++)
{
int fx=dx[m]+i;
int fy=dy[m]+j;
if(fx>0&&fx<=n&&fy>0&&fy<=n&&c[fx][fy]!=-1)
{
add(c[i][j],c[fx][fy],0x3f3f3f);
}
}
}
}
}
dinic();
printf("%d",n*n-k-ans);
}
最新文章
- Zend Framework 项目 index.php 的问题
- ES6 Features系列:Template Strings &; Tagged Template Strings
- MySQL Workbench gnome-keyring-daemon错误的解决
- BZOJ3807 : Neerc2011 Lanes
- C语言中关键字volatile的含义【转】
- 最短路径算法(Dijkstra算法、Floyd-Warshall算法)
- HDU 5949 Relative atomic mass 【模拟】 (2016ACM/ICPC亚洲区沈阳站)
- Java - 推断元音辅音
- web笔记
- Java Map对象的遍历
- idea git提交时候提示 --author &#39;java_suisui&#39; is not &#39;Name &#39; and matches no existing author
- Docker创建JIRA 7.2.4中文破解版
- Unicode与Ansi互转
- Python Solve UnicodeEncodeError &#39;gbk&#39; / &#39;ascii&#39; / &#39;utf8&#39; codec can&#39;t encode character &#39;\x??&#39; in position ? 解决有关Python编码的错误
- libgdx学习记录16——资源加载器AssetManager
- Springboot_StringRedisTemplate配置
- jsp登录页面,展示错误信息,刷新页面后错误依然存在解决方案
- Unit01: Spring简介 、 Spring容器 、 Spring IOC
- Shell中反引号和$()的区别
- canvas之arcTo