| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 81076 | Accepted: 33464 |
Description
Input
Output
Sample Input
4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0
Sample Output
28
Source
模板题
这题TLE了一天，脑溢血了。 用scanf + printf会TLE，换成cin取消同步以后就AC了。
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <vector> 5 #include <iomanip> 6 #include <cmath> 7 #include <cstdio> 8 using namespace std; 9 const int MAXN = 103; 10 const int INF = 0x3f3f3f3f; 11 typedef long long ll; 12 13 14 int n, num; 15 bool vis[MAXN]; 16 int dist[MAXN], g[MAXN][MAXN]; 17 18 int prim(){ 19 int ans = 0; 20 memset(vis, 0, sizeof vis); 21 for(int i = 1; i <= n; ++ i){ 22 dist[i] = INF; 23 } 24 25 for(int i = 0; i < n; ++ i){ 26 int t = -1; 27 for(int j = 1; j <= n; ++ j) 28 if(!vis[j] and (t == -1 or dist[t] > dist[j])) 29 t = j; 30 if(i) 31 ans += dist[t]; 32 for(int j = 1; j <= n; ++ j) 33 if(j != t) 34 dist[j] = min(dist[j], g[t][j]); 35 36 vis[t] = true; 37 38 } 39 return ans; 40 } 41 int main(){ 42 int x, y, w; 43 ios::sync_with_stdio(false); 44 cin.tie(0); 45 cout.tie(0); 46 while(cin >> n and n){ 47 num = 0; 48 49 for(int i = 1; i <= n; ++ i){ 50 for(int j = 1; j <= n; ++ j){ 51 cin >> w; 52 g[i][j] = w; 53 } 54 } 55 56 cout << prim() << endl; 57 } 58 return 0; 59 }
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 #include <vector> 6 #include <iomanip> 7 #include <cmath> 8 using namespace std; 9 const int MAXN = 113; 10 const int INF = 0x3f3f3f3f; 11 typedef long long ll; 12 typedef struct _edge{ 13 int u; 14 int v; 15 int w; 16 bool operator< (const _edge& e) const { 17 return w < e.w; 18 } 19 }edge; 20 21 edge edges[10003]; 22 int n, num; 23 int pa[MAXN]; 24 25 int find(int x){ 26 return x == pa[x]? x : (pa[x] = find(pa[x])); 27 } 28 bool Union(int x, int y){ 29 x = find(x); 30 y = find(y); 31 if(x == y) 32 return false; 33 pa[y] = x; 34 return true; 35 } 36 int kruskal(){ 37 int ans = 0; 38 int cnt = 1; 39 for(int i = 1; i <= n; ++ i) 40 pa[i] = i; 41 sort(edges, edges + num); 42 43 for(int i = 0; i < num; ++ i){ 44 if(Union(edges[i].u, edges[i].v)){ 45 ans += edges[i].w; 46 ++ cnt; 47 if(cnt == n) 48 break; 49 } 50 } 51 return ans; 52 } 53 int main(){ 54 int x, y, w; 55 ios::sync_with_stdio(false); 56 cin.tie(0); 57 cout.tie(0); 58 while(cin >> n and n){ 59 num = 0; 60 for(int i = 1; i <= n; ++ i){ 61 for(int j = 1; j <= n; ++ j){ 62 cin >> w; 63 if(j > i){ 64 edges[num].u = i; 65 edges[num].v = j; 66 edges[num ++].w = w; 67 } 68 } 69 } 70 71 cout << kruskal() << endl; 72 } 73 return 0; 74 }
原文：https://www.cnblogs.com/daremo/p/14432388.html
