HDU1281 二分图最大边独立集 （匹配上的关键匹配）

 1 /*HDU1281
 2 题目大意:
 3 给出NxM的棋盘，其中有K个点不能放“车”
 4 定义：若某个点不能放"车"，则棋盘中放"车"的最大数目减少,该点就为重要点
 5 求重要点的个数和棋盘中放"车"的最大数目
 6 输出：Board T have C important blanks for L chessmen.
 7 思考：
 8 每一行，每一列分别抽象成一个点。
 9 可以放棋子的对应的行和列连边，这样就能求出最大独立点集，也就是L
10 现在问题是如何求关键点？
11 一、暴力一点的想，删除这个棋子对应的边的关系，看点集是否减少。
12 复杂度为：O((N+M)K*K)==10^10超时。
13 二、那么从二分图本身的特点出发呢？
14 假设在独立集中的点都被染成红色，则哪些点是必须被染成红色的呢？
下面是一篇更优化的题解：
15 http://blog.csdn.net/mishifangxiangdefeng/article/details/7109139 
16 但是这样枚举效率太低。实际上，删边只需考虑求出的匹配边（因为删除非匹配边得到的匹配数不变）。
17 这样，只需删除ans条边，复杂度就降低了。
18 
棋盘上的点==图上的边==求最大匹配数
19 */
20 #include <iostream>
21 #include <cmath>
22 #include <algorithm>
23 #include <string.h>
24 #include <stdio.h>
25 #include <set>
26 #include <stack>
27 #include <vector>
28 #define maxn 210
29 using namespace std;
30 vector<int> G[maxn];
31 bool visit[maxn];
32 bool NMvis[maxn];//计算总共点的个数
33 int match[3][maxn];
34 int N,M,K,L,C,A,B;
35 void read(){
36     for(int i=1;i<=N+M;i++){
37         G[i].clear();
38     }
39     memset(NMvis,0,sizeof(NMvis));
40     for(int i=1;i<=K;i++){
41         int a,b;
42         scanf("%d%d",&a,&b);
43         b=b+N;
44         NMvis[a]=NMvis[b]=true;
45 //        cout<<a<<","<<b<<endl;
46         G[a].push_back(b);
47         G[b].push_back(a);
48     }
49     return ;
50 }
51 bool dfs(int st,int A,int B,int k){
52     for(int i=0;i<G[st].size();i++){
53         int v=G[st][i];
54         if ((st==A && v==B) || (st==B && v==A)) continue;
55         if (!visit[v]){
56             visit[v]=true;
57             if (match[k][v]==-1 || dfs(match[k][v],A,B,k)){
58                 match[k][v]=st;
59                 return true;
60             }
61         }
62     }
63     return false;
64 }
65 int hungary(int A,int B,int k){
66     memset(match[k],-1,sizeof(match[k]));
67     int ans=0;
68     for(int i=1;i<=M+N;i++){
69         memset(visit,0,sizeof(visit));
70         if (NMvis[i] && dfs(i,A,B,k)) ans++;
71     }
72 //    cout<<"ans="<<ans/2<<endl;
73     return ans/2;//因为无向图的存储特点，所以正反两条边被记录了两次
74 }
75 int solveC(){//将匹配的边删去，测试是否最大匹配减小，最多测试100次
76     int ans=0;
77     for (int i=1;i<=N+M;i++){
78         if (match[1][i]!=-1)//枚举未匹配的边
79         {
80             if (hungary(i,match[1][i],2)<L) ans++;
81         }
82     }
83     return ans/2;
84 }
85 int T=0;
86 int main()
87 {
88     while(cin>>N>>M>>K){
89         T++;
90         read();
91         L=hungary(-1,-1,1);
92         C=solveC();
93         printf("Board %d have %d important blanks for %d chessmen.\n",T,C,L);
94     }
95     return 0;
96 }