震惊，蒟蒻居然也能去省选，短暂回归 OI!
2020/5/15: 震惊，蒟蒻居然能混到决赛三等奖！
友情tips： 点击右侧目录来快速跳转到自己想要的地方
题单
网络流： https://www.luogu.com.cn/training/65946#information
树链剖分： https://www.luogu.com.cn/training/65955#information
树的直径：https://www.luogu.com.cn/training/67339#information
网络流答案：
P3171 吞吐量
跑最短路建图，然后拆点即可
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define ll long long
const ll inf = 1e16;
template <class T>
inline void read(T& a){
T x = 0, s = 1;
char c = getchar();
while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
a = x * s;
return ;
}
struct node{
int v, next;
ll w;
} t[N << 1];
int f[N];
int cur[N];
int bian = -1;
inline void add(int u, int v, ll w){
t[++bian] = (node){v, f[u], w}, f[u] = bian;
t[++bian] = (node){u, f[v], 0}, f[v] = bian;
return ;
}
int n, m;
ll G[1010][1010];
ll dis[N];
ll c[N];
bool vis[N];
void spfa(){
queue <int> q;
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
q.push(1); vis[1] = 1; dis[1] = 1;
while(!q.empty()){
int now = q.front(); q.pop();
vis[now] = 0;
for(int v = 1; v <= n; v++){
if(~G[now][v]){
if(dis[v] > dis[now] + G[now][v]){
dis[v] = dis[now] + G[now][v];
if(!vis[v]) q.push(v), vis[v] = 1;
}
}
}
}
return ;
}
int deth[N];
bool bfs(int S, int T){
queue <int> q;
memset(deth, 0, sizeof(deth));
q.push(S), deth[S] = 1;
while(!q.empty()){
int now = q.front(); q.pop();
for(int i = f[now]; ~i; i = t[i].next){
int v = t[i].v;
if(!deth[v] && t[i].w != 0)
deth[v] = deth[now] + 1, q.push(v);
}
}
return deth[T]; // 能到达汇点
}
ll dfs(int now, int T, ll flow){
if(now == T || !flow) return flow;
for(int& i = cur[now]; ~i; i = t[i].next){
int v = t[i].v;
if(deth[v] == deth[now] + 1 && t[i].w != 0){
ll di = dfs(v, T, min(t[i].w, flow));
if(di > 0){
t[i].w -= di;
t[i^1].w += di;
return di;
}
}
}
return 0;
}
ll Dicnic(int S, int T){
ll sum = 0;
while(bfs(S, T)){
memcpy(cur, f, sizeof(cur));
ll tmp = 0;
while((tmp = dfs(S, T, inf))) sum += tmp;
}
return sum;
}
int main(){
// freopen("hh.txt", "r", stdin);
read(n), read(m);
memset(G, -1, sizeof(G));
for(int i = 1; i <= m; i++){
int x, y; ll w;
read(x), read(y), read(w);
if(G[x][y] == -1) G[x][y] = G[y][x] = w;
else G[x][y] = G[y][x] = min(G[x][y], w);
}
for(int i = 1; i <= n; i++) read(c[i]);
spfa();
memset(f, -1, sizeof(f));
int S = 0, T = n + n + 1;
add(S, 1, inf); add(n << 1, T, inf);
for(int i = 1; i <= n; i++){
if(i != 1 && i != n) add(i, i + n, c[i]);
else add(i, i + n, inf);
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(i != j)
if(dis[i] + G[i][j] == dis[j] && ~G[i][j]) add(i + n, j, inf);
}
}
ll ans = Dicnic(S, T);
cout << ans << endl;
return 0;
}
树链剖分答案：
P3258 松鼠的新家
其实直接树上差分即可，但还是练习一下树剖。
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define ll long long
template <class T>
inline void read(T& a){
T x = 0, s = 1;
char c = getchar();
while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
a = x * s;
return ;
}
struct node{
int v, next;
} t[N << 1];
int f[N];
int bian = 0;
inline void addedge(int u, int v){
t[++bian] = (node){v, f[u]}, f[u] = bian;
return ;
}
int n;
int a[N];
int top[N], fa[N], deth[N], son[N], siz[N];
int dfn[N], id = 0;
#define v t[i].v
void dfs1(int now, int father){
fa[now] = father;
deth[now] = deth[father] + 1;
siz[now] = 1;
for(int i = f[now]; i; i = t[i].next){
if(v != father){
dfs1(v, now);
siz[now] += siz[v];
if(siz[v] > siz[son[now]])
son[now] = v;
}
}
return ;
}
void dfs2(int now, int tp){
top[now] = tp;
dfn[now] = ++id;
if(!son[now]) return ;
dfs2(son[now], tp);
for(int i = f[now]; i; i = t[i].next){
if(v != fa[now] && v != son[now])
dfs2(v, v);
}
return ;
}
#undef v
struct Segment_tree{ /*完整版线段树练习*/
private:
struct node{
int w, add;
} e[N << 2];
#define lson (o<<1)
#define rson (o<<1|1)
inline void pushdown(int o, int l, int r){
int mid = l + r >> 1;
e[lson].add += e[o].add;
e[rson].add += e[o].add;
e[lson].w += (e[o].add * (mid - l + 1));
e[rson].w += (e[o].add * (r - mid));
e[o].add = 0;
return ;
}
inline void pushup(int o){
e[o].w = e[lson].w + e[rson].w;
return ;
}
public:
/*
inline void build(int o, int l, int r){
e[o].w = e[o].add = 0;
if(l == r) return ;
int mid = l + r >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(o);
}
此题中不需要，仅供练习
*/
void update(int o, int l, int r, int in, int end, int k){
if(l > end || r < in) return ;
if(l >= in && r <= end){
e[o].add += k;
e[o].w += (r - l + 1) * k;
return ;
}
pushdown(o, l, r);
int mid = l + r >> 1;
update(lson, l, mid, in, end, k);
update(rson, mid + 1, r, in, end, k);
pushup(o);
return ;
}
int query(int o, int l, int r, int x){
if(l == r && l == x) return e[o].w;
pushdown(o, l, r);
int mid = l + r >> 1;
if(x <= mid) return query(lson, l, mid, x);
else if(x > mid) return query(rson, mid + 1, r, x);
return 0;
}
} tree;
void jia(int x, int y){
while(top[x] != top[y]){
if(deth[top[x]] < deth[top[y]]) swap(x, y);
tree.update(1, 1, n, dfn[top[x]], dfn[x], 1);
x = fa[top[x]];
}
if(deth[x] > deth[y]) swap(x, y);
tree.update(1, 1, n, dfn[x], dfn[y], 1);
return ;
}
int main(){
// freopen("hh.txt", "r", stdin);
read(n);
for(int i = 1; i <= n; i++) read(a[i]);
for(int i = 1; i < n; i++){
int x, y;
read(x), read(y);
addedge(x, y); addedge(y, x);
}
dfs1(1, 0);
dfs2(1, 0);
// tree.build(1, 1, n); 此题中不需要，仅供练习
for(int i = 1; i < n; i++){
jia(a[i], a[i+1]);
tree.update(1, 1, n, dfn[a[i+1]], dfn[a[i+1]], -1); // 注意，a[i+1] 会重复加一，应减掉
}
for(int i = 1; i <= n; i++)
printf("%d
", tree.query(1, 1, n, dfn[i]));
return 0;
}
树的直径答案
CF455C / P2195 HXY造公园
用并查集维护森林编号。然后可以发现，操作一可以 (O(N)) 预处理。操作二，有式子 (ans(new) = max(ans[x], ans[y], [(ans[x] + 1) / 2 + (ans[y] + 1) / 2 + 1]))
/* 2021.4.10 0:25
for both problems:
luogu: P2195 HXY造公园
CF455C: Civilization
*/
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define ll long long
const int inf = -2e9;
template <class T>
inline void read(T& a){
T x = 0, s = 1;
char c = getchar();
while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
a = x * s;
return ;
}
struct node{
int v, next;
} t[N << 1];
int f[N];
int bian = 0;
inline void add(int u, int v){
t[++bian] = (node){v, f[u]}, f[u] = bian;
return ;
}
/* 并查集 */
int ffa[N];
int find(int x){
return x == ffa[x] ? x : ffa[x] = find(ffa[x]);
}
inline void merge(int u, int v){
int fau = find(u), fav = find(v);
ffa[fau] = fav;
return ;
}
/* 并查集 end */
int vis[N];
int dis[N];
int ans[N];
int find_root;
int find_maxn = 0;
int n, m, T;
void dfs(int now, int rt, int dis){
if(vis[now] == rt) return ;
vis[now] = rt;
if(dis > find_maxn){
find_root = now;
find_maxn = dis;
}
if(now != rt) merge(now, rt);
for(int i = f[now]; i; i = t[i].next){
int v = t[i].v;
dfs(v, rt, dis + 1);
}
return ;
}
void get_root(){ // 寻找每棵树的直径
for(int i = 1; i <= n; i++)
ffa[i] = i; // 并查集初始化
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++){
if(!vis[i]){
find_root = i;
find_maxn = 0;
dfs(i, i, 0);
find_maxn = 0;
dfs(find_root, find_root, 0);
ans[find(i)] = find_maxn;
}
}
return ;
}
int main(){
read(n), read(m), read(T);
for(int i = 1; i <= m; i++){
int x, y;
read(x), read(y);
add(x, y); add(y, x);
}
get_root(); // 找到每棵树的直径并记录
while(T--){
int opt = 0, x = 0, y = 0;
read(opt);
switch (opt){
case 1:
read(x);
printf("%d
", ans[find(ffa[x])]);
break;
case 2:
read(x), read(y);
x = find(x), y = find(y);
if(x == y) break ;
merge(x, y);
ans[find(x)] = max(ans[x], max(ans[y], (ans[x] + 1) / 2 + (ans[y] + 1) / 2 + 1));
break ;
}
}
return 0;
}