1526: 拣金豆
Time Limit: 1 Sec Memory Limit: 256 MBSubmit: 20 Solved: 5
Description
最近小明非常喜欢玩捡金豆游戏。有一个n*m的方格棋盘，每一个格子中有一个金豆或者没有。如果两个相邻的格子都有一个金豆，则可以捡起金豆，这两个格子中就没有金豆了。如果两个格子的曼哈顿距离等于1，则表示两个格子相邻。游戏的目的尽可能捡最多的金豆。
Input
第一行输入是一个整数T，表示测试用例个数，每一个测试用例包含两个整数n,m (1 <= n,m <= 100)，表示棋盘大小。在接下来的n行，每一行m个整数（0或1）表示该格子中是否有金豆。
Output
最大可捡起的金豆数目。
Sample Input
23 40 1 0 10 1 1 01 1 1 12 21 00 1
Sample Output
60
HINT
Source
算法：二分图的最大匹配。
标程：dfs[不知道怎么搜索的]，还ＭＬＥ了
思路：由于点数比较多（最多可能有10000个点），一般的二分图匹配模板只能解决 500 以下的，
数据比较弱，所以用KB神的用 vector 实现邻接表的匈牙利算法（一般可以解决1500点）可以过。
| Accepted |
1692
|
28
|
C++/Edit | 2654 B | 2013-05-08 19:42:19 |
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
using namespace std;
const int maxn = 10010;
int linker[maxn];
bool used[maxn];
vector<int> map[maxn];
int uN;
bool find(int u)
{
for(int i = 0; i < map[u].size(); i++)
{
if(!used[map[u][i]])
{
used[map[u][i]] = true;
if(linker[map[u][i]] == -1 || find(linker[map[u][i]]))
{
linker[map[u][i]] = u;
return true;
}
}
}
return false;
}
int hungary()
{
int sum = 0;
memset(linker,-1,sizeof(linker));
for(int u = 0; u < uN; u++)
{
memset(used,false,sizeof(used));
if(find(u)) sum++;
}
return sum;
}
int g[110][110];
int hash[110][110];
int main()
{
int T;
int n,m;
int u,v;
scanf("%d", &T);
while(T--)
{
scanf("%d%d",&n,&m);
uN = 0;
for(int i = 0; i < maxn; i++)
map[i].clear();
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
scanf("%d", &g[i][j]);
if(g[i][j]) hash[i][j] = uN++;
}
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if(g[i][j])
{
u = hash[i][j];
if(i > 0 && g[i-1][j])
{
v = hash[i-1][j];
map[u].push_back(v);
map[v].push_back(u);
}
if(i < (n-1) && g[i+1][j])
{
v = hash[i+1][j];
map[u].push_back(v);
map[v].push_back(u);
}
if(j > 0 && g[i][j-1])
{
v = hash[i][j-1];
map[u].push_back(v);
map[v].push_back(u);
}
if(j < (m-1) && g[i][j+1])
{
v = hash[i][j+1];
map[u].push_back(v);
map[v].push_back(u);
}
}
}
}
printf("%d\n", hungary());
}
return 0;
}
标程的MLE代码
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 105
struct arc{
int j;
arc * next;
};
struct vex{
int i;
arc * first;
};
vex a[N*N];
int map[N][N];
int tu[10000][10000];
int cov[N*N];
int linker[N*N];
int n,m;
int hx[4]={0,-1,0,1};
int hy[4]={-1,0,1,0};
void dfs(int i,int j,int b)
{
int r;
arc* p;
if(b==0)
{
map[i][j]=2;
for(r=0;r<4;r++)
if(map[i+hx[r]][j+hy[r]]!=0)
{
p=(arc*)malloc(sizeof(arc));
p->j=(i+hx[r])*m+j+hy[r];
p->next=a[i*m+j].first;
a[i*m+j].first=p;
if(map[i+hx[r]][j+hy[r]]==1)
dfs(i+hx[r],j+hy[r],1);
}
}
else
{
map[i][j]=3;
for(r=0;r<4;r++)
if(map[i+hx[r]][j+hy[r]]==1)
dfs(i+hx[r],j+hy[r],0);
}
}
int dfs2(int k)
{
arc* p;
int q;
for(p=a[k].first;p!=NULL;p=p->next)
if(!cov[p->j])
{
q=linker[p->j];
linker[p->j]=k;
cov[p->j]=1;
if(q==-1||dfs2(q)) return 1;
linker[p->j]=q;
}
return 0;
}
int work()
{
int i,sum;
for(i=0;i<m*n;i++)
linker[i]=-1;
for(i=0;i<n*m;i++)
if(map[i/m][i%m]==2)
{
memset(cov,0,sizeof(cov));
dfs2(i);
}
sum=0;
for(i=0;i<n*m;i++)
if(linker[i]!=-1)
sum++;
return sum;
}
int main()
{
int T,i,j,r,k,p;
scanf("%d",&T);
for(r=0;r<T;r++)
{
scanf("%d %d",&n,&m);
for(i=0;i<m*n;i++)
a[i].first=NULL;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&map[i][j]);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if(map[i][j]==1)
dfs(i,j,0);
p=0;
k=work();
printf("%d\n",k*2);
}
return 1;
}