比赛 20111012 评测结果 AAAAAAAWAA
题目名称 配药惊魂 最终得分 90
用户昵称 fanzeyi 运行时间 0.000 s
代码语言 C 内存使用 0.00 MiB
提交时间 2011-10-12 21:44:20
显示代码纯文本
/*
ID: fanzeyi1
LANG: C
TASK: drug 
*/
/*
 * =====================================================================================
 *
 *       Filename:  drug.c
 *        Version:  1.0
 *        Created:  10/12/2011 08:33:29 PM
 *       Revision:  none
 *       Compiler:  gcc
 *         Author:  Zeray Fan, fanzeyi1994[at]gmail.com
 *        Company:  http://www.fanhe.org/
 *
 * =====================================================================================
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef struct {
    double value; 
    int n; 
}val; 

int v, n, m; 
int drug[17]; 
int cant[17][17]; 
int nv; 
val value[65537]; 
short now[17]; 
short used[17]; 

int check(int i) {
    int j; 
    for( j = 0 ; j < n ; j++ ) {
        if(used[j]) {
            if(cant[i][j]) {
                return 0; 
            }
        }
    }
    return 1; 
}

void RemValue() {
    int i; 
    int a = 0; 
    int b = 0; 
    for( i = 0 ; i < n ; i++ ) {
        if(used[i]) {
            a = a + 1; 
            b = b + drug[i]; 
        }
    }
    if(!a) {
        return; 
    }
    value[nv].value = (double)b / a * sqrt(a); 
    value[nv++].n = a; 
}

void getvalue(int times) { 
    if(times == n) {
        RemValue(); 
        return; 
    }
    // 用药
    if(check(times)) {
        used[times] = 1; 
        getvalue(times + 1); 
        used[times] = 0; 
    }
    getvalue(times + 1); 
}

int cmp(const void *a, const void *b) {
    val *c = (val *) a;
    val *d = (val *) b; 
    if(c->value > d->value) {
        return -1; 
    }else{
        return 1; 
    }
}

int main(void) {
    FILE *fin = fopen("drug.in","r");
    FILE *fout = fopen("drug.out", "w");
    int a, b; 
    int i, j; 
    int pack = 0; 
    double result = 0; 
    fscanf(fin, "%d %d %d", &v, &n, &m);
    for( i = 0 ; i < n ; i++ ) {
        fscanf(fin, "%d", &drug[i]); 
    }
    for( i = 0 ; i < m ; i++ ) {
        fscanf(fin, "%d %d", &a, &b); 
        cant[a-1][b-1] = 1; 
        cant[b-1][a-1] = 1; 
    }
    getvalue(0); 
    qsort(value, nv, sizeof(val), cmp); 
    for( i = 0 ; i < nv ; i++ ) {
        for( j = 0 ; j < value[i].n ; j++ ) {
            pack = pack + 1; 
            result = result + value[i].value;
            if(pack == v) {
                fprintf(fout, "%.1lf\n", result); 
                return 0; 
            }
        }
    }
    fprintf(fout, "%.1lf\n", result); 
    return 0;
}