HDU 5556 最大独立集

时间：2022-06-16 06:31:23

这题主要有了中间的一些连通块的限制，不太好直接用二分图最大独立集做。考虑到图比较小，可以作补图求最大团来求解。

 #include <iostream>

 #include <vector>

 #include <algorithm>

 #include <string>

 #include <string.h>

 #include <stdio.h>

 #include <queue>

 #include <stack>

 #include <map>

 #include <set>

 #include <cmath>

 #include <ctime>

 #include <cassert>

 #include <sstream>

 using namespace std;

 const int N=;

 char s[N][N];

 int id[N][N];

 int dx[]={,,,-};

 int dy[]={,-,,};

 int n,m;

 struct MC{

     bool graph[N][N];

     int stk[N][N],dp[N],mc;

     int choice[N],vertex[N];

     void dfs(int n,int sz,int dep){

         if (sz==){

             if (dep>mc){

                 mc=dep;

                 for (int i=;i<mc;i++)

                     vertex[i]=choice[i];

             }

             return;

         }

         for (int i=;i<sz;i++){

             int u=stk[dep][i];

             if (dep+dp[u]<=mc) return;

             if (dep+sz-i<=mc) return;

             choice[dep]=u;

             int cnt=;

             for (int j=i+;j<sz;j++){

                 int v=stk[dep][j];

                 if (graph[u][v])

                     stk[dep+][cnt++]=v;

             }

             dfs(n,cnt,dep+);

         }

     }

     int maxClique(int n){

         mc=;

         //节点从1开始标号

         dp[n]=;

         for (int i=n-;i>=;i--){

             int sz=;

             for (int j=i+;j<=n;j++)

                 if (graph[i][j])

                     stk[][sz++]=j;

             choice[]=i;

             dfs(n,sz,);

             dp[i]=mc;

         }

         return mc;

     }

     void solve(int &cas) {

         map<char,int> mp;

         int cnt=;

         for (int i=;i<=n;i++) {

             for (int j=;j<=m;j++) {

                 if (s[i][j]=='.')

                     id[i][j]=++cnt;

                 else if (mp.find(s[i][j])==mp.end())

                     id[i][j]=mp[s[i][j]]=++cnt;

                 else

                     id[i][j]=mp[s[i][j]];

             }

         }

         //for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) cout<<id[i][j]<<" ";cout<<endl;

         for (int i=;i<=cnt;i++) {

             for (int j=;j<=cnt;j++) {

                 if (i==j) graph[i][j]=false;

                 graph[i][j]=true;

             }

         }

         for (int i=;i<=n;i++) {

             for (int j=;j<=m;j++) {

                 int u=id[i][j];

                 for (int k=;k<;k++) {

                     int ni=i+dx[k];

                     int nj=j+dy[k];

                     if (ni<=||nj<=||ni>n||nj>m) continue;

                     int v=id[ni][nj];

                     graph[u][v]=false;

                     graph[v][u]=false;

                 }

             }

         }

         printf("Case #%d: %d\n",cas,maxClique(cnt));

     }

 }mc;

 int main () {

     //freopen("out.txt","r",stdin);

     int T;

     scanf("%d",&T);

     while (T--) {

         scanf("%d %d",&n,&m);

         for (int i=;i<=n;i++) {

             scanf("%s",s[i]+);

         }

         static int cas=;

         mc.solve(cas);

         cas++;

     }

     return ;

 }

相关文章