“玲珑杯”ACM比赛 Round #18--最后你还是AK了(…

2018-06-17 22:12:35来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目链接
 
DESCRIPTION

 

INPUT

OUTPUT
SAMPLE INPUT
1
4 2
1 2 5
2 3 5
3 4 5
5 5
SAMPLE OUTPUT
35
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+5;
vector<pair<int,int> > v[maxn];
int c[maxn], cn[maxn], tmp, n;
LL ans;

int dfs(int p,int f)
{
    int count=0;
    for(int i=0; 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+1;
}

int main()
{
    #ifdef OPENSTACK
    long long size = 64 << 20; // 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=0;i<maxn;i++) v[i].clear();
        scanf("%d%d",&n,&k);
        for(int i=1;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=0;i<k;i++) scanf("%d",&c[i]);
        ans=0; tmp=0;
        int res=dfs(1,-1);
        //cout<<"点数-----"<<res<<endl;
        //cout<<"    -----"<<ans<<endl;
        sort(cn,cn+tmp);
        sort(c,c+k);
        for(int i=tmp-1, j=k-1; j>=0; i--, j--)
        {
            ans+=(LL)c[j]*(LL)cn[i];
        }
        printf("%lld\n",ans);
    }
    #ifdef OPENSTACK
    exit(0);
    #else
        return 0;
    #endif
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Brackets

下一篇:单调队列初步——转载自“he-honghua的专栏”