22——1879,1875畅通工程

http://acm.hdu.edu.cn/showproblem.php?pid=1879

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define N 100+5
#define maxn 0x3f3f3f
int matrix[N][N],low[N],vis[N];
int n;
int prime()
{
memset(vis,0,sizeof(vis));
int pos=1,sum=0;
for(int i=1;i<=n;i++)
low[i]=(i==pos)?0:matrix[pos][i];
vis[1]=1;
for(int i=1;i<n;i++)
{
int temp=maxn;
for(int j=1;j<=n;j++)
{
if(!vis[j]&&low[j]<temp)
{
temp=low[j];
pos=j;
}
}
vis[pos]=1;
sum+=temp;
for(int j=1;j<=n;j++)
{
if(!vis[j]&&low[j]>matrix[pos][j])
low[j]=matrix[pos][j];
}
}
return sum;
}

int main()
{
int i,j,a,b,v,s;
while(scanf("%d",&n)&&n)
{
memset(matrix,maxn,sizeof(matrix));
for(i=1;i<=n*(n-1)/2;i++)
{
scanf("%d%d%d%d",&a,&b,&v,&s);
if(!s)
matrix[a][b]=matrix[b][a]=v; //这儿是处理的关键
else
matrix[a][b]=matrix[b][a]=0; //将已经联通的路径其权值设为0
}
printf("%d\n",prime());
}
return 0;
}


http://acm.hdu.edu.cn/showproblem.php?pid=1875

#include <iostream>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <cmath>
using namespace std;
#define N 105
#define maxn 9999999
double matrix[N][N],low[N];
int vis[N];
struct node
{
int x;
int y;
} position[N];
int n;
double prime() //prime算法求最小生成树
{
memset(vis,0,sizeof(vis));
int pos=1;
double sum=0;
for(int i=1;i<=n;i++)
if(i!=pos)
low[i]=matrix[pos][i];
low[1]=0;
vis[1]=1;
for(int i=1;i<n;i++)
{
double temp=maxn;
for(int j=1;j<=n;j++)
{
if(!vis[j]&&low[j]<temp)
{
temp=low[j];
pos=j;
}
}
//cout<<temp<<endl;
sum+=temp;
vis[pos]=1;
for(int j=1;j<=n;j++)
{
if(!vis[j]&&low[j]>matrix[pos][j])
low[j]=matrix[pos][j];
}
}
return sum;
}

double distance(int x1,int y1,int x2,int y2) //两点之间的距离
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

int main()
{
int t,i,j;
cin>>t;
while(t--)
{
cin>>n;
memset(matrix,maxn,sizeof(matrix));
for(i=1;i<=n;i++)
cin>>position[i].x>>position[i].y;
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
{
double dis=distance(position[i].x,position[i].y,position[j].x,position[j].y);
if(dis>=10&&dis<=1000) //这儿判断满足符合条件的权值,加入邻接矩阵
matrix[i][j]=matrix[j][i]=dis;
}
double s=prime();
if(s>=maxn)
cout<<"oh!"<<endl;
else
cout<<fixed<<setprecision(1)<<s*100.0<<endl;
}
return 0;
}



评论

© 现实给了梦想多少时间 | Powered by LOFTER