二分图最大匹配

匈牙利算法，通过反复寻找增广路的方法求最大匹配。

const int MAXV = 1001;
int V;                //顶点数
vector<int> G[MAXV];  //图的邻接表表示
int match[MAXV];      //所匹配的定点
bool used[MAXV];      // DFS中用到的访问标记

//添加无向边，注意顶点编号从0开始
void add_edge(int u, int v) {
    G[u].push_back(v);
    G[v].push_back(u);
}

//通过DFS寻找增广路
bool dfs(int v) {
    used[v] = true;
    for (int i = 0; i < G[v].size(); i++) {
        int u = G[v][i], w = match[u];
        if (w < 0 || !used[w] && dfs(w)) {
            match[v] = u;
            match[u] = v;
            return true;
        }
    }
    return false;
}

//二分图最大匹配，返回最大匹配数
int Bipartite_Matching() {
    int res = 0;
    memset(match, -1, sizeof(match));
    for (int v = 0; v < V; v++) {
        if (match[v] < 0) {
            memset(used, 0, sizeof(used));
            if (dfs(v)) {
                res++;
            }
        }
    }
    return res;
}

---

POJ3041

题意：

 在一个N*N的网格上有K个小行星，小行星的位置是（$R_i$, $C_i$），有武器一次可以摧毁或一列的小行星，问最少几次使用武器可以将小行星全部摧毁。

解法：

把光束（横、纵两种）当作顶点，把小行星的位置当作边。问题就是选若干个点（光束）覆盖所有的边，这是最小顶点覆盖（任意边都有只少一个顶点被涵盖），等效于最大匹配。

横纵两种光束是二分图，所以直接二分最大匹配即可。

代码如下：

const int MAXV = 1001;
int V;                //顶点数
vector<int> G[MAXV];  //图的邻接表表示
int match[MAXV];      //所匹配的定点
bool used[MAXV];      // DFS中用到的访问标记

//添加无向边，注意顶点编号从0开始
void add_edge(int u, int v) {
    G[u].push_back(v);
    G[v].push_back(u);
}

//通过DFS寻找增广路
bool dfs(int v) {
    used[v] = true;
    for (int i = 0; i < G[v].size(); i++) {
        int u = G[v][i], w = match[u];
        if (w < 0 || !used[w] && dfs(w)) {
            match[v] = u;
            match[u] = v;
            return true;
        }
    }
    return false;
}

//二分图最大匹配，返回最大匹配数
int Bipartite_Matching() {
    int res = 0;
    memset(match, -1, sizeof(match));
    for (int v = 0; v < V; v++) {
        if (match[v] < 0) {
            memset(used, 0, sizeof(used));
            if (dfs(v)) {
                res++;
            }
        }
    }
    return res;
}

const int MAXK = 10000 + 5;
int N, K;
int R[MAXK], C[MAXK];

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif  // !ONLINE_JUDGE
    N = READ(), K = READ();
    REP(i, 1, K) {
        int R = READ(), C = READ();
        add_edge(R - 1, C + N - 1);
    }
    V = N + N;
    printf("%d
", Bipartite_Matching());
    return 0;
}