玲珑杯1147 - 最后你还是AK了

1147 - 最后你还是AK了

Time Limit：5s Memory Limit：256MByte

DESCRIPTION

今天HHHH遇到了一颗树,这个树有nn个点(nn为偶数),每条边都有一个长度ll,现在HHHH想把这nn个点两两匹配,匹配成n/2n/2对点,然后我们将匹配后的n/2n/2对点的距离求和,我们将所有匹配方案里距离和最大的那一个值定义为可爱值.

即我们将这nn个点分成了

定义dis(x,y)dis(x,y)为xx到yy的距离,那么可爱值为

max(∑n/2i=1dis(ai,bi))max(∑i=1n/2dis(ai,bi))

现在HHHH为了使这颗树变可爱,他可以使用kk次膜法,第ii次能使一条边的长度增加cici,但是被膜过的边就不能再被膜了,现在HHHH想知道使用了膜法以后,这颗树的可爱值最多能是多少.

INPUT

第一行是一个整数T(1≤T≤10)T(1≤T≤10),表示有TT组数据
对于每组数据输入一行2个整数n,k (1≤n≤105,0≤k≤n−1)n,k (1≤n≤105,0≤k≤n−1)表示这棵树总共有nn个点,HHHH可以使用kk次膜法.
接着一行n−1n−1行每行3个数:u,v,w(1≤u,v≤n,1≤w≤105)u,v,w(1≤u,v≤n,1≤w≤105)表示在uu和vv之间有一条长度为ww的边.
最后一行kk个整数,第ii个整数ci(1≤ci≤105)ci(1≤ci≤105)表示第ii种膜法能使得某一条边变长cici
保证nn为偶数且给出的是一颗树

OUTPUT

每组数据输出一行,一个整数,表示♂可♂爱♂值♂最多能是多少

SAMPLE INPUT

1
4 2
1 2 5
2 3 5
3 4 5
5 5

SAMPLE OUTPUT

HINT

对于样例,我们将1和4匹配,2和3匹配,然后对2和3之间的边使用膜法,对3和4之间的边使用魔法
若出现爆栈问题，改栈方法请参考1093题目代码
1093地址：http://www.ifrog.cc/acm/problem/1093
代码地址：http://ideone.com/Wk24ET

分析：不考虑加魔法时与加魔法是独立的；

　　　不加魔法时贪心的对每条边算贡献为min(son[x] , n - son[x] )*len ,可以想象一下是可行的；

　　　加入魔法时只需贪心的放min(son[x] , n - son[x] )大的边即可；

代码：

#define OPENSTACK

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <climits>

#include <cstring>

#include <string>

#include <set>

#include <bitset>

#include <map>

#include <queue>

#include <stack>

#include <vector>

#include <cassert>

#include <ctime>

#define rep(i,m,n) for(i=m;i<=(int)n;i++)

#define mod 1000000007

#define inf 0x3f3f3f3f

#define vi vector<int>

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define ll long long

#define pi acos(-1.0)

#define pii pair<int,int>

#define sys system("pause")

#define ls rt<<1

#define rs rt<<1|1

const int maxn=1e5+;

const int N=5e2+;

using namespace std;

ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}

ll qmul(ll p,ll q,ll mo){ll f=;while(q){if(q&)f=(f+p)%mo;p=(p+p)%mo;q>>=;}return f;}

ll qpow(ll p,ll q,ll mo){ll f=;while(q){if(q&)f=qmul(f,p,mo)%mo;p=qmul(p,p,mo)%mo;q>>=;}return f;}

int n,m,k,t,son[maxn],c[maxn],id[maxn];

vi e[maxn];

vi f[maxn];

ll ret;

bool cmp(int x,int y){return min(son[x],n-son[x])>min(son[y],n-son[y]);}

void dfs(int x,int y)

{

    son[x]=;

    int i;

    rep(i,,e[x].size()-)

    {

        int z=e[x][i],w=f[x][i];

        if(z==y)continue;

        dfs(z,x);

        ret+=1LL*min(son[z],n-son[z])*w;

        son[x]+=son[z];

    }

}

int main()

{

        #ifdef OPENSTACK

        int size =  << ; // 64MB

        char *p = (char*)malloc(size) + size;

        #if (defined _WIN64) or (defined __unix)

            __asm__("movq %0, %%rsp\n" :: "r"(p));

        #else

            __asm__("movl %0, %%esp\n" :: "r"(p));

        #endif

    #endif

    int i,j;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&n,&k);

        rep(i,,n)id[i]=i,e[i].clear(),f[i].clear(),son[i]=;

        rep(i,,n-)

        {

            int x,y,z;

            scanf("%d%d%d",&x,&y,&z);

            e[x].pb(y);

            f[x].pb(z);

            e[y].pb(x);

            f[y].pb(z);

        }

        rep(i,,k)scanf("%d",&c[i]);

        ret=;

        dfs(,);

        sort(c+,c+k+,greater<int>());

        sort(id+,id+n+,cmp);

        rep(i,,min(n,k))ret+=1LL*min(son[id[i]],n-son[id[i]])*c[i];

        printf("%lld\n",ret);

    }

    #ifdef OPENSTACK

        exit();

    #else

        return ;

    #endif

}

巴特西

玲珑杯1147 - 最后你还是AK了

最新文章

热门文章