思路是枚举+最小生成树,用DFS枚举或者二进制枚举。
/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 100000000
#define LOCA
#define PI acos(-1.0)
using namespace std;
int d[16][16], node[16], v[16], dis[16], ans[16];
int n, m;
double mi;
bool used[16];
void search()
{
int i, j, k, sum, weight;
sum = 0;
weight = 0;
memset(used, false, sizeof(used));
for(i = 0; i < m; i++)
dis[v[i]] = MAX;
for(i = 0; i < m; i++)
dis[v[i]] = d[v[0]][v[i]];
used[v[0]] = true;
for(i = 1; i < m; i++)
{
int mini = MAX;
int tmp = -1;
for(j = 0; j < m; j++)
if(!used[v[j]] && dis[v[j]] < mini)
{
mini = dis[v[j]];
tmp = v[j];
}
used[tmp] = true;
sum += mini;
for(j = 0; j < m; j++)
{
if(!used[v[j]] && d[v[j]][tmp] < dis[v[j]])
dis[v[j]] = d[v[j]][tmp];
}
}
for(j = 0; j < m; j++)
weight += node[v[j]];
double T = (double)sum / (double)weight;
if(T < mi)
{
for(j = 0; j < m; j++)
ans[j] = v[j];
mi = T;
}
}
void dfs(int x, int cnt)
{
v[cnt] = x;
if(cnt == m - 1)
{
search();
return;
}
for(int i = x + 1; i <= n; i++)
dfs(i, cnt + 1);
}
int main()
{
#ifdef LOCAL
freopen("ride.in","r",stdin);
freopen("ride.out","w",stdout);
#endif
int i, j;
while(scanf("%d%d", &n, &m) != EOF)
{
if(n == 0 && m == 0) break;
for(i = 1; i <= n; i++)
scanf("%d", &node[i]);
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
scanf("%d", &d[i][j]);
}
}
mi = 100000000.0;
for(i = 1; i <= n; i++)
dfs(i, 0);
for(i = 0; i < m - 1; i++)
printf("%d ", ans[i]);
printf("%d\n", ans[m - 1]);
}
return 0;
}
分享到:
相关推荐
NULL 博文链接:https://200830740306.iteye.com/blog/603493
NULL 博文链接:https://128kj.iteye.com/blog/1705139
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
NULL 博文链接:https://128kj.iteye.com/blog/1704752
最小度限制生成树的求法也不是很难,先把度被限制的那个点(s点)去掉,求一次MST,然后把s到各个连通分量的最小权值的边加上,然后继续加边看看能否使生成树权减小(详见解题报告)。
北大POJ2255-Tree Recovery 解题报告+AC代码
度限制最小生成树代码 摘自POJ1639代码
poj 2201 Cartesian Tree.md
poj 1909 Marbles on a tree.md
poj 1308 Is It A Tree_.md
北大POJ2525-Text Formalization【TrieTree】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/XW4FQ3
POJ2014考研试题表达式·表达式树·表达式求值答案
poj2516代码最小费用最大流
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
Give a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance between node u and v. Give an integer k,for every pair (u,v) of vertices is ...
北大POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】 解题报告+AC代码
利用并查集判断环路,以及快速排序计算最小生成树
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj 2589 Snap 测试数据及标程
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。