hdu1281 棋盘游戏 二分图最大匹配

hdu1281 棋盘游戏 二分图最大匹配

大家好,又见面了,我是全栈君。

小希和Gardon在玩一个游戏:对一个N*M的棋盘,在格子里放尽量多的一些国际象棋里面的“车”,并且使得他们不能互相攻击,这当然很简单,但是Gardon限制了只有某些格子才可以放,小希还是很轻松的解决了这个问题(见下图)注意不能放车的地方不影响车的互相攻击。 
所以现在Gardon想让小希来解决一个更难的问题,在保证尽量多的“车”的前提下,棋盘里有些格子是可以避开的,也就是说,不在这些格子上放车,也可以保证尽量多的“车”被放下。但是某些格子若不放子,就无法保证放尽量多的“车”,这样的格子被称做重要点。Gardon想让小希算出有多少个这样的重要点,你能解决这个问题么?

 

先DFS求出点数,再用二分匹配求解

hdu1281 棋盘游戏 二分图最大匹配hdu1281 棋盘游戏 二分图最大匹配

 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 const int maxn=1e5+5;  5 const int maxm=1e5+5;  6 
 7 int head[maxn],point[maxm],nxt[maxm],size;  8 int match[maxn],vis[maxn];  9 int get[maxn]; 10 
11 void init(){ 12     memset(head,-1,sizeof(head)); 13     size=0; 14     memset(match,-1,sizeof(match)); 15     memset(get,-1,sizeof(get)); 16 } 17 
18 void add(int a,int b){ 19     point[size]=b; 20     nxt[size]=head[a]; 21     head[a]=size++; 22 } 23 
24 int del; 25 
26 int dfs(int s,bool F){ 27     for(int i=head[s];~i;i=nxt[i]){ 28         if(!F&&i==del)continue; 29         int j=point[i]; 30         if(!vis[j]){ 31             vis[j]=1; 32             if(match[j]==-1||dfs(match[j],F)){ 33                 if(F){ 34                     match[j]=s; 35                     get[s]=i; 36  } 37                 return 1; 38  } 39  } 40  } 41     return 0; 42 } 43 
44 
45 int main(){ 46     int T=0; 47     int n,m,k; 48     while(scanf("%d%d%d",&n,&m,&k)!=EOF){ 49         ++T; 50  init(); 51         while(k--){ 52             int a,b; 53             scanf("%d%d",&a,&b); 54             add(a,n+b); 55  } 56         int ans1=0; 57         for(int i=1;i<=n;++i){ 58             memset(vis,0,sizeof(vis)); 59             if(dfs(i,1))ans1++; 60  } 61         int ans=0; 62         for(int i=1;i<=n;++i){ 63             if(get[i]!=-1){ 64                 del=get[i]; 65                 match[point[del]]=-1; 66                 get[i]=-1; 67                 memset(vis,0,sizeof(vis)); 68                 if(!dfs(i,0))ans++; 69                 get[i]=del; 70                 match[point[del]]=i; 71  } 72  } 73         printf("Board %d have %d important blanks for %d chessmen.\n",T,ans,ans1); 74  } 75     return 0; 76 }

View Code

 

转载于:https://www.cnblogs.com/cenariusxz/p/6578414.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108612.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • c语言的stl库_c语言string库

    c语言的stl库_c语言string库今天推荐一个函数库glib注意不是glibc https://developer.gnome.org/glib/一直在抱怨,标准C中为什么没有类似于STL的标准容器,让全世界的程序员在数以万次的重复实现它们。不过,还算走运,有了glib,恶梦在此终结了。glib提供了动态数组、单/双向链表、哈希表、多叉树、平衡二叉树、字符串等常用容器,完全是面向对象设计的,实现得非常精致。

    2022年10月15日
  • DirBuster使用教程

    DirBuster使用教程工具是kali自带,多用于网站的后台扫描工具路径:/usr/share/dirbustercd/usr/share/dirbuster进入路径后ls查看,会看到目录下的jar文件:2.java-jarDirBuster-1.0-RC1.jar打开jar文件3.出现可视化窗口,配置很多,现在我们先填写空白的输入框部分,这里我们在第一个输入框填写扫描网站的url地址4….

    2022年10月26日
  • SQL 模糊查询LIKE concat用法[通俗易懂]

    SQL 模糊查询LIKE concat用法[通俗易懂]concat用来拼接查询的字符串,如下代码所示SELECT*FROMdeploymentWHEREnameLIKEconcat(concat(‘%’,#{queryMessage}),’%’) 

  • 如何卸载干净JAVA?「建议收藏」

    如何卸载干净JAVA?「建议收藏」有很多小伙伴下载了JAVA的JDK(java开发工具包)并安装成功运行后,发现自己下错了版本。凉了,半天白搞了。卸载之后又发现在再安装出现安装不了的问题。这往往是因为JAVA并没有卸载完全。今天我们就看看如何完全卸载JAVA。JAVA卸载有两种方式。手动和用JAVA卸载工具。第一种,手动。1.打开控制面板,找到卸载程序,在找到java的程序,并卸载。2.这样之后,java虽然看不见了。但是还没有卸载干净。打开命令行窗口,输入命令regited。打开注册表窗口,删除ja…

  • 查看Linux内核版本_查看ubuntu内核

    查看Linux内核版本_查看ubuntu内核一、查看Linux内核版本命令(两种方法):1、cat/proc/version[root@S-CentOShome]#cat/proc/versionLinuxversion2.6.32-431.el6.x86_64(mockbuild@c6b8.bsys.dev.centos.org)(gccversion4.4.720120313(RedHat4.4.7-4)(GCC))#1SMPFriNov2203:15:09UTC20132、u

    2022年10月13日
  • 使用Jquery+EasyUI进行框架项目开发案例解说之中的一个—员工管理源代码分享

    使用Jquery+EasyUI进行框架项目开发案例解说之中的一个—员工管理源代码分享

    2021年11月13日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号