【二分图匹配-最小边覆盖】mz语考试
Description
jswf夺冠后
cc: tql
gj: tggl
mz:tlrxml
frz: bksjs
wjjj: whnzmqa
......
js: ???
js: nmflb
————节选自某次mz语等级测试
mz语等级测试即将到来。然而mz语十分难,用词灵活多变,导致作弊人数众多。而防止考生作弊的一个有效的途径是让考生之间保持一定的距离。
某考场有R(行)*C(列)个座位,坐在(r, c)的考生可能会看到(r,c-1)、(r,c+1)、(r-1,c-1)、(r-1,c+1)(即左、右、左前、右前)4个位置的考生的答案。
为了防止这种情况发生,就要保证一个考生周围的这4个位置中无其他考生。
而由于这个考场年久失修,有一些座位已经损坏,是无法使用的。
现在,fls想知道,在保证无人能看到别人答案的前提下,这个考场最多能安排多少名考生?
Input
多组数据
第一行有一个整数T(T<=30),代表数据组数。
对每组数据,第一行有两个整数R、C(1 <= R, C <= 50),表示考场规模。
接下来R行,每行有一个长度为C的字符串,描述考场内每个位置。'.'表示该位置可用,'x'则表示已损坏。
Output
对每组数据,输出该考场内最多能安排的考生数。
Sample Input
1
2 3
...
.x.
Sample Output
4
相隔两列的人是看不见对方的。所以把有冲突的座位连边即为二分图。
任意两个冲突的位置只能有一个地方坐人,即任意点只能有一条边相连。边数就是能坐下的人。转化为了最小边覆盖问题。
答案就是 点数-最大匹配数
注意link vis这些变量名有可能会与STL冲突
#include<vector>
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int dx[]={-1, 0, 1,-1,0,1};
int dy[]={-1,-1,-1, 1,1,1};
char tsr[55][55];
vector<int> G[3025];
int id[55][55];
int visa[3025]={0};
int linka[3025]={0};
int r,c;
int lig(int
… Read the rest