【二分图匹配-最小边覆盖】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