poj-1251 - c++编程基础 - 编程开发网

可怜啊,自己好不容易找了个prim的模板,然后花费不菲的时间使用printf(),scanf()来处理这么复杂的数字,字母的问题居然调试通过了,虽然在最后提交时报告了超时,参考了一下网上的代码,无非就是使用了很多的输入输出语句,这可能导致了大量的用时,算法代码是一致的.先上正确的

#include
  
   
#include
   
     #include
    
      using namespace std; #define INF 10000 #define MAX 50 #define MAXN 100 int n,m,v,sum; int edge[MAX][MAX]; int lowcost[MAX]; int nextvex[MAX]; int prim(int u0,int n) { int i,j; int sum=0; for(i=1;i<=n;i++)//初始化lowcost[i],nextvex[i] { lowcost[i]=edge[u0][i]; nextvex[i]=u0; } nextvex[u0]=-1; for(i=1;i
     
      >n&&n){ memset(edge,0,sizeof(edge)); for(i=n;i>1;i--) { char a,e; int k; cin>>a>>k; for(j=1;j<=k;j++) { int cost; cin>>e>>cost; edge[a-64][e-64]=edge[e-64][a-64]=cost; } } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(i==j) edge[i][j]=0; else if(edge[i][j]==0) edge[i][j]=INF; } } printf("%d\n",prim(1,n)); } return 0; }

下面是我自己写的代码

#include
  
   
#include
   
     #include
    
      using namespace std; #define INF 10000 #define MAX 50 #define MAXN 100 int n,m,v,sum; int edge[MAX][MAX]; int lowcost[MAX]; int nextvex[MAX]; int prim(int u0,int n) { int i,j; int sum=0; for(i=1;i<=n;i++)//初始化lowcost[i],nextvex[i] { lowcost[i]=edge[u0][i]; nextvex[i]=u0; } nextvex[u0]=-1; for(i=1;i
     
      1;i--) { scanf("%c",&a);//城市A scanf("%c",&w);//消除换行符 scanf("%d",&k);//与其他城市连接的道路数目 for(j=1;j<=k;j++) { scanf("%c",&w);//消除影响 scanf("%c",&e);//后一个城市 scanf("%d",&cost);//权值 edge[a-64][e-64]=edge[e-64][a-64]=cost; } scanf("%c",&w);//消除影响 } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(i==j) edge[i][j]=0; else if(edge[i][j]==0) edge[i][j]=INF; } } printf("%d\n",prim(1,n)); } return 0; }

二者区别仅在于输入输出的不同,教训:不管什么样的题,先做正确再说别的!