codevs1002搭桥(建图+Prim)

/*
先来个灌水法 然后建图跑最小生成树
注意观察题目中的规则 a[1][i]!=a[1][j]&&abs(a[2][i]-a[2][j])<=1
建图的时候可以每一个建筑物都看成一个点 然后计算需要几个桥
同一个城市的不用桥
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int n,m,tot,g[][],a[][],minn[],f[],sum,bb;
char s[][];
int xx[]={,,,,,,-,-,-};//枚举8个方向
int yy[]={,,-,-,,,-,,};
void Dfs(int x,int y)
{
s[x][y]=tot+;
int i,j,ox,oy;
for(i=;i<=;i++)//枚举8个方向
{
ox=x+xx[i];oy=y+yy[i];
if(ox>&&ox<=n&&oy>&&oy<=m&&s[ox][oy]=='#')
Dfs(ox,oy);
}
}
int main()
{
cin>>n>>m;
int i,j,k,l;
for(i=;i<=n;i++)
for(j=;j<=m;j++)
cin>>s[i][j];
for(i=;i<=n;i++)
for(j=;j<=m;j++)
if(s[i][j]=='#')//统计城市个数
{
tot++;
Dfs(i,j);
}
cout<<tot<<endl;
memset(g,,sizeof(g));
tot=;//建筑物数量
for(i=;i<=n;i++)
{
for(j=;j<=m;j++)
if(s[i][j]!='.')//记录每个建筑物的信息
{
tot++;
a[][tot]=i;//横坐标
a[][tot]=j;//纵坐标
}
}
for(i=;i<=tot;i++)//建图(每个点都建 属于一个城市的不同桥)
for(j=i+;j<=tot;j++)
{
if(a[][i]!=a[][j]&&abs(a[][i]-a[][j])<=)//如果符合连桥的条件
{
g[i][j]=abs(a[][i]-a[][j])-;
g[j][i]=g[i][j];
}
else if(a[][i]!=a[][j]&&abs(a[][i]-a[][j])<=)
{
g[i][j]=abs(a[][i]-a[][j])-;
g[j][i]=g[i][j];
}
}
memset(minn,,sizeof(minn));
minn[]=;
for(i=;i<=tot;i++)//跑 Prim
{
k=;
for(j=;j<=tot;j++)
if(f[j]==&&minn[j]<minn[k])
k=j;
f[k]=;
for(j=;j<=tot;j++)
if(f[j]==&&minn[j]>g[k][j])
minn[j]=g[k][j];
}
for(i=;i<=tot;i++)
{
if(minn[i]!=&&minn[i]<)
{
bb++;//统计桥的个数
sum=sum+minn[i];//累加桥的长度
}
}
cout<<endl<<bb<<" "<<sum;
return ;
}
上一篇:算法:Astar寻路算法改进


下一篇:07-语言入门-07-A Famous Music Composer