TYVJP1035棋盘覆盖 棋盘覆盖问题

题目在tyvj
刚开始用网络流做这道题目,可是限于水平没写出来。后来看了二分图,觉得这次才真的解出来了。很基础的二分图最大匹配,我用匈牙利算法写的。
【附匈牙利算法程序】Constdx:array[1..4]of -1..1=(1,0,-1,0);dy:array[1..4]of -1..1=(0,1,0,-1);VARmap:array[1..10000,1..10]oflongint;//注意用临接表,邻接矩阵会爆内存v,link:array[1..10000]oflongint;//v记录临接表与节点相连的点数,link记录二分图匹配时的点can:array[1..10000]ofboolean;//记录是否可以放棋子cover:array[1..10000]ofboolean;//计算最大匹配时的访问标志i,m,n,j,maxp :longint;Procedure init;//读入数据,把二维的数据转化成一维的(这个思想是Kudo神牛传授的...)vari,x,y,j,k,tmp,tmpx:longint;beginfillchar(can,sizeof(can),true);fillchar(v,sizeof(v),0);//初始化readln(n,m);for i:=1 to m do begin readln(x,y); can[(x-1)*n+y]:=false; end;for i:=1 to n do for j:=1 to n do begin if can[(i-1)*n+j]then begin tmp:=(i-1)*n+j;//当前(i,j)在二分图的位置标号 for k:=1 to 4 do//讨论上下左右四个相邻格子,建立相应的联系 if(i+dx[k]>0)and(j+dy[k]>0)and(i+dx[k]<=n)and(j+dy[k]<=n)and(can[(i+dx[k]-1)*n+j+dy[k]])then begin tmpx:=(i+dx[k]-1)*n+j+dy[k];//相邻的点在二分图的位置标号 inc(v[tmp]);map[tmp,v[tmp]]:=tmpx;//建立二分图 inc(v[tmpx]);map[tmpx,v[tmpx]]:=tmp; end; end; end;end;Function find(i:longint):boolean;//最大匹配varq,k,m:longint;beginfind:=true;for k:=1 to v[i] do begin m:=map[i,k]; if not cover[m] then beginq:=link[m];link[m]:=i;cover[m]:=true; if (q=0)or find(q) thenexit; link[m]:=q; end; end;exit(false);end;Procedure main;vari,j:longint;beginfor i:=1 to n*n do begin fillchar(cover,sizeof(cover),0); find(i); end;maxp:=0;for i:=1 to n*n do iflink[i]<>0 theninc(maxp);//求最大匹配end;Begininit;main;writeln(maxp div 2);End.
#01:Accepted(59ms, 1164KB)
#02:Accepted(28ms, 1136KB)
#03:Accepted(0ms, 1128KB)
#04:Accepted(0ms, 1120KB)
#05:Accepted(4ms, 1120KB)
#06:Accepted(0ms, 1120KB)
#07:Accepted(75ms, 1196KB)
TYVJP1035[棋盘覆盖] 棋盘覆盖问题
#08:Accepted(90ms, 1188KB)
#09:Accepted(0ms, 1120KB)
#10:Accepted(0ms, 1120KB)

Accepted/ 100 /257ms / 1196KB

  

爱华网本文地址 » http://www.413yy.cn/a/25101015/251646.html

更多阅读

如何恢复u盘删除的文件 u盘文件删了怎么恢复

如何恢复u盘删除的文件——简介恢复删除文件,取决于几个条件。1使用合适的数据恢复软件。2待恢复的数据大小和类型。一般文本类数据易恢复,小数据文件易恢复,图像格式文件因数据覆盖问题难恢复,流媒体有部分可能恢复。3u盘数据没有被覆

去创造一种棋盘游戏连载四十六 六子棋棋盘

几乎每一个孩子都喜欢玩游戏——然而有什么能比自己设计的游戏更有意思呢?第一个步骤是要找到一个主题——你要设计一个太空飞船的游戏吗?它是否以一个卡通人物为蓝本呢?如果你的孩子还在苦苦地思索主题的话,你可以暗示他一些有用的

深圳地铁6号线11号线将覆盖宝安(图) 深圳联通光纤覆盖查询

2012年,全市首期开工的是7、9、11号线,6、8号线也将适时启动建设。在三期轨道建设中,宝安区将建设6、11号线和穗莞深城际线,全长61.5公里,设立站点17个,涵盖新宝安的六个街道,总投资大概300多亿元。■覆盖宝安6街道■区领导要求,要按照时间

word打字覆盖后面的字 lol打字后面的字就没了

?很多不太会用word打字的朋友们常常会遇到这样的情况,本来打字好好的,不知道碰到什么键子,再以后打字的过程中会把后面已经输入好的字覆盖掉,这时候需要仔细观察一下Word的输入状态,是改写还是正常输入。方法/步骤word版本,仔细查看底部输

声明:《TYVJP1035棋盘覆盖 棋盘覆盖问题》为网友握紧手里的梦想分享!如侵犯到您的合法权益请联系我们删除