题目:题目链接
题意:给你一个图,然后求最小花费的图使得所有的点都有被连到
分析:最小生成树,需要注意的是这里的边是更新的,每次都需要判断一下是不是边的权值被更新了。Prime竟然不超时。
代码:
#include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <stack> #include <functional> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cassert> #include <bitset> #include <stack> #include <ctime> #include <list> #define INF 0x7fffffff #define max3(a,b,c) (max(a,b)>c?max(a,b):c) #define min3(a,b,c) (min(a,b)<c?min(a,b):c) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; int QuickMod(int a,int b,int n) { int r = 1; while(b) { if(b&1) r = (r*a)%n; a = (a*a)%n; b >>= 1; } return r; } #define maxn 100 int mp[maxn][maxn]; int n, p; int solve() { int s = 1; int m = 1; int u[maxn]; mem(u, 0); u[s] = 1; int min_w; int prim_w = 0; int point; int low_dis[maxn]; for(int i=1; i <= n; i++) low_dis[i] = INF; while(1) { if(m == n) break; min_w = INF; for(int i = 2; i <= n; i++) { if(!u[i] && low_dis[i] > mp[s][i]) low_dis[i] = mp[s][i]; if(!u[i] && min_w > low_dis[i]) { min_w = low_dis[i]; point = i; } } s = point; u[s] = 1; prim_w += min_w; m++; } return prim_w; } int main() { while(scanf("%d", &n) && n) { scanf("%d", &p); int a, b, cost; for(int i = 0; i < 55; ++i) for(int j = 0; j < 55; ++j) mp[i][j] = INF; for(int i = 0; i < p; ++i) { scanf("%d%d%d", &a, &b, &cost); mp[a][b] = min(mp[a][b], cost); mp[b][a] = min(mp[b][a], cost); } int ans = solve(); printf("%d\n", ans); } return 0; }