題意:
? ? ? 給你n個點,和任意兩點的距離,讓你在這N個點中找到一個有m個點并且ratio最小的樹.
? ? ? ? ? ? ? ? ? ? ? ? ratio = sum(edge) / sum(node)

思路: N <= 15 直接DFS暴力枚舉出 m個點,然后再這m個點中跑一邊最小生成樹,這m個點的sum(node) 可以直接加出來,而 sum(edge) 就是最小生數的值,然后求出ratio更新最小,記錄答案.?

#include<stdio.h> #include<string.h> #include<algorithm>#define N 20 #define inf 100000000; using namespace std;typedef struct {int a ,b ,c; }NODE;bool camp(NODE a ,NODE b) {return a.c < b.c; }NODE node[N*N]; int map[N][N] ,weight[N]; int ans_num[N] ,now[N] ,n ,nn; int mer[N]; double now_min;int finds(int x) {if(x == mer[x]) return x;return mer[x] = finds(mer[x]); }void DFS(int s ,int t) {if(t == n + 1){int tmp = 0 ,sum1 = 0 ,sum2 = 0 ,mm = 0;for(int i = 1 ;i <= n ;i ++){sum1 += weight[now[i]];for(int j = i + 1 ;j <= n ;j ++){node[++tmp].a = now[i];node[tmp].b = now[j];node[tmp].c = map[now[i]][now[j]];if(mm < now[i]) mm = now[i];if(mm < now[j]) mm = now[j];}}sort(node + 1 ,node + tmp + 1 ,camp);for(int i = 1 ;i <= mm ;i ++)mer[i] = i;mm = 0;for(int i = 1 ;i <= tmp ;i ++){int x = finds(node[i].a);int y = finds(node[i].b);if(x == y) continue; mer[x] = y;sum2 += node[i].c; if(++mm == n - 1) break;}//printf("%d %d %d %d\n" ,sum1 ,sum2 ,now[1] ,now[2]); double nowm = sum2 * 1.0 / sum1;if(nowm < now_min){now_min = nowm;for(int i = 1 ;i <= n ;i ++)ans_num[i] = now[i];}return ;}for(int i = s + 1 ;i <= nn ;i ++){now[t] = i;DFS(i ,t + 1);} }int main () {int i;while(scanf("%d %d" ,&nn ,&n) && n + nn){for(i = 1 ;i <= nn ;i ++)scanf("%d" ,&weight[i]);for(i = 1 ;i <= nn ;i ++)for(int j = 1 ;j <= nn ;j ++)scanf("%d" ,&map[i][j]);now_min = inf;DFS(0 ,1);for(i = 1 ;i < n ;i ++)printf("%d " ,ans_num[i]);printf("%d\n" ,ans_num[i]);}return 0; }

? ? ? ?





《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的hdu2489-DFS+最小生成树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。