http://poj.org/problem?id=1789
很裸的一道最小生成树题目,就是建立map[][]后直接套模板。。。。
http://poj.org/problem?id=2485
求最小生成树中的最大权值。。。做这个题时犯了个很2的错误,贡献了好几次WA。。最后重敲了一遍A了。。不说那2的错误了。
http://poj.org/problem?id=1258
裸的最小生成树
http://poj.org/problem?id=3026
注意这里the group may split in two or more groups 应为他在最小生成树专题里,看看题目就可以理解转换成最小生成树求解。如果没有分类我想只有那些大牛们才能想到吧。。
中出所有的A,S点,然后bfs求出任意两点的距离,然后套最小生成树模板。。。才开始RE了一下。。。因为A点至多100个在加上A101我直接开成55了。。这道题目最坑爹的地方在DIscuss里面有。唉。。不说了。。。
View Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define maxn 55
#define inf 99999999
using namespace std;
struct node
{
int x,y;
int val;
};
int map[maxn][maxn],dis[120];
int c[120][120];
bool vt[120],flag[maxn][maxn];
int n,m,ans;
char str[maxn][maxn];
int knum;
int dir[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};
void bfs(int x,int y,int val)
{
node cur,nt;
queue<node>q;
while (!q.empty()) q.pop();
cur.x = x;cur.y = y;cur.val = val;
q.push(cur);
while (!q.empty())
{
// puts("@@@@");
cur = q.front(); q.pop();
for (int i = 0; i < 4; ++i)
{
int p1 = cur.x + dir[i][0];
int p2 = cur.y + dir[i][1];
if (!flag[p1][p2] && map[p1][p2] >= 0)//可以使空格 A, S
{
flag[p1][p2] = true;
nt.x = p1; nt.y = p2;
nt.val = cur.val + 1;
if (map[p1][p2] > 0)//保证必须是A S
{
int xx = map[p1][p2];
int yy = map[x][y];
c[xx][yy] = c[yy][xx] = nt.val;
}
q.push(nt);
}
}
}
}
void prim()
{
int i,j,k,min;
for (i = 1; i < knum; ++i)
{
dis[i] = c[1][i] ;
vt[i] = false;
}
vt[1] = true; ans = 0;
for (k = 2; k < knum; ++k)
{
j = 0; min= inf;
for (i = 2; i < knum; ++i)
{
if (!vt[i] && dis[i] < min)
{
j = i; min = dis[i];
}
}
vt[j] = true;
ans += min;
for (i = 2; i < knum; ++i)
{
if (!vt[i] && dis[i] > c[i][j])
dis[i] = c[i][j];
}
}
}
int main()
{
int i,j,t;
cin>>t;
char dd[100];
while (t--)
{
scanf("%d%d",&m,&n);
gets(dd);//最坑爹的地方。。。多个空格
for (i = 0; i < n; ++i)
gets(str[i]);
knum = 1;
for (i = 0; i < n; ++i)//转换成int型矩阵,然后编号
{
for (j = 0; j < m; ++j)
{
if (str[i][j] == '#')
map[i][j] = -1;
else if (str[i][j] == ' ')
map[i][j] = 0;
else if (str[i][j] == 'A' || str[i][j] == 'S')
{
map[i][j] = knum++;
}
}
}
//printf("%d\n",knum);
for(i = 0; i < knum; ++i)//初始化最小生成树的图
{
for (j = 0; j < knum; ++j)
{
if (i == j) c[i][j] = 0;
else c[i][j] = inf;
}
}
for (i = 0; i < n; ++i)//bfs寻找任意两点之间的距离
{
for (j = 0; j < m; ++j)
{
if (str[i][j] == 'A' || str[i][j] == 'S')
{
memset(flag,false,sizeof(flag));
flag[i][j] = true;
bfs(i,j,0);
}
}
}
prim();//求最小生成树
printf("%d\n",ans);
}
return 0;
}