当前位置:首页 >> 学科竞赛 >>

Noip整理


无向图是二分图当且仅当图中没有奇数长度的回路 最大匹配=最小覆盖=N-最大独立集
有一个 N×N 的正方形棋盘。棋盘上被挖掉 P 个方格。现在用 2×1 的多米诺骨牌来覆盖剩下来的棋盘, 骨牌不能重叠。 问现在有没有可 能把剩下来的棋盘全部覆盖,如果有可能则输出一种方案。
1≤N≤40

样例输入
42 12 43

r />样例输出
6

原题出处:
190. Dominoes
time limit per test: 0.25 sec. memory limit per test: 4096 KB input: standard input output: standard output There is a NxN squared chessboard (1<=N<=40). P squares were removed from the chessboard (0<=P<N*N). It is necessary to find out whether it is possible to cover the remaining part of the chessboard with dominoes dice (each die is 2x1 squares sized). Each die should lie on two neighboring squares exactly. No two dice can cover one and the same square. Your task is to find the covering, if it exists.

Input The first line contains two integer numbers N and P separated by a space. Each of the

following P lines contains a pair of numbers separated by a space - coordinates of the removed square (1<=Xi, Yi<=N). The bottom left square has the coordinates (1, 1), the bottom right square - (N, 1).

Output If the covering exists, output "Yes" to the first line and "No" in the opposite case. If the first answer was positive, then output to the second line integer number Nh - the number of horizontally placed dice. Each of the following Nh lines should contain two integers - the coordinates of the left square covered by a corresponding die. Output to the next line Nv - the number of vertically placed dice. And the following Nv lines should contain the coordinates of the bottom square covered by a corresponding die.

Sample test(s)

Input 4 10 1 3 1 2 1 1 2 1 3 1 4 1 3 2 4 2 3 3 4 3 Output Yes 2 1 4 3 4 1 2 2 [submit] [forum]

Author: Resourc e: Date:

Michael R. Mirzayanov ACM International Collegiate Programming Contest

2003-2004 North-Eastern European Region, Southern Subregion 2003 October, 9

将图中(i+j)为奇数的点置为 0,将(i+j)为偶数的点置为 1,将不 可覆盖点置为 3 由于每一个多米诺骨牌都必须覆盖一黑点和一白点。 若黑点与白点相邻则连一条边。将则问题转化为求二分图最大匹配, 由匈牙利算法可得。

const dx:array[1..4] of longint=(1,-1,0,0); dy:array[1..4] of longint=(0,0,-1,1); var map:array[-10..40,-10..40] of longint; w:array[1..1600,1..1600] of longint; ans,n,p,temp1:longint; c:array[1..1600] of boolean;

b:array[1..1600] of longint; num:array[1..40,1..40] of longint; procedure init; var i,j,x,y,temp:longint; begin assign(input,'in.in'); reset(input); readln(n,p); temp:=1;ans:=0;temp1:=0; fillchar(map,sizeof(map),$7f); for i:=1 to n do begin for j:=1 to n do begin num[i][j]:=temp; temp:=temp+1; end; end; if n mod 2=0 then temp1:=n*n div 2 else temp1:=n*n div 2+1; for i:=1 to n do for j:=1 to n do begin if (i+j) mod 2=0 then map[i][j]:=1 else map[i][j]:=0; end; for i:=1 to p do begin readln(x,y); map[x][y]:=3; if num[x][y] mod 2=1 then dec(temp1); end; end; procedure solve; var i,j,x,y,k:longint; begin for i:=1 to n do for j:=1 to n do begin if map[i][j]<>3 then begin for k:=1 to 4 do begin x:=i;y:=j; x:=x+dx[k];y:=y+dy[k]; if (x<>0) and (y<>0) and (x<=n) and (y<=n) then if (map[i][j]<>map[x][y])and (w[num[i][j],num[x][y]]=0) then begin w[num[i][j],num[x][y]]:=1;w[num[x][y],num[i][j]]:=1;end; end; end; end; end; function path(x:longint):boolean; var i:longint; begin for i:=1 to (n*n-temp1-p) do if (w[x][i]=1) and (not c[i]) then begin c[i]:=true; if (b[i]=0) or path(b[i]) then

begin b[i]:=x; exit(true); end; end; exit(false); end; procedure hungray; var i:longint; begin fillchar(b,sizeof(b),0); for i:=1 to temp1 do begin fillchar(c,sizeof(c),0); if path(i) then inc(ans); end; end; begin init; solve; hungray; writeln(ans); end.
bool 寻找从 k 出发的对应项出的可增广路 { while (从邻接表中列举 k 能关联到顶点 j) { if (j 不在增广路上) { 把 j 加入增广路; if (j 是未盖点 或者 从 j 的对应项出发有可增广路) { 修改 j 的对应项为 k; 则从 k 的对应项出有可增广路,返回 true; } } } 则从 k 的对应项出没有可增广路,返回 false; } void 匈牙利 hungary() { for i->1 to n { if (则从 i 的对应项出有可增广路) 匹配数++; } 输出 匹配数; }

P1204CoVH 之柯南开锁
标签:图结构 二分图柯南之 Vijos 被黑事件

背景
随着时代的演进,困难的刑案也不断增加... 但真相只有一个 虽然变小了,头脑还是一样好,这就是名侦探柯南!

描述
[CoVH06] 面对 OIBH 组织的嚣张气焰, 柯南决定深入牛棚, 一探虚实. 他经过深思熟虑, 决定从 OIBH 组织大门进入...........

OIBH 组织的大门有一个很神奇的锁. 锁是由 M*N 个格子组成, 其中某些格子凸起(灰色的格子). 每一次操作可以把某一行或某 一列的格子给按下去.

如果柯南能在组织限定的次数内将所有格子都按下去, 那么他就能够进入总部. 但是 OIBH 组织不是吃素的, 他们的限定次数恰是最少次数.

请您帮助柯南计算出开给定的锁所需的最少次数.

格式
输入格式

第一行 两个不超过100的正整数 N, M 表示矩阵的长和宽 以下 N 行 每行 M 个数 非0即1 1为凸起方格

输出格式
一个整数 所需最少次数

样例
样例输入
4 4 0000 0101 0000 0100

样例输出
2

限制
全部1秒

提示 OIBH 组织的第一道防线居然被柯南突破了.
派出了黄金十二人+青铜五小强进行抵抗.

这引起了 OIBH 组织的高度重视, 他们

var w:array[1..200,1..200] of longint; pic:string; b:array[1..200] of longint; c:array[1..200] of boolean; n,m,k,ans:longint; procedure init; var i,j:longint; begin assign(input,'in.in'); reset(input); readln(n,m); for i:=1 to n do begin readln(pic); for j:=1 to m do begin if pic[j]='1' then begin w[i][j+n]:=1; w[j+n][i]:=1;

end; end; end; close(input); end; function path(x:longint):boolean; var i:longint; begin for i:=n+1 to n+m do if (w[x][i]=1) and (not c[i]) then begin c[i]:=true; if (b[i]=0) or path(b[i]) then begin b[i]:=x; exit(true); end; end; exit(false); end; procedure hungray; var i:longint;

begin fillchar(b,sizeof(b),0); for i:=1 to n do begin fillchar(c,sizeof(c),0); if path(i) then inc(ans); end; end; begin init; hungray; writeln(ans); End. 将列看成一部分,将行看成一部分: 如果在某一方格上有凸起方格则将所在列与所在行连一条边, 由于能 改变一行或一列,则求所得二分图的最小覆盖使得每点都能被改变。

样例中,建立如图所示,则选取第二行,第四行能全部改变;选取第 二列,第 4 列能全部改变


相关文章:
NOIp每日整理
["扫地"杯 III day1]诡异的数学题 From liouzhou_101 背景 Background “扫地”杯 III NOIP2012模拟赛 day1 第一题描述 Description liouzhou_101从 NOI 归来...
Noip整理
Noip整理_学科竞赛_高中教育_教育专区。团伙 背景 Background From BearHsu 经典题目描述 Description 1920年的芝加哥,出现了一群强盗。如果两个强盗遇上了,那么他 ...
Noip整理
或者如何实现呢?这正是 Kosaraju 算法最为精妙的地 方,关键在于第二次 DFS 选取的顺序:在第一次 DFS 中,将顶点按 照后序编号存放,第二次 DFS 就按照这个...
noip 每日整理
Noip整理 暂无评价 16页 1下载券 Noip整理 暂无评价 5页 2下载券 Noip整理 暂无评价 8页 2下载券 noip初赛基础知识整理(精... 8页 3下载券 基础代码汇总整...
NOIP算法整理_图文
NOIP算法整理_学科竞赛_高中教育_教育专区。2015NOIP算法总结PASCAL版 前言离 NOIP 还有一个星期,匆忙的把寒假整理的算法补充完善,看 着当时的整理觉得那时还年少。...
NOIP常用程序段整理
NOIP常用程序段整理 程序程序隐藏>> Noip2009 衢州一中 目录关于时间复杂度 快速排序 归并排序 筛选法求素数 floyed 迪杰斯特拉 prim 拓扑排序 深搜 广搜 最长子序...
NOIP2014 题解
NOIP2014 题解_IT/计算机_专业资料。NOIP2014 题解 D1T1 : 生活大爆炸版石头...(x+p)在展开后必然可以整理成 f(x)+T,其中 T 为关于 p 的一个多项式, ...
信息学奥赛(NOIP)必看经典书目汇总
信息学奥赛(NOIP)必看经典书目汇总_学科竞赛_高中教育_教育专区。信息学奥赛(NOIP)必看经典书目汇总! 小编整理汇总了一下大神们极力推荐的复习资料! (欢迎大家查漏...
冲刺NOIP之整理
NOIP范围内的DP算法 6页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 冲刺NOIP整理 冲刺NOIP2012知识点整理、冲...
noip的总结
noip 总结 1 算法总结动规难点:模型的建立和理解。 要求:对于每道题,都能在很短的时间里把思路完整地整理一遍,可以快速而无误的写 出程序。 (一) 两种动机 ...
更多相关标签:
noip吧 | noip动态域名注册 | noip2015 | noip2016 | noip2013 | noip2014 | noip2015提高组复赛 | noip2015普及组复赛 |