題目鏈接 DESCRIPTION INPUT 題目鏈接 DESCRIPTION INPUT INPUT INPUT OUTPUT OUTPUT SAMPLE INPUT 1 4 2 1 2 5 2 3 5 3 4 5 5 5 SAMPLE INPUT 1 4 2 1 2 5 2 3 5 3 4 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 }
