题目链接:hdu5556-Land of Farms
题意:
给定一个图,图上的数字表示ancient farms,' . '表示新农场,要求在这片土地上建立农场,农场之间不能有连接(Manhattan distance is exactly 1),问最多能修建多少个农场。
题解:
由题可知,只需要建图,然后求图的最大独立集,及求其补图的最大团。
参考代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m,id,ans;
int mp[15][15],dx[5],dy[5];
int cnt[105],used[105];
bool edge[105][105];
char farm[15][15];
//给原图染色
void col(int x,int y,char cc)
{
if(x<1||x>n||y<1||y>m||farm[x][y]!=cc||mp[x][y]!=-1)
return;
mp[x][y]=id;
for(int i=1; i<=4; i++)
col(x+dx[i],y+dy[i],cc);
}
void color()
{
id=0;
memset(mp,-1,sizeof(mp));
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(farm[i][j]=='.')
{
mp[i][j]=id;
id++;
}
else if(mp[i][j]==-1)
{
col(i,j,farm[i][j]);
id++;
}
}
}
}
//建新图
void newgraph(int x1,int y1,int x2,int y2)
{
if(x2<1||x2>n||y2<1||y2>m)
return;
int x=mp[x1][y1];
int y=mp[x2][y2];
if(x==y)
return;
edge[x][y]=edge[y][x]=1;
}
void buildgraph()
{
memset(edge,0,sizeof(edge));
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
for(int k=1; k<=4; k++)
newgraph(i,j,i+dx[k],j+dy[k]);
}
//跑补图的最大团
bool dfs(int u,int dep)
{
for(int i=u+1; i<id; i++)
{
if(cnt[i]+dep<=ans)
return 0;
if(edge[u][i])
{
int j=0;
for(j=0; j<dep; j++)
{
if(!edge[i][used[j]])
break;
}
if(j==dep)
{
used[dep]=i;
if(dfs(i,dep+1))
return 1;
}
}
}
if(dep>ans)
{
ans=dep;
return 1;
}
return 0;
}
void maxclique()
{
memset(used,0,sizeof(used));
memset(cnt,0,sizeof(cnt));
for(int i=id-1; i>=0; i--)
{
used[0]=i;
dfs(i,1);
cnt[i]=ans;
}
}
int main()
{
scanf("%d",&T);
dx[1]=1; dx[2]=-1; dx[3]=0; dx[4]=0;
dy[1]=0; dy[2]=0; dy[3]=-1; dy[4]=1;
int icase=0;
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
scanf("%s",farm[i]+1);
color();
buildgraph();
//构造补图
for(int i=0; i<id; i++)
for(int j=0; j<id; j++)
if(i==j)
edge[i][j]=0;
else
edge[i][j]^=1;
ans=0;
maxclique();
printf("Case #%d: %d\n",++icase,ans);
}
return 0;
}