首页 > 代码库 > 【HDU1875】畅通工程再续(MST基础题)
【HDU1875】畅通工程再续(MST基础题)
更改成实形数即可。第一次敲完直接交,CE了一次。晕。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cstdio> 5 #include <cctype> 6 #include <cmath> 7 #include <algorithm> 8 #include <numeric> 9 10 #define typec double11 using namespace std;12 13 const typec inf = 0xffff;14 const int V = 1005;15 int vis[V];16 typec lowc[V], Map[V][V], point[V][2];17 18 typec prim (typec cost[][V], int n) {19 int i, j, p;20 typec minc, res = 0;21 memset(vis, 0, sizeof(vis));22 vis[0] = 1;23 for (i = 1; i < n; ++ i) lowc[i] = cost[0][i];24 for (i = 1; i < n; ++ i) {25 minc = inf; p = -1;26 for (j = 0; j < n; ++ j ) {27 if (0 == vis[j] && minc > lowc[j]) {28 minc = lowc[j];29 p = j;30 }31 }32 if (inf == minc) return -1;33 res += minc;34 vis[p] = 1;35 for (j = 0; j < n; ++ j) {36 if (0 == vis[j] && lowc[j] > cost[p][j]) {37 lowc[j] = cost[p][j];38 }39 }40 }41 return res;42 }43 44 double cal_dis (double x1, double y1, double x2, double y2) {45 return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));46 }47 48 int main () {49 int T; scanf("%d", &T);50 while (T --) {51 //vector<pair<double, double> > p;52 int n; scanf("%d", &n);53 for (int i = 0; i < n; ++ i) {54 scanf("%lf%lf", &point[i][0], &point[i][1]);55 }56 57 for (int i = 0 ; i < 105; ++ i) {58 for (int j = 0; j < 105; ++ j) {59 if (i == j) Map[i][j] = 0;60 else Map[i][j] = inf;61 }62 }63 64 for (int i = 0; i < n; ++i) {65 for (int j = i + 1; j < n; ++ j) {66 double w = cal_dis(point[i][0], point[i][1],point[j][0],point[j][1]);67 if (w >= 10 && w <= 1000)68 Map[i][j] = Map[j][i] = min(Map[i][j], w);69 else continue;70 /*cout << Map[i][j] << endl;71 cout << Map[j][i] << endl;*/72 }73 }74 75 /*for (int i = 0; i < 2; ++ i) {76 for (int j = 0 ; j < 2; ++ j) {77 cout << Map[i][j] << " ";78 }79 cout << endl;80 }*/81 double ans = 100 * prim(Map, n);82 if (ans > 0)83 printf("%.1lf\n", ans);84 else {85 printf("oh!\n");86 }87 //cout << prim (Map, n) << endl;88 }89 return 0;90 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。