HUST 1027 Enemy Target!

求二分图的最小点覆盖集，并输出

对于每一个a[i][j]=1，我们从行i-->列j建立一条边

显然，这张图是一张二分图。左边的节点代表删除哪一行，右边的节点代表删除哪一列。中间的边代表所有a[i][j]为1的点。

现在，我们需要做的事情就是找出最少的点，使这些点覆盖住所有的边（即删去哪几行哪几列，没有士兵）

最少的点，使这些点覆盖住所有的边   这个东西是最小点覆盖集。

对于一张二分图来说，在数量上，最小点覆盖集=最大匹配

如果 最大匹配>坦克数量，那么输出无解

剩下的情况就是有解了，如何寻找解？这问题困扰了我很久......最后还是看了别人的博客。

此外，这题目点最多有2000个，为什么匈牙利算法可以AC......不是o(n^3)效率的吗......

#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 ;

}