题目链接:

https://www.luogu.org/problemnew/show/P4304

分析:

最大独立集

最大独立集=总点数-最大匹配数

独立集:点集,图中选一堆点,这堆点两两之间没有连边

最大独立集:尽可能多得选点,使得其满足独立集的性质

这是网络流二分图经典题目,值得练习

代码:

#include<cstdio>
#include<utility>
#include<vector>
using namespace std;
int x[9]={0,-1,-2,1,2,-1,-2,1,2};
int y[9]={0,-2,-1,-2,-1,2,1,2,1};
struct ben
{
int first,second;
};
vector<ben> v[205][205];
int a[205][205];
ben link[205][205];
int vis[205][205];
int t;
bool find(ben andd)
{
int x=andd.first;
int y=andd.second;
for(int i=0;i<v[x][y].size();i++)
{
int p=v[x][y][i].first;
int q=v[x][y][i].second;
if(vis[p][q]!=t)
{
vis[p][q]=t;
int ls=link[p][q].first;
int ls2=link[p][q].second;
if((ls==0&&ls2==0)||find(link[p][q]))
{
link[p][q].first=x;
link[p][q].second=y;
return 1;
}
}
}
return 0;
}
int main()
{
int n;
scanf("%d",&n);
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%1d",&a[i][j]);
if(a[i][j]==0)
ans++;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=8;k++)
{
int xx=i+x[k];
int yy=j+y[k];
if(xx<=0||xx>n||yy<=0||yy>n)
continue;
ben tmp;
tmp.first=xx;
tmp.second=yy;
if(a[xx][yy]==0)
{
v[i][j].push_back(tmp);
}
}
}
}
int cnt=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j]==1)
continue;
t++;
ben tmp;
tmp.first=i;
tmp.second=j;
if(find(tmp))
{
cnt++;
}
//else
//break;
}
}
printf("%d\n",ans-cnt/2);
return 0;
}

最新文章

  1. Chrome 控制台 console
  2. SQL注入测试平台 SQLol -3.INSERT注入测试
  3. 如何搭建配置php开发环境
  4. Linux - 进程调度算法
  5. Visual Studio 2012 和 SVN 结合实现版本控制 AnkhSvn
  6. PyCharm 2018.1破解过程
  7. NPOI生成不规则Excel表格(并以流的形式下载,不将文件保存在服务器上,直接在客户端导出excel)
  8. XSS攻击 CSRF攻击
  9. 使用PoolingHttpClientConnectionManager解决友盟(umeng)推送在多线程环境推送失败的问题
  10. BZOJ2406矩阵
  11. [Python设计模式] 第23章 烤串的哲学——命令模式
  12. UE4:四种加载资源的方式
  13. Processing-基础小坑-
  14. CBV源码解析
  15. SharePoint 解决管理员密码修改后各种问题的来袭
  16. Git - 信息查看
  17. 「BZOJ 3645」小朋友与二叉树
  18. C#提高-------------------Module的使用
  19. python 检索一个目录下所有的txt文件,并把文件改为.log
  20. 将远程UI分支克隆到本地UI分支

热门文章

  1. A Summaryof JDBC
  2. win32内存调用图
  3. x64系统的判断和x64下文件和注册表访问的重定向(举例了GetProcAddress后转成函数指针的用法)
  4. 拉格朗日乘子法 - KKT条件 - 对偶问题
  5. maven中引入oracle驱动报错Missing artifact com.oracle:ojdbc14:jar
  6. 妹子问我maven是啥?从相亲说起。。
  7. Codeforces Round #568 (Div. 2)B
  8. maven的私服私包镜像地址配置settings.xml
  9. NumPy基础操作
  10. PATA 1036. Boys vs Girls (25)