“玲珑杯”ACM比赛 Round #18--最后你还是AK了（搜索+思维）

题目链接

DESCRIPTION

INPUT

OUTPUT

SAMPLE INPUT

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

思路：官方题解：

我的理解：其实每条边上的值的大小并不影响点的匹配，对于任意一条边来说，对应一个父节点和孩子节点，令以这个孩子为根节点的子树包含的节点数为 t，总节点数位 n，我们应该尽量使子树上的点都过这条边去和子树以外的点匹配，所以过该边的最大点对数为min(t,n-t), 所以ans+=min(t,n-t)*w ,可以利用树上搜索得到该树的最大可爱值，对于k次使用魔法，可以对每条边进过的次数进行排序，贪心的吧增量大用得到进过次数多的边上即可。

代码如下：

#define OPENSTACK

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

typedef long long LL;

const int maxn=1e5+;

vector<pair<int,int> > v[maxn];

int c[maxn], cn[maxn], tmp, n;

LL ans;

int dfs(int p,int f)

{

    int count=;

    for(int i=; i<v[p].size(); i++)

    {

        pair<int,int>pa=v[p][i];

        if(pa.first==f) continue;

        int t=dfs(pa.first,p);

        cn[tmp]=min(t,n-t);

        ans+=(LL)cn[tmp]*(LL)pa.second;

        tmp++;

        count+=t;

    }

    return count+;

}

int main()

{

    #ifdef OPENSTACK

    long long 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 T,k;  cin>>T;

    while(T--)

    {

        for(int i=;i<maxn;i++) v[i].clear();

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

        for(int i=;i<n;i++)

        {

            int u1,u2,w;

            scanf("%d%d%d",&u1,&u2,&w);

            pair<int,int>pa1=make_pair(u1,w);

            pair<int,int>pa2=make_pair(u2,w);

            v[u1].push_back(pa2);

            v[u2].push_back(pa1);

        }

        for(int i=;i<k;i++) scanf("%d",&c[i]);

        ans=; tmp=;

        int res=dfs(,-);

        //cout<<"点数-----"<<res<<endl;

        //cout<<"    -----"<<ans<<endl;

        sort(cn,cn+tmp);

        sort(c,c+k);

        for(int i=tmp-, j=k-; j>=; i--, j--)

        {

            ans+=(LL)c[j]*(LL)cn[i];

        }

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

    }

    #ifdef OPENSTACK

    exit();

    #else

        return ;

    #endif

}

秒客网

“玲珑杯”ACM比赛 Round #18--最后你还是AK了（搜索+思维）

相关文章