二分图 JT的难题

Posted by Cww97 on 2016-01-07

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/50474880
(problem.cpp/pas)
【问题描述】
亮姐很喜欢下棋,有一天,他看见了无所事事的JT
“哇,你今天竟然有空!”
“今天放假嘛”
“那过来陪我下棋”
JT“······”
亮姐的棋盘很奇葩,是一个N*N的正方形棋盘,上面有一些国际象棋中的马。棋盘的行用1开始的N 个自然数标记,列用’A’开始的N 个大写英文字母标记。若一个马放置在格子(x, y)。那么格子(x-2, y-1), (x-2, y+1), (x-1, y-2),(x-1, y+2), (x+1, y-2), (x+1, y+2), (x+2, y-1), (x+2, y+1)如果在棋盘内的话,就都处于这个马的攻击范围内。如果若干个马在棋盘上的一种放置方法能使得没有一个马处在其它马的攻击范围内,那么称为和谐的方案。现在上面已经有N个棋子。
亮姐:“JT,你说我最少要拿掉多少棋子让剩下的棋子和谐?”
JT:“我怎么知道?”
亮姐:“你不是学编程的吗?”
JT:“······”
唉,没办法,JT实在是弱爆了,现在只能向你求救,告诉他最少拿走的个数。

【输入格式】
第一行,两个正整数N,M,分别表示棋盘的大小,和马的数目。
以下M 行,每行描述一个马的坐标。

【输出格式】
输出一行,一个整数,表示至少拿走多少个马。

【样例输入】
6 9
A1
A5
B3
C5
C1
D2
D4
E6
F5
【样例输出】
3

【Hint】
30%的数据满足,1 <= N <= 4.
100%的数据满足,1 <= N <= 26.

匈牙利算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
program cx;
const dx:array[1..8]of longint=(2,2,1,1,-1,-1,-2,-2);
dy:array[1..8]of longint=(1,-1,2,-2,2,-2,1,-1);
var i,n,m,x,y,ans,j:longint;
bx,by,a:array[0..1000]of longint;
g,gg:array[-2..200,-2..200]of longint;
v:array[0..1000]of boolean;
ch:char;

//=================culex===================

function find(x:longint):boolean;
var i:longint;
begin
for i:=1 to m do
if (gg[x,i]=1)and not v[i] then
begin
v[i]:=true;
if (a[i]=0) or find(a[i]) then
begin
a[i]:=x;
exit(true);
end;
end;
exit(false);
end;

begin
assign(input, 'problem.in'); reset(input);
assign(output,'problem.out');rewrite(output);
readln(n,m);
for i:=1 to m do
begin
read(ch);
bx[i]:=ord(ch)-64;
readln(by[i]);
g[bx[i],by[i]]:=i;
end;

for i:=1 to m do
begin
x:=g[bx[i],by[i]];
for j:=1 to 8 do
begin
y:=g[bx[i]+dx[j],by[i]+dy[j]];
if y>0 then
begin
gg[x,y]:=1;
gg[y,x]:=1;
end;
end;
end;

for i:=1 to m do
begin
fillchar(v,sizeof(v),0);
if find(i) then inc(ans);
end;

writeln(ans>>1);
close(input);
close(output);
end.