POJ2075是到PRIM练习题，但是很坑爹。有个很奇怪的问题就是：输出浮点数%.1f就过 %.1lf就不过。如果有人知道原因，请一定告知！不知道是不是.1f是四舍五入的 %.1lf是取floor的？
#include#include #include using std::memset;const int MAX = 1005;double totallength;double map[MAX][MAX];char house[MAX][30];int n,m;double prim(){ bool visit[MAX]; double dis[MAX]; memset(visit, 0, sizeof(visit)); for(int i = 0 ; i < n; i++) dis[i] = -1; dis[0] = 0; double ans = 0; for(int i = 0 ; i< n; i++) { //find mingap double mindis = INT_MAX; int minindex = -1; for(int j = 0 ; j < n; j++) { if(!visit[j] && dis[j]!= -1 && mindis > dis[j]) { mindis = dis[j]; minindex = j; } } visit[minindex] = 1; ans += mindis; int from = minindex; for(int to = 0 ; to < n; to++) { if(visit[to]) continue; if(map[from][to] == 0) continue; if(dis[to] == -1 || map[from][to] < dis[to]) { dis[to] = map[from][to]; } } } return ans;}int main(){ while(scanf("%lf", &totallength)!=EOF) { scanf("%d", &n); for(int i = 0 ; i< n; i++) scanf("%s", house[i]); scanf("%d", &m); for(int i = 0 ; i < m; i++) { char house1[30], house2[30]; double length; scanf("%s %s %lf", &house1, &house2, &length); int house1index, house2index; for(int j = 0 ; j < n; j++) { if(strcmp(house1, house[j]) == 0) house1index = j; } for(int j = 0 ; j < n; j++) { if(strcmp(house2, house[j]) == 0) house2index = j; } map[house1index][house2index] = length; map[house2index][house1index] = length; } double ans = prim(); if(ans > totallength) printf("Not enough cable\n"); else printf("Need %.1f miles of cable\n", ans); }}