最优布线问题(wire.cpp)

 1 #include<iostream>
 2 using namespace std;
 3 #include<cstring>
 4 #define N 2010
 5 int minn[N];
 6 int map[N][N];
 7 bool vis[N];
 8 int n,m;
 9 int sum;
10 int main()
11 {
12     memset(minn,0x7f,sizeof(minn));
13     cin>>n;
14     for(int i=1;i<=n;++i)
15     {
16         for(int j=1;j<=n;++j)
17         cin>>map[i][j];
18     }
19     minn[1]=0;
20     for(int i=1;i<=n;++i)
21     {
22         int k=0;
23         for(int j=1;j<=n;++j)
24             if(!vis[j]&&minn[k]>minn[j])k=j;
25         vis[k]=1;
26         for(int j=1;j<=n;++j)
27         {
28             if(!vis[j]&&(map[k][j]<minn[j]))
29                 minn[j]=map[k][j];
30         }
31     }
32     for(int k=1;k<=n;++k)sum+=minn[k];
33     cout<<sum;
34     return 0;
35 }