就是棋盘问题输出一组解
https://blog.csdn.net/llx523113241/article/details/47759745
http://www.matrix67.com/blog/archives/116
求最小覆盖的步骤大致如下：1）在右边找到一个未被匹配过的点，标记。2）走一条没被匹配过的边，到左边的点，标记。3）走一条匹配过的边到右边，标记。4）重复2,3步骤直到不能再走。5）回到步骤一，直到找不到未被匹配且未被标记的右边的点。6）标记结束后，右边没有标记的点，和左边标记过的点，就可以覆盖所有的边。
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = , INF = 0x7fffffff;
int line[maxn][maxn], girl[maxn], used[maxn], boy[maxn], cx[maxn], cy[maxn];
int n, m, c; bool find(int x)
{
for(int i=; i<=m; i++)
{
if(line[x][i] == true && used[i] == false)
{
used[i] = ;
if(girl[i] == || find(girl[i]))
{
girl[i] = x;
boy[x] = i;
return true;
}
}
}
return false;
} bool dfs(int y)
{
cy[y] = ;
for(int i=; i<=n; i++)
{
if(line[i][y] && !cx[i])
{
cx[i] = ;
if(boy[i] == || dfs(boy[i]))
return true;
}
}
return false;
} int main()
{
while(scanf("%d%d%d", &n, &m, &c) && n+m+c)
{
int res = ;
mem(line, );
mem(girl, );
mem(boy, );
mem(cx, );
mem(cy, );
mem(inx, );
mem(iny, );
rap(i, , c)
{
int a, b;
scanf("%d%d", &a, &b);
line[a][b] = ;
}
for(int i=; i<=n; i++)
{
mem(used, );
if(find(i))
res++;
}
for(int i=; i<=m; i++)
if(!girl[i]) dfs(i);
printf("%d", res);
rap(i, , n) if(cx[i]) printf(" r%d", i);
rap(i, , m) if(!cy[i]) printf(" c%d", i);
printf("\n"); } return ;
}