題目描述：

由于 zzq 太懶了，所以這題沒有題目背景。

有一棵樹，樹上有 n 個(gè)點(diǎn)，每條邊上有一個(gè)非負(fù)邊權(quán)。

在這 n 個(gè)點(diǎn)中有 k 個(gè)特殊點(diǎn)，其中 k 為偶數(shù)。定義兩個(gè)點(diǎn)的距離為它們?cè)跇渖系暮?jiǎn)單路徑上的邊權(quán)之和。你需要將這 k 個(gè)點(diǎn)配成k/2個(gè)互不相交的對(duì)，并最大化每一對(duì)點(diǎn)的距離之和。

思路：

一個(gè)結(jié)論，這k條路經(jīng)至少會(huì)交于一個(gè)公共點(diǎn)，可以證明如果沒有交于一點(diǎn)一定存在一個(gè)更優(yōu)的方案并且交于一點(diǎn)。

于是考慮去求所有選中的點(diǎn)到相交點(diǎn)的距離，動(dòng)態(tài)維護(hù)距離，同時(shí)要保證擁有最多選中點(diǎn)的子樹大小<=k/2，否則會(huì)有路徑無(wú)法交于相交點(diǎn)。

以下代碼：

#include<bits/stdc++.h> #define il inline #define LL long long #define _(d) while(d(isdigit(ch=getchar()))) using namespace std; const int N=1e5+5; bool f[N]; LL ans,dist[N],S; int dfn[N],id,sz[N],mx[N],sum[N],out[N],rt,a[N]; int n,k,head[N],ne[N<<1],to[N<<1],w[N<<1],cnt; il int read(){int x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return f*x; } il void insert(int x,int y,int z){ne[++cnt]=head[x];head[x]=cnt;to[cnt]=y;w[cnt]=z; } il void dfs1(int x,int fa){dfn[x]=++id;sz[x]=f[x];sum[id]=sum[id-1]+f[x];if(f[x])S+=dist[x];for(int i=head[x];i;i=ne[i]){if(to[i]==fa)continue;dist[to[i]]=dist[x]+w[i];dfs1(to[i],x);sz[x]+=sz[to[i]];mx[x]=max(mx[x],sz[to[i]]);}mx[x]=max(mx[x],k-sz[x]);out[x]=id; } il void dfs2(int x,int fa){if(mx[x]*2<=k&&ans<S)ans=S,rt=x;for(int i=head[x];i;i=ne[i]){if(fa==to[i])continue;int tot=sum[out[to[i]]]-sum[dfn[to[i]]-1];S+=1ll*(k-(tot<<1))*w[i];dfs2(to[i],x);S-=1ll*(k-(tot<<1))*w[i];} } int tt=0; vector<int> v[N]; struct node{int x,d,id;bool operator<(const node&t1)const{return d<t1.d;} }; priority_queue<node> q; il void dfs3(int x,int fa){if(f[x])v[tt].push_back(x);for(int i=head[x];i;i=ne[i]){if(fa==to[i])continue;dfs3(to[i],x);} } int main() {n=read();k=read();for(int i=1;i<n;i++){int x=read(),y=read(),z=read();insert(x,y,z);insert(y,x,z);}for(int i=1;i<=k;i++)a[i]=read(),f[a[i]]=1;dfs1(1,0);dfs2(1,0);if(f[rt])v[++tt].push_back(rt);for(int i=head[rt];i;i=ne[i])++tt,dfs3(to[i],rt);for(int i=1;i<=tt;i++){int x=v[i].size();if(!x)continue;q.push((node){v[i][x-1],x-1,i});}for(int i=1;i<=(k>>1);i++){node a=q.top();q.pop();node b=q.top();q.pop();printf("%d %d\n",a.x,b.x);if(a.d>=1)q.push((node){v[a.id][a.d-1],a.d-1,a.id});if(b.d>=1)q.push((node){v[b.id][b.d-1],b.d-1,b.id});}return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/Jessie-/p/10416047.html

總結(jié)

以上是生活随笔為你收集整理的dtoj#4178. 配对（pair）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。