2020-hdu多校-2
ACM
1541字
6763 1001 并查集
题目出锅了 虽然开局一堆人A的飞快，但是应该都是假算法？主要是出题人给的题解是假的
如果从每次都尽可能删除极大联通块的策略来考虑，那么可以用并查集维护信息。显然在一个极大联通块中可以将每个节点删去所有权值中的最小值，之后该点断裂，将原联通块分成若干个小联通块，反复进行上述操作即可。我们用并查集反向维护这个过程：将所有节点按照权值从大到小进行遍历，如果当前点$u$连有边$<u,v>$并且有$w[v] > w[u]$，那么就在并查集中连$<root[v]->u>$ 。这样， 我们最终就会得到一颗有根树，其上节点的父子关系也给出了删去权值的方案。最终只需要用w[x] - w[par[x]]去更新答案即可。
因为使用路径压缩的并查集，所以要额外存一个数组，表示真正的拓扑结构上的父节点，用于最后更新答案。
1const int maxn = 1e5 + 10;
2
3struct star{int to, next;};
4int n, m, head[maxn], top = 0;
5int w[maxn];
6star edge[maxn << 2];
7
8void add(int u, int v){
9 edge[top].to = v;
10 edge[top].next = head[u];
11 head[u] = top++;
12}
13
14bool cmp(int a, int b){return w[a] > w[b];}
15int id[maxn], vis[maxn];;
16
17int par[maxn], f[maxn];
18int find(int x){return x == par[x]? x: par[x] = find(par[x]);}
19
20int main(){
21// Fastin;
22 int t; scanf("%d", &t); while(t--){
23 clr(head, -1); top = 0; clr(vis, 0);
24 scanf("%d %d", &n, &m);
25 for(int i = 1; i <= n; i++){
26 scanf("%d", w + i);
27 id[i] = i; par[i] = i; f[i] = 0;
28 }
29 for(int i = 0; i < m; i++){
30 int u, v; scanf("%d %d", &u, &v); add(u, v); add(v, u);
31 }
32 sort(id + 1, id + n + 1, cmp);
33 for(int i = 1; i <= n; i++){
34 vis[id[i]] = 1;
35 for(int j = head[id[i]]; ~j; j = edge[j].next){
36 int to = edge[j].to; if(vis[to]){
37 int r = find(to);
38 if(r != id[i]) par[r] = f[r] = id[i];
39 }
40 }
41 }
42 ll ans = 0;
43 for(int i = 1; i <= n; i++) ans += w[i] - w[f[i]];
44 printf("%lld\n", ans);
45 }
46 return 0;
47}1012
1
2const int maxn = 1e5 + 10;
3const int inf = 1e9;
4int n, m;
5char s[maxn], t[30];
6
7int nxt[maxn][26], temp[26];
8int dp[30][30];
9
10int main(){
11// Fastin;
12 int __; scanf("%d", &__); while(__--){
13 scanf("%s %s", s + 1, t + 1); n = (int)strlen(s + 1); m = (int)strlen(t + 1);
14
15 for(int i = 0; i < 26; i++) temp[i] = inf;
16 for(int i = n; i >= 0; i--){
17 for(int j = 0; j < 26; j++) nxt[i][j] = temp[j];
18 if(i) temp[s[i] - 'a'] = i;
19 }
20 int q; scanf("%d", &q); for(int i = 0; i < q; i++){
21 int l, r; scanf("%d %d", &l, &r);
22 //dp[i][j]表示处理t串的第i位后，已经有lcs长为j时，s串中最短的前缀位置
23 dp[1][0] = l - 1; dp[1][1] = s[l] == t[1]? l: nxt[l][t[1] - 'a'];
24 for(int i = 2; i <= m; i++) dp[1][i] = inf;
25
26 for(int i = 2; i <= m; i++){
27 for(int j = 1; j <= i; j++){
28 dp[i][0] = dp[i - 1][0]; dp[i][j] = dp[i - 1][j];
29 if(dp[i - 1][j - 1] <= r && nxt[dp[i - 1][j - 1]][t[i] - 'a'] <= r)
30 dp[i][j] = min(dp[i][j], nxt[dp[i - 1][j - 1]][t[i] - 'a']);
31 }
32 for(int j = i + 1; j <= m; j++) dp[i][j] = inf;
33 }
34
35 int lcs = 0;
36 for(int i = 1; i <= m; i++) if(dp[m][i] <= r) lcs = i;
37
38 printf("%d\n", r - l + 1 + m - 2 * lcs);
39 }
40 }
41 return 0;
42}
43
1#include <iostream>
2
3#include <algorithm>
4#include <string>
5#include <vector>
6#include <stack>
7#include <queue>
8#include <set>
9#include <map>
10#include <unordered_map>
11#include <unordered_set>
12#include <random>
13#include <chrono>
14
15#include <cstdio>
16#include <cstring>
17#include <cmath>
18#include <ctime>
19#include <cstdlib>
20#include <cassert>
21
22#define itn int
23#define fro for
24#define scnaf scanf
25#define sacnf scanf
26#define Fastin freopen("in.txt", "r", stdin)
27#define Fastout freopen("out.txt", "w", stdout)
28#define manx maxn
29#define lowbit(x) ((x) & (-x))
30#define ceil(n, p) (((n) +(p) - 1) / (p))
31#define DBG(x) (void)(cout << "L" << __LINE__ << ": " << #x << " = " <<( x) << '\n')
32#define clr(a, x) memset((a), x, sizeof (a))
33#define min(a, b) ((a) < (b)? (a): (b))
34#define max(a, b) ((a) > (b)? (a): (b))
35
36using namespace std;
37typedef long long ll;
38
39int read(){
40 int ng=0,x=0;
41 char ch=getchar();
42 for(;ch<'0' || ch>'9';ch=getchar()) ng|=ch=='-';
43 for(;ch>='0' && ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
44 return ng?-x:x;
45}
46/*------------------------------------------------------------------------------------*/
47ll gcd(ll x, ll y){return !x? y: gcd(y % x, x);}
48void exgcd(ll a, ll b, ll &x, ll &y){
49 if(!b){x = 1; y = 0;return;}
50 exgcd(b, a % b, y, x); y -= a / b * x;
51}
52ll qp(ll a, ll p){
53 if(p < 0) return 0;
54 ll ans = 1; while(p){if(p & 1) ans = ans * a ; a = a * a; p >>= 1;}
55 return ans;
56}
57ll qp(ll a, ll p, ll M){
58 ll ans = 1; while(p){ if(p & 1) ans = ans * a % M; a = a * a % M; p >>= 1;}
59 return ans;
60}
61/*------------------------------------------------------------------------------------*/
62
63const int manx = 2e4 + 10;
64
65struct star{int to, next, a, b;};
66int n, k;
67int head[maxn], top = 0;
68star edge[maxn << 1];
69void add(int u, int v, int a, int b){
70 edge[top].to = v;
71 edge[top].next = head[u];
72 edge[top].a = a; edge[top].b = b;
73 head[u] = top++;
74}
75
76
77//检验树直径<=x 的可能性
78ll dp[maxn][25], middle, h[25], size[maxn];
79void dfs(int now, int par){
80 int pre = 0; dp[now][0] = 0;
81 for(int id = head[now]; ~id; id = edge[id].next){
82 int to = edge[id].to; if(to == par) continue;
83
84 dfs(to, now);
85 for(int i = 0; i <= k && i <= pre + size[to]; i++) h[i] = middle + 1;
86 for(int i = 0; i <= pre; i++) for(int j = 0; j < size[to] && j + i <= k; j++){
87 if(dp[now][i] + dp[to][j] + edge[id].a <= middle)
88 h[i + j + 1] = min(h[i + j + 1], max(dp[now][i], dp[to][j] + edge[id].a));
89 if(dp[now][i] + dp[to][j] + edge[id].b <= middle)
90 h[i + j] = min(h[i + j], max(dp[now][i], dp[to][j] + edge[id].b));
91 }
92
93 for(int i = 0; i <= pre + size[to]; i++) dp[now][i] = h[i];
94 pre += size[to];
95 }
96 size[now] = pre + 1;
97}
98
99
100
101int main(){
102// Fastin;
103 int _; scanf("%d", &_); while(_--){
104 top = 0;
105
106 scanf("%d %d", &n, &k); for(int i = 0; i < 2 * n; i++) head[i] = -1;
107 ll M =0 ;
108 for(int i = 0; i < n - 1; i++){
109 int u, v, a, b;
110 scanf("%d %d %d %d", &u, &v, &a, &b);
111 add(u, v, a, b);
112 add(v, u, a, b);
113 M += max(a, b);
114 }
115 ll left = 1, right = M;
116 while(left < right){
117 middle = (left + right) >> 1;
118 dfs(1, 0);
119 if(dp[1][k] <= middle) right = middle;
120 else left = middle + 1;
121 }
122 printf("%lld\n", left);
123 }
124 return 0;
125}