#include<iostream>
#include<stdlib.h>
using namespace std;
#define inf 1001
#define maxint 100
int c[maxint][maxint]={0};
int L[maxint*maxint/2][2]={0};

int Prim(int n)
 { 
	int lowcost[maxint];
    int closest[maxint];
    bool s[maxint];
	int i,j,k,min,sum=0;
    s[1] = true;
    for(i = 2;i<= n; i++)
	{
		lowcost[i] = c[1][i];
        closest[i] = 1;
        s[i]= false; 
	}

    for (i = 1; i< n; i++)
	{
		 min = inf;
         j = 1;
         for ( k = 2;k<= n; k++)
             if ((lowcost[k] < min)&&(!s[k]))
			 {
                min = lowcost[ k];
                j=k;
			 }
        sum+=min;
        s[j] = true;
        for(k= 2; k<= n; k++)
           if((c[j][k] < lowcost[k])&&(!s[k])) 
		   {
	     		lowcost[k] = c[j][k];
                closest[k] =j; 
		   }
	}
	return sum;
}
void convert(int q)
{
	int i;
	for(i=0;i<q;i++)
		c[L[i][0]][L[i][1]]=0;
}
int main()
{
	int N,Q;
    int i,j;
  
	cin>>N;
	if(N<3||N>100)exit(-1);
    for(i=1;i<=N;i++)
        for(j=1;j<=N;j++)
		   cin>>c[i][j];
	cin>>Q;
	if(Q>N*(N+1)/2||Q<0)exit(-1);
    for(i=0;i<Q;i++)
		cin>>L[i][0]>>L[i][1];
    convert(Q);
	int s=Prim(N);
	cout<<s;
	system("PAUSE");
	return 1;
}

• Re:数组开大点..... (1382) wsbear 2006-07-22 02:09:55
• Re:谁能给出测试数据，高手帮帮咱，看看下面程序 (1382) ecjtuhaoli 2006-08-17 16:04:56