求二分图的最小点覆盖集，并输出
对于每一个a[i][j]=1，我们从行i-->列j建立一条边
显然，这张图是一张二分图。左边的节点代表删除哪一行，右边的节点代表删除哪一列。中间的边代表所有a[i][j]为1的点。
现在，我们需要做的事情就是找出最少的点，使这些点覆盖住所有的边（即删去哪几行哪几列，没有士兵）
最少的点，使这些点覆盖住所有的边 这个东西是最小点覆盖集。
对于一张二分图来说，在数量上，最小点覆盖集=最大匹配
如果 最大匹配>坦克数量，那么输出无解
剩下的情况就是有解了，如何寻找解？这问题困扰了我很久......最后还是看了别人的博客。
此外，这题目点最多有2000个，为什么匈牙利算法可以AC......不是o(n^3)效率的吗......
详见北京大学神犇Matrix67的讲解http://blog.csdn.net/niushuai666/article/details/7036897
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std; const int MAXN = + ;
int nx, ny;
int g[MAXN][MAXN];
int cx[MAXN], cy[MAXN];
int mk[MAXN];
int ROW, COLUMN, N;
char s[MAXN][MAXN];
vector<int>Gl[MAXN];
vector<int>Gr[MAXN];
vector<int> ansr;
vector<int> ansc;
int flagl[MAXN], flagr[MAXN];
int flag[MAXN];
int mat[MAXN][MAXN]; int path(int u)
{
for (int v = ; v<ny; v++)
{
if (g[u][v] && !mk[v])
{
mk[v] = ;
if (cy[v] == - || path(cy[v]))
{
cx[u] = v;
cy[v] = u;
return ;
}
}
}
return ;
} int MaxMatch()
{
int res = ;
memset(cx, -, sizeof(cx));
memset(cy, -, sizeof(cy));
for (int i = ; i<nx; i++)
{
if (cx[i] == -)
{
memset(mk, , sizeof(mk));
res = res + path(i);
}
}
return res;
} void dfs(int now, int x)
{
if (x==)
{
flagl[now] = ;
for (int i = ; i<Gl[now].size(); i++)
if (flagr[Gl[now][i]] == && cx[now] == Gl[now][i])
dfs(Gl[now][i], ); }
else
{
flagr[now] = ;
for (int i = ; i<Gr[now].size(); i++)
if (flagl[Gr[now][i]] == && cy[now] != Gr[now][i])
dfs(Gr[now][i], );
}
} int main()
{
while (~scanf("%d%d%d", &ROW, &COLUMN, &N))
{
for (int i = ; i < ROW; i++) scanf("%s", s[i]);
memset(g, , sizeof g);
for (int i = ; i<=ROW; i++) Gl[i].clear();
for (int i = ; i<=COLUMN; i++) Gr[i].clear();
for (int i = ; i < ROW; i++)
for (int j = ; j < COLUMN; j++)
if (s[i][j] == '')
{
g[i][j] = ;
Gl[i].push_back(j);
Gr[j].push_back(i);
}
nx = ROW;
ny = COLUMN;
int ans = MaxMatch();
if (ans>N) printf("NOT ENOUGH TANK\n");
else
{
printf("%d\n", ans); memset(flagl, , sizeof flagl);
memset(flagr, , sizeof flagr);
memset(flag, , sizeof flag);
memset(mat, , sizeof mat);
ansr.clear();
ansc.clear(); for (int i = ; i<ROW; i++) if (cx[i] != -) flag[cx[i]] = ;
for (int j = ; j<COLUMN; j++) if (!flag[j]) dfs(j, ); for (int i = ; i<ROW; i++) if (flagl[i]) ansr.push_back(i);
for (int i = ; i<COLUMN; i++) if (!flagr[i]) ansc.push_back(i); printf("ROW:");
for (int i = ; i < ansr.size(); i++) printf(" %d", ansr[i]+);
printf("\n"); printf("COLUMN:");
for (int i = ; i < ansc.size(); i++) printf(" %d", ansc[i]+);
printf("\n"); }
}
return ;
}