洛谷题解 P1351 【联合权值】

Problem

P1351 【联合权值】

record

用时： 99ms
空间： 13068KB(12.76MB)
代码长度： 3.96KB
提交记录： R9883701
注：使用了
1. o1 优化
2. o2 优化
3. o3 优化
4. use-v4
5. 快读快输

Solution

直接爆搜，枚举每两个距离为 2 的点，然后记录答案。

写法优异可以拿走

代码。。。就不放了，有兴趣的可以看：

(use-v4)

(use-v3)

考虑我们的思路慢在哪儿？

在于组合！

考虑一个菊花图，复杂度几乎是 $Θ(n^2) 的，当然慢。$

想到乘法交换律（数学老师不要怪我这么长时间才想起你）

这时候考虑任意两个距离为 2 的有序点对一定会有一个中间点，枚举这个点即可，并不需要搜索。复杂度

思路基本没什么问题了吧！

等等，图 G 上联合权值的最大值呢？

每次记录中间点相邻点中最大的和次大的即可。

没问题了吧？

不，还有问题！

答案要乘 2 ！

因为题目可以看成一对有序点对要计算两次。

Code

  1 // luogu-judger-enable-o2
  2 /*
  3     Problem:    P1351 联合权值 
  4     Author:     航空信奥 
  5     Date:       2018/08/18
  6     Upload:     Luogu
  7     P.s.:       use-v4
  8 */
  9 #pragma GCC optimize("O1")
 10 #pragma GCC optimize("O2")
 11 #pragma GCC optimize("O3")
 12 #include <stdio.h>
 13 #include <string.h>
 14 #include <vector>
 15 using namespace std;
 16 
 17 namespace AuthorName { /* 防重名 */
 18     template <typename _TpInt> inline _TpInt read();
 19     template <typename _TpInt> inline void write(_TpInt x);
 20 
 21 #   define Online_Judge
 22 #   define Max_N 200007
 23 #   define Mod 10007
 24 
 25     vector<vector<int> > g;
 26     int *w;
 27     int maxx = 0, sum = 0;
 28 
 29     void work(int p)
 30     {
 31         int max_1st = 0, max_2nd = 0, temp_sum = 0;
 32         for (size_t i = 0; i < g[p].size(); i++) {
 33             if (w[g[p][i]] > max_1st) {
 34                 max_2nd = max_1st;
 35                 max_1st = w[g[p][i]];
 36             }
 37             else if (w[g[p][i]] > max_2nd) {
 38                 max_2nd = w[g[p][i]];
 39             }
 40             sum = (sum + temp_sum * w[g[p][i]]) % Mod;
 41             temp_sum = (temp_sum + w[g[p][i]]) % Mod;
 42         }
 43         maxx = max(maxx, max_1st * max_2nd);
 44     } 
 45 
 46     int main() 
 47     {   
 48         int n;
 49         n = read<int>();
 50         g.resize(n + 1);
 51         w = new int[n + 1];
 52         int u, v;
 53         for (int i = 1; i < n; i++) {
 54             u = read<int>();
 55             v = read<int>();
 56             g[u].push_back(v);
 57             g[v].push_back(u);
 58         }
 59         for (int i = 1; i <= n; i++) {
 60             w[i] = read<int>();
 61         }
 62         for (int i = 1; i <= n; i++) {
 63             work(i);
 64         }
 65 
 66         write(maxx), putchar(32), write((sum << 1) % Mod), putchar(10);
 67 
 68         return 0;
 69     }
 70 
 71 #ifdef Online_Judge
 72     char BufferRead[1 << 15];
 73     int rLen = 0, rPos = 0;
 74     inline char Getchar()
 75     {
 76         if (rPos == rLen) rPos = 0, rLen = fread(BufferRead, 1, 1 << 15, stdin);
 77         if (rPos == rLen) return EOF;
 78         return BufferRead[rPos++];
 79     } 
 80 #else
 81 #   define Getchar() getchar()
 82 #endif
 83 
 84     template <typename _TpInt>
 85     inline _TpInt read()       
 86     {
 87         register int flag = 1;
 88         register char c = Getchar();
 89         while ((c > '9' || c < '0') && c != '-') 
 90             c = Getchar();
 91         if (c == '-') flag = -1, c = Getchar();
 92         register _TpInt init = (c & 15);
 93         while ((c = Getchar()) <= '9' && c >= '0') 
 94             init = (init << 3) + (init << 1) + (c & 15);
 95         return init * flag;
 96     }
 97 
 98     template <typename _TpInt>
 99     inline void write(_TpInt x)
100     {
101         if (x < 0) {
102             putchar('-');
103             write<_TpInt>(~x + 1);
104         }
105         else {
106             if (x > 9) write<_TpInt>(x / 10);   
107             putchar(x % 10 + '0');
108         }
109     }
110 }
111 
112 int main()
113 {
114     AuthorName::main();
115     return 0;
116 }

View Code

洛谷 题解 P1351 【联合权值】

Problem

record

Solution

60 or 70 pts

70⇒100 pts

100 pts

Code

洛谷题解 P1351 【联合权值】