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

最小生成树 （prim)

代码：

#include
     
       #include
      
        const int inf=1002; using namespace std; int a[101][101],dis[101],visit[101]; int prim(int N)//1为原点 {
   int i,sum,min,mark,j,k; for(i=2;i<=N;i++)       dis[i]=a[1][i];        dis[1]=0;        visit[1]=1;      sum=0; for(i=1;i
       
        dis[k])             {
                   mark=k;                 min=dis[k];              }         }             sum+=min;             visit[mark]=1;             dis[mark]=0; for(j=1;j<=N;j++)              {
   if(dis[j]>dis[mark]+a[mark][j]&&visit[j]==0)                  dis[j]=dis[mark]+a[mark][j];              }      } return sum; } int main() {
   int N,i,j,Q; while(scanf("%d",&N)!=EOF)     {
   for(i=1;i<=N;i++)         {
               a[i][i]=0;             visit[i]=0; for(j=1;j<=N;j++)               {
                    scanf("%d",&a[i][j]);               }         }          scanf("%d",&Q); while(Q--)          {
             scanf("%d%d",&i,&j);           a[i][j]=0;           a[j][i]=0;          } int sum=prim(N);         printf("%d\n", sum);     } return 0; }