HDOJ1045解题报告【二分图最大匹配】

题目地址：

　　http://acm.hdu.edu.cn/showproblem.php?pid=1045

题目概述：

　　在图上有一些障碍物，要求在图上放上尽可能多的点使得每一行每一列没有两个点直接相连。

大致思路：

　　类似八皇后问题，而且数据范围很小不清楚搜索加剪枝能不过，有兴趣可以试一下。

　　我的做法是用二分图，建图就在每个点的x坐标和y坐标之间连一条边，障碍物怎么处理呢？事实上在一行里只需要将一个障碍物的两边设成不同的行就好了，列也是同样的道理。

代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <vector>
  6 #include <ctime>
  7 #include <map>
  8 #include <stack>
  9 #include <queue>
 10 #include <cstring>
 11 #include <algorithm>
 12 using namespace std;
 13 
 14 #define sacnf scanf
 15 #define scnaf scanf
 16 #define maxn  10
 17 #define maxm 26
 18 #define inf 1061109567
 19 #define Eps 0.00001
 20 const double PI=acos(-1.0);
 21 #define mod 7
 22 #define MAXNUM 10000
 23 void Swap(int &a,int &b) {int t=a;a=b;b=t;}
 24 int Abs(int x) {return (x<0)?-x:x;}
 25 typedef long long ll;
 26 typedef unsigned int uint;
 27 
 28 char G[maxn][maxn];
 29 int rG[maxn][maxn][2];
 30 vector<int> tG[10*maxn];
 31 int l[10*maxn],vis[10*maxn];
 32 
 33 bool dfs(int u)
 34 {
 35     int len=tG[u].size();
 36     for(int i=0;i<len;i++)
 37     {
 38         int v=tG[u][i];
 39         if(!vis[v])
 40         {
 41             vis[v]=1;
 42             if(l[v]==-1||dfs(l[v]))
 43             {
 44                 l[v]=u;return true;
 45             }
 46         }
 47     }
 48     return false;
 49 }
 50 
 51 int hungary(int n)
 52 {
 53     int ans=0;
 54     memset(l,-1,sizeof(l));
 55     for(int i=1;i<=n;i++)
 56     {
 57         memset(vis,0,sizeof(vis));
 58         if(dfs(i)) ans++;
 59     }
 60     return ans;
 61 }
 62 
 63 int main()
 64 {
 65     //freopen("data.in","r",stdin);
 66     //freopen("data.out","w",stdout);
 67     //clock_t st=clock();
 68     int n;
 69     while(~scanf("%d",&n))
 70     {
 71         if(n==0) break;
 72         for(int i=1;i<=n;i++)
 73         {
 74             getchar();
 75             for(int j=1;j<=n;j++)
 76             {
 77                 scanf("%c",&G[i][j]);
 78             }
 79         }
 80         int x=1;bool flag=false,flag2=false;
 81         for(int i=1;i<=n;i++)
 82         {
 83             for(int j=1;j<=n;j++)
 84             {
 85                 if(G[i][j]=='X')
 86                 {
 87                     if(flag) x++;
 88                     flag=false;continue;
 89                 }
 90                 else {flag=true;flag2=true;}
 91                 rG[i][j][0]=x;
 92             }
 93             if(flag2) x++;flag=flag2=false;
 94         }
 95         int y=1;flag=false;flag2=false;
 96         for(int j=1;j<=n;j++)
 97         {
 98             for(int i=1;i<=n;i++)
 99             {
100                 if(G[i][j]=='X')
101                 {
102                     if(flag) y++;
103                     flag=false;continue;
104                 }
105                 else {flag=true;flag2=true;}
106                 rG[i][j][1]=y;
107             }
108             if(flag2) y++;flag=flag2=false;
109         }
110         int t=x+y;
111         for(int i=1;i<=t;i++) tG[i].clear();
112         for(int i=1;i<=n;i++)
113         {
114             for(int j=1;j<=n;j++)
115             {
116                 if(G[i][j]!='X')
117                 {
118                     int tx=rG[i][j][0],ty=rG[i][j][1];
119                     tG[tx].push_back(x+ty);
120                     tG[x+ty].push_back(tx);
121                 }
122             }
123         }
124         printf("%d
",hungary(x));
125     }
126     //clock_t ed=clock();
127     //printf("

Time Used : %.5lf Ms.
",(double)(ed-st)/CLOCKS_PER_SEC);
128     return 0;
129 }