hdu2489 Minimal Ratio Tree

題意：一個 至多 ?n=15 的 完全圖 ，求 含有 m 個節(jié)點的樹 使 邊權(quán)和 除 點權(quán)和 最小

題解：枚舉 m 個 點 ，然后 求 最小生成樹

自己粗心。。。。WA 了 好多次……（233333 ）

#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <map> #include <queue> #include <stack> #include <set> #include <string> using namespace std; typedef long long ll; const double ESP = 10e-8; const int MOD = 1000000007; typedef long long LL; const int MAXN = 15 + 3;int graph[MAXN][MAXN]; int node[MAXN]; int tmp[MAXN]; int dist[MAXN]; int ans[MAXN]; double ansMi; int n,m; bool vis[MAXN]; double prim(){double dis = 0;memset(vis,0,sizeof(vis));int cur = 0;vis[cur] = 1;for(int i = 0;i < m;i++){dist[i] = graph[ tmp[cur] ][ tmp[i] ];}for(int i = 0;i < m-1;i++){int mi = 0x7ffffff;int k;for(int j = 0;j < m;j++){if(!vis[j] && dist[j] < mi){mi = dist[j];k = j;}}cur = k;vis[cur] = 1;dis += mi;for(int j = 0;j < m;j++){if(!vis[j] && dist[j] > graph[ tmp[cur] ][ tmp[j] ]){dist[j] = graph[ tmp[cur] ][ tmp[j] ];}}}return dis; }void dfs(int v,int cnt){if(cnt == m-1){double h = 0;for(int i = 0;i < m;i++){h += node[ tmp[i] ];}double b = prim();double tt = b/h;if(tt - ansMi < -(1e-9)){ansMi = tt;for(int i = 0;i < m;i++){ans[i] = tmp[i];}}return;}for(int i = v+1;i<= n;i++){tmp[cnt+1] = i;dfs(i,cnt+1);} }int main(){ // freopen("input.txt","r",stdin);while(~scanf("%d%d",&n,&m) && n &&m){for(int i = 1;i <= n;i++){scanf("%d",&node[i]);}for(int i = 1;i <= n;i++){for(int j = 1;j <= n;j++){scanf("%d",&graph[i][j]);}}ansMi = 10e10;for(int i = 1;i <= n;i++){tmp[0] = i;dfs(i,0);}for(int i = 0;i < m-1;i++){printf("%d ",ans[i]);}printf("%d\n",ans[m-1]);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/hanbinggan/p/4681059.html

總結(jié)

以上是生活随笔為你收集整理的hdu2489 Minimal Ratio Tree的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。