题目 http://acm.hdu.edu.cn/showproblem.php?pid=1102
刚开始做这个题目时,没看清题目意思 一直错误 纠结死了我 这个是一个简单的最小生成树问题哦
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int map[101][101],dis[101]; bool mark[101]; int n,q,a,b; void prime() { int min,sum,i,j,k; memset(dis,0,sizeof(dis)); memset(mark,false,sizeof(mark)); sum=0; for(i=1;i<=n;i++) dis[i]=map[1][i]; mark[1]=true; dis[1]=0; for(i=2;i<=n;i++) { min=999999; for(j=1;j<=n;j++) { if(!mark[j]&&dis[j]<min) ///找出最小距离哦 { min=dis[j]; k=j; } } sum+=min; mark[k]=true; for(j=1;j<=n;j++) ///更新距离 { if(!mark[j]&&dis[j]>map[k][j]) { dis[j]=map[k][j]; } } } cout<<sum<<endl; } int main() { int i,j; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&map[i][j]); } scanf("%d",&q); while(q--) { scanf("%d %d",&a,&b); map[a][b]=map[b][a]=0; } prime(); } return 0; }