Agri-Net

http://poj.org/problem?id=1258

 1 #include<cstdio>

 2 #include<cstring>

 3 #include<algorithm>

 4 #define MAXN 110

 5 

 6 const int INF=1<<28;

 7 using namespace std;

 8 int g[MAXN][MAXN];

 9 int dis[MAXN];

10 bool vis[MAXN];

11 int n,sum;

12 bool sprim()

13 {

14     memset(vis,false,sizeof(vis));

15     for(int i=1;i<=n;i++)

16         dis[i]=INF;

17     dis[1]=0;sum=0;

18     for(int i=1;i<=n;i++)

19     {

20         int min=INF,k=0;

21         for(int j=1;j<=n;j++)

22         {

23             if(!vis[j]&&dis[j]<min)

24             {

25                 min=dis[j];

26                 k=j;

27             }

28         }

29         if(min==INF) return false;

30         vis[k]=true;

31         sum+=min;

32         for(int j=1;j<=n;j++)

33         {

34             if(!vis[j]&&dis[j]>g[k][j])

35             {

36                 dis[j]=g[k][j];

37             }

38         }

39     }

40     printf("%d
",sum);

41     return true;

42 }

43 int main()

44 {

45     while(scanf("%d",&n)!=EOF){

46 

47        for(int i=1;i<=n;i++)

48        {

49            for(int j=1;j<=n;j++)

50            {

51                scanf("%d",&g[i][j]);

52            }

53        }

54        sprim();

55     }

56     return 0;

57 

58 }

View Code