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.
",T,C,L);
94 }
95 return 0;
96 }