【HDOJ5556】Land of Farms（最大团）

题意：给定n*m的网格图，上面只有字符'.' 和数字0-9。其中数字表示这是该格是古老的土地，字符'.'表示该格只是普通的土地。

可以认为一块古老的农田由四联通的所有数字相同的格组成的块，一块普通的农田只由一格组成。

现在要建立最大数目的农田，要求任意两块农田不能相邻。问你能够建立的最大数目。

n,m<=10

思路：把四联通的同一个数字缩成一个，每个字符.当做单独的一个，按照相邻四联通情况建图

这样建出来的图不一定是二分图，变成了一个一般图最大独立集问题

考虑一般图最大独立集=建反图后最大团大小，使用爆搜版本的最大团求解，随机化的最大团正确性在此题范围下没有保证，甚至连样例有时都过不去……

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<string>
  4 #include<cmath>
  5 #include<iostream>
  6 #include<algorithm>
  7 #include<map>
  8 #include<queue>
  9 #include<vector>
 10 #include<ctime>
 11 using namespace std;
 12 typedef long long ll;
 13 typedef unsigned int uint;
 14 typedef unsigned long long ull;
 15 typedef pair<int,int> PII;
 16 typedef vector<int> VI;
 17 #define fi first
 18 #define se second 
 19 #define MP make_pair
 20 #define N  210000
 21 #define M  130
 22 #define MOD 1000000007
 23 #define eps 1e-8 
 24 #define pi acos(-1)
 25 
 26 const int dx[4]={-1,1,0,0};
 27 const int dy[4]={0,0,-1,1};
 28 
 29 
 30 char ch[M];
 31 int num[M][M],a[M][M],set[M][M],f[M][M],g[M],p[M],ans;
 32 
 33 
 34 int read()
 35 { 
 36    int v=0,f=1;
 37    char c=getchar();
 38    while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
 39    while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
 40    return v*f;
 41 }
 42 
 43 
 44 bool dfs(int size,int dep)
 45 {
 46     if(!size)
 47     {
 48         if(dep>ans)
 49         {
 50             ans=dep;
 51             return 1;
 52         }
 53          else return 0;
 54     }
 55     for(int i=1;i<=size;i++)
 56     {
 57         if(dep+size-i+1<=ans) return 0;
 58         int u=set[dep][i];
 59         if(dep+g[u]<=ans) return 0;
 60         int num=0;
 61         for(int j=i+1;j<=size;j++)
 62          if(f[u][set[dep][j]]) set[dep+1][++num]=set[dep][j];
 63         if(dfs(num,dep+1)) return 1;
 64     }
 65     return 0;
 66 }
 67             
 68     
 69 int main()
 70 {
 71     freopen("E.in","r",stdin);
 72     freopen("E.out","w",stdout);
 73     int cas,n,m,size,id;
 74     scanf("%d",&cas);
 75     for(int v=1;v<=cas;v++)
 76     {
 77         scanf("%d%d",&n,&m);
 78         for(int i=0;i<=9;i++) p[i]=0;
 79         id=0;        
 80         for(int i=1;i<=n;i++)
 81         {
 82             scanf("%s",ch+1);
 83             for(int j=1;j<=m;j++) 
 84             {
 85                 if('0'<=ch[j]&&ch[j]<='9') 
 86                 {
 87                     if(!p[ch[j]-'0']) p[ch[j]-'0']=++id;
 88                     num[i][j]=p[ch[j]-'0'];
 89                 }
 90                  else num[i][j]=++id;
 91             }
 92         }
 93         
 94         for(int i=1;i<=id;i++)
 95          for(int j=1;j<=id;j++) f[i][j]=i!=j;
 96         
 97         for(int i=1;i<=n;i++)
 98          for(int j=1;j<=m;j++)
 99          {
100              for(int k=0;k<=3;k++)
101              {
102                  int x=i+dx[k];
103                  int y=j+dy[k];
104                  if(x<1||x>n||y<1||y>m) continue;
105                  f[num[i][j]][num[x][y]]=0;
106                 f[num[x][y]][num[i][j]]=0;     
107              }
108          }
109         
110         
111         ans=0;
112         for(int i=id;i>0;i--)
113         {
114             size=0;
115             for(int j=i+1;j<=id;j++)
116              if(f[i][j]) set[1][++size]=j; 
117             dfs(size,1);
118             g[i]=ans;
119         }
120         printf("Case #%d: %d
",v,ans);
121     }
122     return 0;         
123 }