Cogs 746. [网络流24题] 骑士共存(最大独立集)
2024-09-05 07:03:49
- [网络流24题] 骑士共存
★★☆ 输入文件:knight.in 输出文件:knight.out 简单对比
时间限制:1 s 内存限制:128 MB
骑士共存问题
«问题描述:
在一个n*n个方格的国际象棋棋盘上,马(骑士)可以攻击的棋盘方格如图所示。棋盘
上某些方格设置了障碍,骑士不得进入。
«编程任务:
对于给定的n*n个方格的国际象棋棋盘和障碍标志,计算棋盘上最多可以放置多少个骑
士,使得它们彼此互不攻击。
«数据输入:
由文件knight.in给出输入数据。第一行有2 个正整数n 和m (1<=n<=200, 0<=m<=n*n)
分别表示棋盘的大小和障碍数。接下来的m 行给出障碍的位置。每行2 个正整数,表示障
碍的方格坐标。
«结果输出:
将计算出的共存骑士数输出到文件knight.out。
输入文件示例 输出文件示例
knight.in
3 2
1 1
3 3
knight.out
5
/*
最大独立集问题.
跑二分图匹配.
建图比较鬼畜.
注意边的编号问题.
ans=V-最大匹配数.
dinic即可.
(证明自行百度)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define MAXN 210
using namespace std;
int dis[MAXN*MAXN+10],n,cut=1,ans,tot,m,max1=1e9,head[MAXN*MAXN+10];
struct data{int v,next,c;}e[MAXN*MAXN*10];
bool b[MAXN][MAXN];
void add(int u,int v,int c)
{
e[++cut].v=v;
e[cut].c=c;
e[cut].next=head[u];
head[u]=cut;
}
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
bool bfs()
{
memset(dis,-1,sizeof dis);
queue<int>q;
q.push(0);
dis[0]=0;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]==-1&&e[i].c)
{
dis[v]=dis[u]+1;
q.push(v);
}
}
}
return dis[n*n+1]!=-1;
}
int dfs(int u,int y)
{
if(u==n*n+1) return y;
int rest=0;
for(int i=head[u];i&&rest<y;i=e[i].next)
{
int v=e[i].v;
if(dis[v]==dis[u]+1&&e[i].c)
{
int x=dfs(v,min(e[i].c,y-rest));
rest+=x;
e[i].c-=x;
e[i^1].c+=x;
}
}
if(!rest) dis[u]=-1;
return rest;
}
void dinic(int s,int t)
{
while(bfs()) ans+=dfs(s,max1);
printf("%d",n*n-m-ans);
return ;
}
void slove()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(b[i][j])continue;
if(i+j&1) add((i-1)*n+j,n*n+1,1),add(n*n+1,(i-1)*n+j,0);
else add(0,(i-1)*n+j,1),add((i-1)*n+j,0,1);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i+j&1&&b[i][j]) continue;
if(i+1<=n&&j+2<=n&&!b[i+1][j+2])
add((i-1)*n+j,i*n+j+2,1),add(i*n+j+2,(i-1)*n+j,0);
if(i+2<=n&&j+1<=n&&!b[i+2][j+1])
add((i-1)*n+j,(i+1)*n+j+1,1),add((i+1)*n+j+1,(i-1)*n+j,0);
if(i>=2&&j>=3&&!b[i-1][j-2])
add((i-1)*n+j,(i-2)*n+j-2,1),add((i-2)*n+j-2,(i-1)*n+j,0);
if(i>=3&&j>=2&&!b[i-2][j-1])
add((i-1)*n+j,(i-3)*n+j-1,1),add((i-3)*n+j-1,(i-1)*n+j,0);
if(i>=3&&j+1<=n&&!b[i-2][j+1])
add((i-1)*n+j,(i-3)*n+j+1,1),add((i-3)*n+j+1,(i-1)*n+j,0);
if(i>=2&&j+2<=n&&!b[i-1][j+2])
add((i-1)*n+j,(i-2)*n+j+2,1),add((i-2)*n+j+2,(i-1)*n+j,0);
if(i+2<=n&&j>=2&&!b[i+2][j-1])
add((i-1)*n+j,(i+1)*n+j-1,1),add((i+1)*n+j-1,(i-1)*n+j,0);
if(i+1<=n&&j>=3&&!b[i+1][j-2])
add((i-1)*n+j,i*n+j-2,1),add(i*n+j-2,(i-1)*n+j,0);
}
}
int main()
{
freopen("knight.in","r",stdin);
freopen("knight.out","w",stdout);
int x,y;
n=read(),m=read();
for(int i=1;i<=m;i++) x=read(),y=read(),b[x][y]=true;
slove();
dinic(0,n*n+1);
return 0;
}
最新文章
- 支持同步滚动的RichTextbox控件
- 树莓派启用root账户
- 【JAVA】ConcurrentHashMap
- cvCreateImage函数说明(转载)
- 2016年11月22日 星期二 --出埃及记 Exodus 20:13
- ARM寻址方式
- [windows驱动]标准驱动例程
- 读jQuery官方文档:样式
- (导航控制器view)全屏幕滑动实现pop效果
- Python -- 文档测试
- JAVA开发环境搭建 - JDK安装及环境变量配置
- Tomcat源码调试环境搭建
- jquery $(document).ready() 与window.onload的区别(转)
- nginx漏洞分析与升级修复
- grovvy身份证(全)
- Exp3 免杀原理与实践 20164303 景圣
- mongo-2ds索引对超过半球范围的适用性测试
- day11(python)装饰器
- OA协同办公软件
- 2018 ACM 国际大学生程序设计竞赛上海大都会部分题解
热门文章
- gitlab安装指南(gitlab-ce-9.4.3-ce.0.el7.x86_64 centos7)
- k8s之helm入门
- Codeforces 1097F. Alex and a TV Show
- sqlce基本语法
- MongoDB查询操作 返回指定字段(C#官方驱动)
- Git详细操作
- eureka解析hostname为localhost问题 (转)
- 简要了解web安全之sql注入
- 【loj#2133 &;&; luoguP2178】[NOI2015]品酒大会
- IDEA设置CodeGlance颜色