hdu 1879 继续畅通工程

hdu1102 #include<iostream>#include<string>#define MAXINT 9999999using namespace std;int map[101][101],s[101],dis[101],n;int prim(){ int sum=0; memset(s,0,sizeof(s)); s[1]=1; for(int i=2;i<=n;i++) dis[i]=map[1][i]; dis[1]=0; for(int i=1;i<n;i++) { int min=MAXINT,k=1; for(int j=1;j<=n;j++) if(!s[j]&&dis[j]<min) k=j,min=dis[j]; sum+=min; s[k]=1; for(int j=1;j<=n;j++) { min=map[k][j]; if(min<dis[j]) dis[j]=min; } } return sum;}int main(){ int a,b;while(scanf("%d",&n)==1&&n) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&map[i][j]); int m; scanf("%d",&m);for(int i=0;i<m;i++) { scanf("%d %d",&a,&b); map[a][b]=0; map[b][a]=0; } cout<<prim()<<endl; } return 0;}

呵呵，差点就被坑了，路分为已修和未修，只要把已修的路的成本改为0，就变回原原本本的最小生成树了

附上hdu1102的代码，题意也是查不多的

#include<iostream> #include<string> #define MAXINT 9999999 using namespace std; int map[101][101],s[101],dis[101],n; int prim() { int sum=0; memset(s,0,sizeof(s)); s[1]=1; for(int i=2;i<=n;i++) dis[i]=map[1][i]; dis[1]=0; for(int i=1;i<n;i++) { int min=MAXINT,k=1; for(int j=1;j<=n;j++) if(!s[j]&&dis[j]<min) k=j,min=dis[j]; sum+=min; s[k]=1; for(int j=1;j<=n;j++) { min=map[k][j]; if(min<dis[j]) dis[j]=min; } } return sum; } int main() { int a,b,c,d; while(scanf("%d",&n)==1&&n) { int m=(n*(n-1))/2; for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) map[i][j]=MAXINT; for(int i=0;i<m;i++) { scanf("%d %d %d %d",&a,&b,&c,&d); if(d) c=0; if(map[a][b]>c) { map[a][b]=c; map[b][a]=c; } } cout<<prim()<<endl; } return 0; }

转载于:https://www.cnblogs.com/nanke/archive/2011/08/16/2140037.html

相关资源：数据结构—成绩单生成器