Land
of Farms
Time Limit:
2000/
1000 MS (Java/Others) Memory Limit:
65536/
65536 K (Java/Others)
Total Submission(s):
622 Accepted Submission(s):
201
Problem Description
Farmer John
and his brothers have found
a new land. They are so excited
and decide
to build
new farms
on the land. The land is a rectangle and consists of N×M grids. A farm consists of one or more connected grids. Two grids are adjacent if they share a common border, i.e. their Manhattan distance is exactly 1. In a farm, two grids are considered connected if there exist a series of adjacent grids, which also belong to that farm, between them.
Farmer John wants
to build
as many farms
as possible
on the new land. It is required that any two farms should not be adjacent. Otherwise, sheep from different farms would fight on the border. This should be an easy task until several ancient farms are discovered.
Each
of the ancient farms also consists
of one or more connected grids. Due
to the respect
to the ancient farmers, Farmer John
do not want
to divide any ancient farm. If
a grid
from an ancient farm is selected
in a new farm, other grids
from the ancient farm should also be selected
in the new farm. Note that
the ancient farms may be adjacent, because ancient sheep
do not fight
each other.
The problem is
a little complicated now. Can you help Farmer John
to find
a plan
with the maximum
number of farms?
Input
The
first line of input
contains a number T indicating
the number of test cases (T≤
200).
Each test
case starts
with a line containing
two integers N
and M, indicating
the size
of the land. Each
of the following N
lines contains M
characters, describing
the map
of the land (
1≤N,M≤
10). A grid
of an ancient farm is indicated
by a single digit (
0-
9). Grids
with the same digit belong
to the same ancient farm. Other grids are denoted
with a single
character “.”. It is guaranteed that all test cases are valid.
Output
For
each test
case, output
a single
line consisting
of “Case
Sample Input
3
3 4
.
.3.
023.
.211
2 3
...
...
4 4
1111
1..1
1991
1111
Sample Output
Case
Case
Case
Source
2015ACM/ICPC亚洲区合肥站-重现赛（感谢中科大）
模拟赛时做的 刚接触到这题 一面懵逼 猜到是最大独立集，但是不会构图 目测是最大团，但是没最大团板子 果然是菜….只能靠题解了
首先,不考虑ancient farms 对点(i,j),其上下左右的点(ni,nj),有(i+j)%2!=(ni+nj)%2 所以 可以将点按(i+j)的奇偶性分为2个集合 (i,j)对与其相邻的点建边 跑一遍二分匹配 图的最大独立集(二分图X,Y集合的点数之和-最大匹配)就是答案ans=nx+ny-maxMatch HK算法可以在
O(V1/2E)
内求出最大匹配
考虑上ancient farms 发现ancient farms最多只有10个 如果枚举任意一个ancient farms是否建为新农场 对建成新农场的ancient farms的点以及其附近的点全部删掉 对没建成新农场的ancient farms的点也删掉 于是问题转化为上面的最大独立集问题 需要
O(210V1/2E)
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<ctime>
#include <string.h>
#include<math.h>
#include<unordered_set>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int inf=
1e9+
7;
const int N =
250;
const int M = N*N*
5;
const int INF=inf;
const int NX=
130;
const int NY=
130;
struct Edge{
int to,next;
}edge[NX*NY];
int head[NX];
inline void addEdge(
int k,
int u,
int v){
edge[k].to=v;
edge[k].next=head[u];
head[u]=k;
}
int nx,ny;
int cx[NX],cy[NY];
int disX[NX],disY[NY];
int dis;
bool bmask[NY];
bool searchPath(){
queue<int>que;
dis=INF;
fill(disX,disX+nx+
1,-
1);
fill(disY,disY+ny+
1,-
1);
for(
int i=
1;i<=nx;++i){
if(cx[i]==-
1){
que.push(i);
disX[i]=
0;
}
}
while(!que.empty()){
int u=que.front();
que.pop();
if(disX[u]>dis){
break;
}
for(
int i=head[u];i!=-
1;i=edge[i].next){
int v=edge[i].to;
if(disY[v]==-
1){
disY[v]=disX[u]+
1;
if(cy[v]==-
1){
dis=disY[v];
}
else{
disX[cy[v]]=disY[v]+
1;
que.push(cy[v]);
}
}
}
}
return INF!=dis;
}
int findPath(
int u){
for(
int i=head[u];i!=-
1;i=edge[i].next){
int v=edge[i].to;
if(!bmask[v]&&disY[v]==disX[u]+
1){
bmask[v]=
1;
if(cy[v]!=-
1&&disY[v]==dis){
continue;
}
if(cy[v]==-
1||findPath(cy[v])){
cy[v]=u;
cx[u]=v;
return 1;
}
}
}
return 0;
}
int maxMatch(){
int res=
0;
fill(cx,cx+nx+
1,-
1);
fill(cy,cy+ny+
1,-
1);
while(searchPath()){
fill(bmask,bmask+ny+
1,
false);
for(
int i=
1;i<=nx;++i){
if(cx[i]==-
1){
res+=findPath(i);
}
}
}
return res;
}
int state[
12];
int sIdx[
12];
char mp[
12][
12];
bool use[
12][
12];
int dirX[
4]={
0,
0,-
1,
1};
int dirY[
4]={-
1,
1,
0,
0};
int initState(
int n,
int m){
state[
0]=
1;
fill(sIdx,sIdx+
12,-
1);
for(
int i=
1;i<=
9;++i){
state[i]=state[i-
1]<<
1;
}
int stateNum=
0;
for(
int i=
0;i<n;++i){
for(
int j=
0;j<m;++j){
if(mp[i][j]!=
'.'){
int num=mp[i][j]-
'0';
if(sIdx[num]==-
1){
sIdx[num]=stateNum++;
}
mp[i][j]=
'0'+sIdx[num];
}
}
}
return stateNum;
}
bool initUse(
int s,
int n,
int m){
for(
int i=
0;i<n;++i){
fill(use[i],use[i]+m,
true);
}
for(
int i=
0;i<n;++i){
for(
int j=
0;j<m;++j){
if(mp[i][j]!=
'.'){
use[i][j]=
false;
int num=mp[i][j]-
'0';
if(state[num]&s){
for(
int k=
0;k<
4;++k){
int ni=i+dirX[k];
int nj=j+dirY[k];
if(ni>=
0&&ni<n&&nj>=
0&&nj<m){
use[ni][nj]=
false;
if(mp[ni][nj]!=mp[i][j]){
int num1=mp[i][j]-
'0';
int num2=mp[ni][nj]-
'0';
if((num1!=num2)&&(state[num2]&s)){
return false;
}
}
}
}
}
}
}
}
return true;
}
int idx[
12][
12];
void getIdx(
int i,
int j,
int&x,
int&y){
if(idx[i][j]==-
1){
if((i+j)&
1){
nx++;
idx[i][j]=nx;
}
else{
ny++;
idx[i][j]=ny;
}
}
if((i+j)&
1){
x=idx[i][j];
}
else{
y=idx[i][j];
}
}
void buildG(
int n,
int m){
for(
int i=
0;i<n;++i){
fill(idx[i],idx[i]+m,-
1);
}
nx=ny=
0;
int edgeK=
0;
fill(head,head+n*m+
1,-
1);
for(
int i=
0;i<n;++i){
for(
int j=
0;j<m;++j){
if(!use[i][j]){
continue;
}
int x,y;
getIdx(i,j,x,y);
for(
int k=
0;k<
4;++k){
int ni=i+dirX[k];
int nj=j+dirY[k];
if(ni>=
0&&ni<n&&nj>=
0&&nj<m&&use[ni][nj]){
getIdx(ni,nj,x,y);
addEdge(edgeK++,x,y);
}
}
}
}
}
int divi(
int s){
int ans=
0;
while(s){
ans+=(s&
1);
s>>=
1;
}
return ans;
}
int slove(
int n,
int m){
int stateNum=initState(n,m);
int ans=
0;
for(
int s=
0,end=
1<<stateNum;s<end;++s){
if(initUse(s,n,m)){
buildG(n,m);
int match=maxMatch();
ans=max(ans,nx+ny-match+divi(s));
}
}
return ans;
}
int main()
{
int T;
scanf(
"%d",&T);
for(
int t=
1;t<=T;++t){
int n,m;
scanf(
"%d%d",&n,&m);
for(
int i=
0;i<n;++i){
scanf(
"%s",mp[i]);
}
printf(
"Case #%d: %d\n",t,slove(n,m));
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-23890.html
