USACO 3.1 Agri-net(primテンプレート)
6905 ワード
久しぶりにprimを叩いたけど、すばやく秒落ちた.
1 /*
2 ID: cuizhe
3 LANG: C++
4 TASK: agrinet
5 */
6 #include <iostream>
7 #include <cstdio>
8 #include <cstring>
9 #include <cmath>
10 #include <algorithm>
11 using namespace std;
12 #define N 100000000
13 int p[101][101],low[101],o[101];
14 int main()
15 {
16 int i,j,k,n,t,ans;
17 freopen("agrinet.in","r",stdin);
18 freopen("agrinet.out","w",stdout);
19 scanf("%d",&n);
20 for(i = 1;i <= n;i ++)
21 {
22 for(j = 1;j <= n;j ++)
23 scanf("%d",&p[i][j]);
24 }
25 o[1] = 1;
26 for(i = 1;i <= n;i ++)
27 low[i] = p[1][i];
28 ans = 0;
29 for(i = 1;i <= n-1;i ++)
30 {
31 t = N;
32 for(j = 1;j <= n;j ++)
33 {
34 if(!o[j]&&t > low[j])
35 {
36 t = low[j];
37 k = j;
38 }
39 }
40 if(t == N) break;
41 o[k] = 1;
42 ans += t;
43 for(j = 1;j <= n;j ++)
44 {
45 if(low[j] > p[k][j]&&!o[j])
46 low[j] = p[k][j];
47 }
48 }
49 printf("%d
",ans);
50 return 0;
51 }