最大流应用(最小点集覆盖) poj3041Asteroids-jiangwen127-ChinaUnix博客

Asteroids

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 4525		Accepted: 2350

Description

Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <= N <= 500). The grid contains K asteroids (1 <= K <= 10,000), which are conveniently located at the lattice points of the grid.

Fortunately, Bessie has a powerful weapon that can vaporize all the asteroids in any given row or column of the grid with a single shot.This weapon is quite expensive, so she wishes to use it sparingly.Given the location of all the asteroids in the field, find the minimum number of shots Bessie needs to fire to eliminate all of the asteroids.

Input

* Line 1: Two integers N and K, separated by a single space.
* Lines 2..K+1: Each line contains two space-separated integers R and C (1 <= R, C <= N) denoting the row and column coordinates of an asteroid, respectively.

Output

* Line 1: The integer representing the minimum number of times Bessie must shoot.

Sample Input

Sample Output

Hint

INPUT DETAILS:
The following diagram represents the data, where "X" is an asteroid and "." is empty space:
X.X .X. .X.

OUTPUT DETAILS:
Bessie may fire across row 1 to destroy the asteroids at (1,1) and (1,3), and then she may fire down column 2 to destroy the asteroids at (2,2) and (3,2).

题意可以概括为：
给一个map，上面的X代表需要覆盖的位置，每次只能覆盖一行或一列，问最少需要执行几次覆盖操作。

二分图之所以灵活，是因为有很多看似无关的问题都能转化到最大匹配的问题上来。

问题一：最小覆盖，寻找一个点集，使得图中每一条边至少有一个点在该点集中，且该点集所包含的点数最少。（最小覆盖的情况下，每边条有且仅有一个端点在该点集中）。

定理：二分图最小覆盖等于二分图的最大匹配。

证明：设最大匹配数为m。

1：至少要m个点

证：因为二分图的最大匹配数为m，而每条边的端点互不相同，故至少要有m个点，才可以覆盖到所有的边。

2：最多要m个点

证：若存在m+1个点，则必有一条边的两个端点在该点集中，删去其中一点仍可以保持每条边被覆盖到，以此类推，大于m个点的点集都不是最小覆盖。

综上：最小覆盖的点集所包含的点数等于m，即二分图的最小覆盖等于二分图的最大匹配。

经典问题：PKU3041 Asteroids，给定一个矩阵，矩阵上有若干个障碍物，你可以一次清除一行或者一列的障碍物，问最少的清除操作需要几步。

#include
#include
#include
using namespace std;

const int MAXN = 1000;
int uN, vN; // u,ｖ数目
bool g[MAXN][MAXN];// g[i][j] 表示 xi与yj相连
int xM[MAXN], yM[MAXN];// 输出量
bool chk[MAXN];// 辅助量检查某轮 y[v]是否被check

bool SearchPath(int u)
{
    int v;
    for (v = 0 ; v < vN; v++)
    {
        if (g[u][v] && !chk[v])
        {
            chk[v] = true ;
            if (yM[v] == -1 || SearchPath(yM[v])) /*递归搜索*/
            {

/*这一部分在递归返回的时候会取反，即匈牙利算法中最重要的一步*/

                yM[v] = u;
                xM[u] = v;
                return true ;
            }
        }
    }
    return false ;
}

int MaxMatch()
{
    int u;
    int ret = 0 ;
    memset(xM, -1, sizeof (xM));
    memset(yM, -1, sizeof (yM));
    for (u = 0 ; u < uN; u++)
    {
//        if (xM[u] == -1) /*是否需要做这个判断还有待考虑*/
//       {
            memset(chk, false, sizeof(chk));
            if (SearchPath(u)) ret++;
//        }
    }
    return ret;
}

int main(int argc, char *argv[])
{
    int N, K, i, M, tU, tV;
    cin >> N >> K;

    uN = vN = N;
    memset(g, false, sizeof (g));
    for (i=0 ; i    {
        cin >> tU >> tV;
        g[tU - 1][tV - 1] = true ;
    }
    M = MaxMatch();
    cout << M << endl;
}