hdu2489Minimal Ratio Tree 最小生成樹

hdu2489Minimal Ratio Tree 最小生成樹

//給一個完全圖，在其中找一顆樹，使得邊的權值之和除以點的權值之和最小
//由於n<=15，直接暴力枚舉所有選的點的情況，在從這些點找最小生成樹
#include
#include
#include
using namespace std ;
const int inf = 0x3f3f3f3f ;
const int maxn = 20 ;
int vis[maxn] ;
int dis[maxn] ;
int tmp[maxn] ;
int w[maxn] ;int a[maxn] ;
int map[maxn][maxn] ;
int n , m;
int prim()
{
    int pos ;
    memcpy(tmp , vis , sizeof(vis)) ;
    for(int i = 1;i <= n;i++)
    if(!vis[i])
    {
        vis[i] = 1 ;
        pos = i ;
        break;
    }
    for(int i = 1;i <= n;i++)
    dis[i] = i == pos ? 0 : map[pos][i] ;
    int ans = 0 ;
    while(1)
    {
        int mi = inf ;
        for(int i = 1;i <= n;i++)
        if(!vis[i] && dis[i] < mi)
        mi = dis[pos = i] ;
        if(mi == inf)break;
        vis[pos] = 1;
        ans += mi ;
        for(int i = 1;i <= n;i++)
        if(!vis[i])
        dis[i] = min(dis[i] , map[pos][i]) ;
    }
    memcpy(vis , tmp , sizeof(tmp)) ;
    return ans ;
}
double ans = inf ;
void dfs(int pos , int num , double sum )
{
    if(num == m)
    {
        double sum_e = prim() ;
        if(sum_e/sum < ans)
        {
            ans = sum_e/sum ;
            memcpy(a , vis , sizeof(vis)) ;
        }
        return ;
    }
    for(int i = pos;i <= n;i++)
    {
        if(!vis[i])continue ;
        vis[i] = 0 ;
        dfs(i , num + 1 , sum + w[i]) ;
        vis[i] = 1 ;
    }
}
int main()
{
    //freopen(in.txt ,r , stdin) ;
    while(scanf(%d%d , &n ,&m) &&(n+m))
    {
        for(int i = 1;i <= n;i++)
        scanf(%d , &w[i]) ;
        for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n ;j++)
        scanf(%d , &map[i][j]) ;
        for(int i = 1;i <= n;i++)
        vis[i] = 1;
        ans = inf ;
        dfs(1,0 , 0) ;
        int flag = 0 ;
        for(int i = 1;i <= n ;i++)
        if(!a[i])
        {
            if(flag)printf( ) ;
            printf(%d , i) ;
            flag = 1 ;
        }
        puts() ;
    }
    return 0 ;
}