問題 B: 聯合權值

時間限制: 1 Sec??內存限制: 128 MB
提交: 138??解決: 21
[提交] [狀態] [討論版] [命題人:admin]

題目描述

無向連通圖G 有n 個點，n - 1 條邊。點從1 到n 依次編號，編號為 i 的點的權值為W i ，每條邊的長度均為1 。圖上兩點( u , v ) 的距離定義為u 點到v 點的最短距離。對于圖G 上的點對( u, v) ，若它們的距離為2 ，則它們之間會產生Wu×Wv 的聯合權值。
請問圖G 上所有可產生聯合權值的有序點對中，聯合權值最大的是多少？所有聯合權值之和是多少？

?

輸入

第一行包含1 個整數n 。
接下來n - 1 行，每行包含 2 個用空格隔開的正整數u 、v ，表示編號為 u 和編號為v 的點之間有邊相連。
最后1 行，包含 n 個正整數，每兩個正整數之間用一個空格隔開，其中第 i 個整數表示圖G 上編號為i 的點的權值為W i 。

?

輸出

輸出共1 行，包含2 個整數，之間用一個空格隔開，依次為圖G 上聯合權值的最大值
和所有聯合權值之和。由于所有聯合權值之和可能很大，[b]輸出它時要對10007 取余。

?

樣例輸入

復制樣例數據

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

樣例輸出

20 74

?

提示

本例輸入的圖如上所示，距離為2 的有序點對有( 1,3) 、( 2,4) 、( 3,1) 、( 3,5) 、( 4,2) 、( 5,3) 。

其聯合權值分別為2 、15、2 、20、15、20。其中最大的是20，總和為74。

?

?

對于 30%的數據，1 < n ≤ 100；

對于 60%的數據，1 < n ≤ 2000；

對于 100%的數據，1 < n ≤ 200,000，0 <?Wi?≤ 10,000。?

思路：先枚舉以每個點為中軸點，找出與其直接相連的點，記錄總值和最大值，判斷一下是否有多個最大值，然后枚舉每個點所對應的另一邊的點，注意體會這兩次枚舉的點的差別。

#include<bits/stdc++.h> #define REP(i, a, b) for(int i = (a); i <= (b); ++ i) #define REP(j, a, b) for(int j = (a); j <= (b); ++ j) #define PER(i, a, b) for(int i = (a); i >= (b); -- i) using namespace std; const int maxn=2e6+666; template <class T> inline void rd(T &ret){char c;ret = 0;while ((c = getchar()) < '0' || c > '9');while (c >= '0' && c <= '9'){ret = ret * 10 + (c - '0'), c = getchar();} } long long w[maxn],r,s,t,dis[maxn],tot[maxn],mx[maxn],pos[maxn],cover[maxn],ans,mans; int head[maxn],l; struct node{int v,nx; }p[maxn]; long long n,m; void addedge(int x,int y){p[++l].v=x,p[l].nx=head[y],head[y]=l;p[++l].v=y,p[l].nx=head[x],head[x]=l; }int main(){rd(n);REP(i,1,n-1){int a,b;rd(a),rd(b);addedge(a,b);}REP(i,1,n)rd(w[i]);REP(i,1,n){for(int j=head[i];j;j=p[j].nx){tot[i]+=w[p[j].v];if(mx[i]<w[p[j].v])mx[i]=w[p[j].v],pos[i]=p[j].v,cover[i]=0;else if(mx[i]==w[p[j].v])cover[i]=1;}}REP(i,1,n){for(int j=head[i];j;j=p[j].nx){ans=(ans+w[i]*(tot[p[j].v]-w[i]))%10007;if(cover[p[j].v]||pos[p[j].v]!=i)mans=max(mans,w[i]*mx[p[j].v]);}}cout<<mans<<' '<<ans<<endl;return 0; }

?

點，統計答案就好了。

?

?

轉載于:https://www.cnblogs.com/czy-power/p/10412560.html

總結

以上是生活随笔為你收集整理的联合权值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。