- 2022tysc0306 的博客
【模版】
-
2022tysc0306
LV 10
@
2024-8-12 11:59:46
【模版】
算法
差分
差分
#include <iostream>
#include <map>
#define int long long
using namespace std;
int n;
int a[1000005];
map<int, int> mp;
signed main()
{
cin >> n;
for(int i = 1; i <= n; i++){
int x, y;
cin >> x >> y;
mp[x]++, mp[y + 1]--;
}
int last = -1, x = 0;
for(map<int, int>::iterator it = mp.begin(); it != mp.end(); it++){
if(last != -1){
int now = it -> first;
a[x] += now - last;
}
last = it -> first;
x += it -> second;
}
for(int i = 1; i <= n; i++) cout << a[i] << " ";
return 0;
}
深搜
inline bool check(int x, int y)
{
if(x > n || y > m || x < 1 || y < 1) return 0;
if(vis[x][y]) return 0;
return 1;
}
inline void dfs(int x, int y, int ans)
{
if(x == n && y == m){
maxn = max(ans, maxn);
return;
}
vis[x][y] = 1;
for(int i = 0; i < 3; i++){
int nx = dx[i] + x;
int ny = dy[i] + y;
if(check(nx, ny)){
dfs(nx, ny, ans + a[nx][ny]);
vis[nx][ny] = 0;
}
}
}
数论
【模版】快速幂
快速幂
#include <iostream>//cin cout
using namespace std;//命名空间
long long n, m, k;
long long ksm(long long n, long long m, long long k)
{
long long ans = 1;
while(m){
if(m & 1) ans = ((ans % k) * (n % k)) % k;//同余定理
n = ((n % k) * (n % k)) % k;
m >>= 1;
}
return ans;
}
int main()//主函数
{
cin >> n >> m >> k;
cout << ksm(n, m, k);
return 0;//华丽结束
}
动态规划
【模版】最长不下降子序列(LIS)
最长不下降子序列
#include <iostream>//cin cout
#include <algorithm>//upper_bound
#include <cstring>//memset
using namespace std;//命名空间
int a[5005], dp[5005];
int main()//主函数
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
memset(dp, 0x3f3f3f3f, sizeof(dp));
int maxn = dp[1];
for(int i = 1; i <= n; i++){
a[i] = *upper_bound(dp + 1, dp + n + 1, a[i]);
}
int ans = 0;
while(dp[ans + 1] != maxn) ans++;
cout << ans;
return 0;//华丽结束
}
【模版】换根dp
换根
#include <iostream>
#include <vector>
#define int long long
using namespace std;
const int N = 1e6 + 5;
vector<int> g[N];
int sz[N], f[N], dep[N], n;
inline void dfs(int u, int fa)
{
sz[u] = 1;//记录大小
dep[u] = dep[fa] + 1;//记录深度
for(int i = 0; i < g[u].size(); i++){
int v = g[u][i];
if(v == fa) continue;
dfs(v, u);//往下深搜
sz[u] += sz[v];//加上儿子的大小
}
inline void dp(int u, int fa)
{
for(int i = 0; i < g[u].size(); i++){
int v = g[u][i];
if(v == fa) continue;
f[v] = f[u] - sz[v] * 2 + n;//dp
dp(v, u);//继续往下dp
}
}
signed main()
{
cin >> n;
for(int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 1);
for(int i = 1; i <= n; i++) f[1] += dep[i];
dp(1, 1);
int ans = -1;
int id;
for(int i = 1; i <= n; i++){//统计答案
if(f[i] > ans){//如果大于ans，就记录
ans = f[i];
id = i;//编号
}
}
cout << id;//输出
return 0;//华丽结束
}
【模版】st表
表
#include <iostream>//cin cout
#include <cmath>
using namespace std;//命名空间
int x, y;
const int N = 100005;
int a[N];
int st[N][35], log1[N];
inline int query(int x, int y)
{
int k = log1[y - x + 1];
return max(st[x][k], st[y - (1 << k) + 1][k]);
}
int main()//主函数
{
int n, m;
scanf("%d%d", &n, &m);
log1[0] = -1;
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
st[i][0] = a[i];
log1[i] = log1[i >> 1] + 1;
}
for(int j = 1; j <= log1[n]; j++){
for(int i = 1; i + (1 << j) - 1 <= n; i++){
st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
}
for(int i = 1; i <= m; i++){
scanf("%d%d", &x, &y);
printf("%d\n", query(x, y));
}
return 0;//华丽结束
}
数据结构
【模版】单链表
单链表
#include <bits/stdc++.h>
using namespace std;
struct node{
int data;//存储数据
node *next;//存下一个数据点的地址
};
node *p, *head = NULL;
inline void create_list()//构建单链表
{
int n, x;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> x;
p = new node;//申请新的空间
p -> data = x;//将 x 封装成 node 节点
//反向插入写法，从头部插入
p -> next = head;//next 指向此时 head 所指向的地址
head = p;//将 head 指向自己
}
}
inline void print_list()
{
p = head;
while(p != NULL){
cout << p -> data << " ";
p = p -> next;//让 p 跳到下一个节点
}
cout << "\n";
}
inline void insert_list(int k, int x)//在第 k 个节点插入 x
{
p = new node;
p -> data = x;
if(k == 1){//头部插入
p -> next = head;//next 指向此时 head 指向的节点，即目前第一个节点
head = p;//head 指向自己，称谓新的首节点
}
else{//非头部插入
int i = 1;
node *q = head;
while(i < k - 1){//找到第 k-1 个节点
q = q -> next;
i++;
}
p -> next = q -> next;
//q 为第 k-1 个节点，它的 next 指向此时第 k 个节点，将此值赋予 p 的 next 后，p 将成为新的第 k 个节点
q -> next = p;;//第 k-1 个节点的 next 指向 p，即指向了新的第 k 个节点
}
}
inline void delete_list(int k)
{
if(k == 1){//头部删除
p = head;
head = p -> next;
delete p;
}
else{
int i = 1;
p = head;
while(i < k - 1){//p 为第 k - 1 个节点
p = p -> next;
i++;
}
node *q = p -> next;//q 为待删除的第 k 个节点
p -> next = q -> next;//p 指向第 k + 1 节点
delete q;
}
}
int main()
{
return 0;
}
【模版】单调栈
单调栈
#include <iostream>
using namespace std;
const int N = 3e6 + 5;
int h[N], res[N];
struct stack{//手写栈
int a[N];
int t = 0;
inline void push(int x){a[++t] = x;}
inline int top(){return a[t];}
inline void pop(){t--;}
inline int empty(){return t == 0 ? 1 : 0;}
}st;
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> h[i];
for(int i = n; i >= 1; i--){
while(!st.empty() && h[st.top()] <= h[i]) st.pop();
st.empty() ? res[i] = 0 : res[i] = st.top();
st.push(i);
}
for(int i = 1; i <= n; i++) cout << res[i] << " ";
return 0;
}
图论
【模版】最短路
最短路
dijkstra
O(n^2)
#include <bits/stdc++.h>
using namespace std;
struct edge{
int v, w;
};
vector<edge> g[10005];
int d[10005], vis[10005];
void dijkstra(int st)
{
memset(d, 127, sizeof(d));
d[st] = 0;//从起点出发
for(int i = 1; i <= n; i++){
int t = d[0], k;
for(int j = 1; j <= n; j++){
if(!vis[j] && d[j] < t){
t = d[j];
k = j;
}
}
for(int j = 0; j < g[k].size(); j++){
int val = g[k][j].v;
int wal = g[k][j].w;
if(d[val] > d[k] + wal) d[val] = d[k] + wal;
}
vis[k] = 1;
}
}
int main()
{
return 0;
}
O(nlogn)
#include <iostream>
#include <queue>
#include <cstring>
#define int long long
using namespace std;
int n, m, st;
struct poi{
int v, w;
bool operator < (poi x) const{
return w > x.w;
}
};
const int N = 2e5 + 5;
int d[N], vis[N];
vector<poi> g[N];
priority_queue<poi> q;
void dijkstra(int st)
{
memset(d, 0x3f, sizeof(d));
d[st] = 0;
q.push({st, 0});
while(!q.empty()){
int u = q.top().v;
q.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int i = 0; i < g[u].size(); i++){
int v = g[u][i].v, w = g[u][i].w;
if(d[u] + w < d[v]){
d[v] = d[u] + w;
q.push({v, d[v]});
}
}
}
}
signed main()
{
cin >> n >> m >> st;
for(int i = 1; i <= m; i++){
int u, v, w;
cin >> u >> v >> w;
g[u].push_back((poi){v, w});
}
dijkstra(st);
for(int i = 1; i <= n; i++) cout << d[i] << " ";
return 0;
}
spfa
#include <bits/stdc++.h>
using namespace std;
struct poi{
int v, w;
};
int n, m, s;
queue<int> q;
bool vis[100005];
long long d[100005];
long long cnt[100005];
vector<poi> g[100005];
void spfa(int st)
{
memset(d, 127, sizeof(d));
memset(vis, 0, sizeof(vis));
d[st] = 0;
vis[st] = 1;
q.push(st);
while(!q.empty()){
int k = q.front();
q.pop();
vis[k] = 0;
for(int i = 0; i < g[k].size(); i++){
int v = g[k][i].v;
int w = g[k][i].w;
if(d[k] + w < d[v]){
d[v] = d[k] + w;
if(!vis[v]){
vis[v] = 1;
q.push(v);
cnt[v]++;
if(cnt[k] > n) cout << -1, exit(0);//负环
}
}
}
}
}
int main()
{
cin >> n >> m >> s;
for(int i = 1; i <= m; i++){
int a, b, c;
cin >> a >> b >> c;
g[a].push_back((poi){b, c});
}
spfa(s);
cout << d[n];
return 0;
}
floyd
void floyd()
{
memset(f, 127, sizeof(f));
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
f[i][i] = 0;
for(int j = 1; j <= n; j++){
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
}
}
}
【模版】最小生成树
kruskal
#include <bits/stdc++.h>//万能头文件
using namespace std;//命名空间
int fa[1000001];
int n, m, res, cnt;
struct poi{
int x, y, z;
}g[1000001];
bool cmp(poi a, poi b)
{
return a.z < b.z;
}
int find(int x)//并查集
{
if(x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
int main()//主函数
{
cin >> n >> m;
for(int i = 1; i <= m; i++) cin >> g[i].x >> g[i].y >> g[i].z;
stable_sort(g + 1, g + m + 1, cmp);//排序
for(int i = 1; i <= n; i++) fa[i] = i;//并查集初始化
for(int i = 1; i <= m; i++){
int x = find(g[i].x);//并查集
int y = find(g[i].y);//并查集
if(x == y) continue;//若出现两个点已经联通了，那么这一条边就不需要了
fa[x] = y;//将y、x合并
res += g[i].z;//将边权计入答案
cnt++;//边数++
}
if(cnt == n - 1) cout << res;
else cout << "No MST";//没有最小生成树
return 0;//华丽结束
}
prim
#include <bits/stdc++.h>//万能头文件
using namespace std;//命名空间
bool vis[1001];
int n, m, res;
int a[1001][1001], d[1001];
void prim()
{
memset(d, 0x3f, sizeof(d));
memset(vis, 0, sizeof(vis));
d[1] = 0;
for(int i = 1; i <= n; i++){
int x = 0;
for(int j = 1; j <= n; j++){
if(!vis[j] && d[j] < d[x]) x = j;
}
vis[x] = 1;
for(int j = 1; j <= n; j++){
if(!vis[j]) d[j] = min(d[j], a[x][j]);
}
}
}
int main()//主函数
{
memset(a, 0x3f, sizeof(a));
cin >> n >> m;
for(int i = 1; i <= n; i++) a[i][i] = 0;
for(int i = 1; i <= m; i++){
int x, y, z;
cin >> x >> y >> z;
a[x][y] = a[y][x] = min(a[x][y], z);
}
prim();
for(int i = 2; i <= n; i++) res += d[i];
cout << res;
return 0;//华丽结束
}
【模版】树状数组
树状数组
基础操作
#include <bits/stdc++.h>
using namespace std;
int n, m, l, r;
int a[100005], c[100005];
int lowbit(int x)
{
return x & (-x);
}
int ask(int x)//区间[1,x]的前缀和
{
int ans = 0;
while(x > 0){
ans += c[x];
x -= lowbit(x);
}
return ans;
}
void add(int x, int d)//树状数组添加
{
while(x <= n){
c[x] += d;
x += lowbit(x);
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) add(i, a[i]);
cin >> m;
for(int i = 1; i <= m; i++){
cin >> l >> r;
cout << ask(r) - ask(l - 1) << "\n";
}
return 0;
}
离散化
离散化
所谓离散化就是指对序列中的数值按数值大小重新标号，最小值标为 ，最大值标为 。
步骤：
①先建立一个备用数组 ;
②对数组 排序；
③对数组 去重；
④将原数值 放到 中二分查找，得到自己的顺序号，将顺序号更新为自己的新数值。
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i], t[i] = a[i];
sort(t + 1, t + n + 1);//排序
int len = unique(t + 1, t + n + 1) - t - 1;//去重
for(int i = 1; i <= n; i++){
a[i] = lower_bound(t + 1, t + len + 1, a[i]) - t;//将原数重新标号
}
return 0;
}
逆序对
逆序对
#include <bits/stdc++.h>
using namespace std;
int n, m, l, r;
long long ans = 0;
int a[100005], c[100005];
int lowbit(int x)
{
return x & (-x);
}
int ask(int x)//区间[1,x]的前缀和
{
int ans = 0;
while(x > 0){
ans += c[x];
x -= lowbit(x);
}
return ans;
}
void add(int x, int d)//树状数组添加
{
while(x <= n){
c[x] += d;
x += lowbit(x);
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = n; i >= 1; i--){
ans += ask(a[i] - 1);//求出序列后方比a[i]小的数量
add(a[i], 1);//将数字加入树状数组
}
cout << ans;
return 0;
}
用离散化优化：
#include <bits/stdc++.h>
using namespace std;
int n, m, l, r;
long long ans = 0;
int a[100005], c[100005], t[100005];
int lowbit(int x)
{
return x & (-x);
}
int ask(int x)//区间[1,x]的前缀和
{
int ans = 0;
while(x > 0){
ans += c[x];
x -= lowbit(x);
}
return ans;
}
void add(int x, int d)//树状数组添加
{
while(x <= n){
c[x] += d;
x += lowbit(x);
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i], t[i] = a[i];
//离散化
sort(t + 1, t + n + 1);//排序
int len = unique(t + 1, t + n + 1) - t - 1;//去重
for(int i = 1; i <= n; i++){
a[i] = lower_bound(t + 1, t + len + 1, a[i]) - t;//将原数重新标号
}
for(int i = n; i >= 1; i--){
ans += ask(a[i] - 1);//求出序列后方比a[i]小的数量
add(a[i], 1);//将数字加入树状数组
}
cout << ans;
return 0;
}
【模版】线段树
线段树
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int n, m, p, x, y, a[N], sum[4 * N];
inline void pushup(int rt)
{
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
inline void build(int l, int r, int rt)//建树
{
if(l == r){ sum[rt] = a[l]; return;}
int mid = (l + r) >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
pushup(rt);
}
inline void update(int l, int r, int rt, int x, int d)//单点修改
{
if(l == r){ sum[rt] = d; return;}
int mid = (l + r) >> 1;
if(x <= mid) update(l, mid, rt << 1, x, d);
else update(mid + 1, r, rt << 1 | 1, x, d);
pushup(rt);
}
inline int query(int l, int r, int rt, int x, int y)//区间查询
{
if(x <= l && r <= y) return sum[rt];//区间[l,r]包含[x,y]
int mid = (l + r) >> 1;
int res = 0;
if(x <= mid) res += query(l, mid, rt << 1, x, y);
if(y > mid) res += query(mid + 1, r, rt << 1 | 1, x, y);
return res;
}
int main()
{
int m, n;
cin >> m >> n;
memset(a, 127, sizeof(a));
for(int i = 1; i <= m; i++) cin >> a[i];
build(1, m, 1);//建树
for(int i = 1; i <= n; i++){
cin >> p >> x >> y;
if(p == 1) cout << query(1, m, 1, x, y) << " ";
else update(1, m, 1, x, y);
}
return 0;
}
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 1e5;
int n, m, q, l, r, x;
int a[N], add[N], sum[4 * N];
void pushup(int rt)
{
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void pushdown(int rt, int l, int r)
{
if(add[rt] == 0) return;
add[rt << 1] += add[rt];
add[rt << 1 | 1] += add[rt];
sum[rt << 1] += add[rt] * l;
sum[rt << 1 | 1] += add[rt] * r;
add[rt] = 0;
}
void build(int l, int r, int rt)//建树
{
if(l == r){ sum[rt] = a[l]; return;}
int mid = (l + r) >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
pushup(rt);
}
void update(int l, int r, int rt, int x, int d)//单点修改
{
if(l == r){ sum[rt] = d; return;}
int mid = (l + r) >> 1;
if(x <= mid) update(l, mid, rt << 1, x, d);
else update(mid + 1, r, rt << 1 | 1, x, d);
pushup(rt);
}
void modify(int x, int y, int d, int l, int r, int rt)//区间修改[x,y]+d
{
if(x <= l && y >= r){
sum[rt] += d * (r - l + 1);//当前的[l,r]都在[x,y]范围内
add[rt] += d;//标记
return;
}
int mid = (l + r) >> 1;
pushdown(rt, mid - l + 1, r - mid);
if(x <= mid) modify(x, y, d, l, mid, rt << 1);
if(y > mid) modify(x, y, d, mid + 1, r, rt << 1 | 1);
pushup(rt);
}
int query(int l, int r, int rt, int x, int y)//区间查询
{
if(x > r || y < l) return 0;
if(x <= l && r <= y) return sum[rt];//区间[x,y]包含[l,r]
int mid = (l + r) >> 1;
pushdown(rt, mid - l + 1, r - mid);
int ans = 0;
if(x <= mid) ans += query(l, mid, rt << 1, x, y);
if(y > mid) ans += query(mid + 1, r, rt << 1 | 1, x, y);
return ans;
}
signed main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
build(1, n, 1);//建树
for(int i = 1; i <= m; i++){
cin >> q >> l >> r;
if(q == 1){
cin >> x;
modify(l, r, x, 1, n, 1);
}
else cout << query(1, n, 1, l, r) << "\n";
}
return 0;
}
权值线段树
【模板】
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7;
int n, m, q, l, r, x;
int a[N], sum[4 * N];
void pushup(int rt)
{
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void build(int l, int r, int rt)//建树
{
if(l == r){ sum[rt] = 0; return;}
int mid = (l + r) >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
pushup(rt);
}
void update(int l, int r, int rt, int x, int d)//单点修改
{
if(l == r){ sum[rt] = d; return;}
int mid = (l + r) >> 1;
if(x <= mid) update(l, mid, rt << 1, x, d);
else update(mid + 1, r, rt << 1 | 1, x, d);
pushup(rt);
}
int query(int l, int r, int rt, int x, int y)//区间查询
{
if(x > r || y < l) return 0;
if(x <= l && r <= y) return sum[rt];//区间[x,y]包含[l,r]
int mid = (l + r) >> 1;
int ans = 0;
if(x <= mid) ans += query(l, mid, rt << 1, x, y);
if(y > mid) ans += query(mid + 1, r, rt << 1 | 1, x, y);
return ans;
}
int kth(int l, int r, int rt, int k)//求第k小的数
{
if(l == r) return r;//到达叶子结点
int mid = (l + r) >> 1;
int lsum = sum[rt << 1];
if(k <= lsum) return kth(l, mid, rt << 1, k);
return kth(mid + 1, r, rt << 1 | 1, k - lsum);
}
int pre(int x)//查找前驱
{
int k = query(1, N, 1, 1, x - 1);
if(!k) return -1;//它是最小值，无前驱
return kth(1, N, 1, k);
}
int next(int x, int mx)
{
int k = query(1, N, 1, 1, x - 1) + 1;
if(!(k ^ mx)) return -1;//它是最大值，无前驱
return kth(1, N, 1, k);
}
int main()
{
return 0;
}
动态开点
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7;
struct node{
int lson, rson, sum;
}T[N * 3];
int n, opt, x, cnt = 1, root = 1;
void update(int rt, int l, int r, int k, int v)//更新数值
{
if(l == r){
T[rt].sum += v;
return;
}
int mid = (l + r) >> 1;
if(k <= mid){
if(!T[rt].lson) T[rt].lson = ++cnt;
update(T[rt].lson, l, mid, k, v);
}
else{
if(!T[rt].rson) T[rt].rson = ++cnt;
update(T[rt].rson, mid + 1, r, k, v);
}
T[rt].sum = T[T[rt].lson].sum + T[T[rt].rson].sum;//类似pushup
}
int query(int l, int r, int rt, int x, int y)//区间求和
{
if(rt == 0)return 0;
if(x <= l && r <= y) return T[rt].sum;
int s = 0;
int mid = (l + r) >> 1;
if(x <= mid) s += query(T[rt].lson, l, mid, x, y);
if(y > mid) s += query(T[rt].rson, mid + 1, r, x, y);
return s;
}
int kth(int rt, int l, int r, int k)//找第K个数
{
if(l == r) return r;
int mid = (l + r) >> 1;
int lson = T[rt].lson;
int rson = T[rt].rson;
if(T[lson].sum >= k)return kth(lson, l, mid, k);//左子树总数量>=k，那么第k个肯定在左子树
return kth(rson, mid + 1, r, k - T[lson].sum);//第k个在右子树，递归右子树，注意k值的变化
}
int main()
{
return 0;
}
【模板】树的重心与直径
重心
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 1e6 + 5;
vector<int> g[N];
int d[N], a[N], ans = 1e9, num;
inline void dfs(int u, int fa)
{
d[u] = 1;
int max_part = 0;
for(int i = 0; i < g[u].size(); i++){//求出节点数量
int v = g[u][i];//枚举儿子节点
if(v == fa) continue;
dfs(v, u);
d[u] += d[v];//加上儿子节点数量
max_part = max(max_part, d[v]);
}
max_part = max(max_part, n - d[u]);//比较除了u以外的连通块
if(max_part < ans){//如果更优
ans = max_part;//记录
num = 0;//更新
a[++num] = u;//记录
}
else if(max_part == ans) a[++num] = u;//记录
}
int main()
{
cin >> n;
for(int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
//建树
}
dfs(1, 0);
sort(a + 1, a + num + 1);//排序
cout << num << "\n";//重心个数
for(int i = 1; i <= num; i++) cout << a[i] << " ";
return 0;
}
直径
直径
权值树
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 1e6 + 5;
struct poi{
int v, w;
};
int d[N];
vector<poi> g[N];
inline void dfs(int u, int fa, int len)
{
d[u] = len;
for(int i = 0; i < g[u].size(); i++){
int v = g[u][i].v, w = g[u][i].w;
if(v == fa) continue;
dfs(v, u, len + w);
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i++){//建树
int u, v, w;
cin >> u >> v >> w;
g[u].push_back((poi){v, w});
g[v].push_back((poi){u, w});
}
dfs(1, -1, 0);//求最远距离
int s = 1;
for(int i = 2; i <= n; i++){
if(d[i] > d[s]) s = i;//求直径的一个端点
}
dfs(s, -1, 0);//求最远距离
int t = s;
for(int i = 1; i <= n; i++){
if(d[i] > d[t]) t = i;//求直径的另一个端点
}
cout << d[t];//输出直径
return 0;
}
无权树
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 1e6 + 5;
int d[N];
vector<int> g[N];
inline void dfs(int u, int fa, int len)
{
d[u] = len;
for(int i = 0; i < g[u].size(); i++){
int v = g[u][i];
if(v == fa) continue;
dfs(v, u, len + 1);
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i++){//建树
int u, v, w;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, -1, 0);//求最远距离
int s = 1;
for(int i = 2; i <= n; i++){
if(d[i] > d[s]) s = i;//求直径的一个端点
}
dfs(s, -1, 0);//求最远距离
int t = s;
for(int i = 1; i <= n; i++){
if(d[i] > d[t]) t = i;//求直径的另一个端点
}
cout << d[t];//输出直径
return 0;
}
【模版】树的独立集和支配集
独立集
独立集
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
int n, d[N], dp[N][2];
vector<int> g[N];
inline void dfs(int u, int fa)
{
dp[u][0] = 0;
dp[u][1] = 1;//选点u
for(int i = 0; i < g[u].size(); i++){
int v = g[u][i];
if(v == fa) continue;
dfs(v, u);
dp[u][0] += max(dp[v][0], dp[v][1]);//不选点u，子节点可选可不选
dp[u][1] += dp[v][0];//选点u，那么子节点不能再选了
}
}
int main()
{
cin >> n;
for(int i = 1; i < n; i++){
int a, b;
cin >> a >> b;
g[b].push_back(a);
g[a].push_back(b);
}
dfs(1, -1);//从节点1开始dfs，1相当于根节点
cout << max(dp[1][1], dp[1][0]) << "\n";
return 0;
}
支配集
支配集
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
const int N = 1e5, inf = 99999999;
int dp[N][3], a[N];
vector<int> g[N];
inline void dfs(int u, int fa)//模板
{
dp[u][2] = 0;//定义为不要点u加入支配集，点u为根的子树所有节点都被覆盖，但是点u不被任何一个子节点覆盖的情况下，支配集最少节点的个数
dp[u][1] = 1;//定义为选择点u加入支配集，并且点u为根的子树所有节点都被覆盖了的情况下，支配集中包含最少的节点个数
dp[u][0] = inf;//定义为不要点u加入支配集，点u为根的子树所有节点都被覆盖，并且点u被至少一个子节点覆盖的情况下，支配集最少节点个数
int sum = 0, ans = inf;
bool flag = 0;
for(int i = 0; i < (int)g[u].size(); i++){
int v = g[u][i];
if(v == fa) continue;
dfs(v, u);
dp[u][1] += min(dp[v][1], min(dp[v][0], dp[v][2]));//点u被选，和子节点无关，累加子节点的三种情况的最小值，随便选
sum += min(dp[v][1], dp[v][0]);//累计子节点中已经被覆盖的情况，为dp[u][0]做准备
dp[u][0] = sum;
if(dp[v][0] >= dp[v][1]) flag = 1;//表示存在一个子节点已经被选择，可以通过他覆盖节点u
if(dp[v][0] < dp[v][1]) ans = min(ans, dp[v][1] - dp[v][0]);//保存dp[v][1]和dp[v][0]的差值最小值
dp[u][2] += dp[v][0]; //为了得到最小值，我们把差值最小的从dp[v][0]替换为dp[v][1]，强行选择这个子节点，这样点u就可以满足覆盖条件
}
if(!flag && ans != inf) dp[u][0] += ans;
}
signed main()
{
cin >> n;
for(int i = 1; i <= n; i++){
int id, k, m;
cin >> id >> k >> m;
a[id] = k;
for(int j = 1; j <= m; j++){
int r;
cin >> r;
g[id].push_back(r);
g[r].push_back(id);
}
}
dfs(1, -1);
cout << min(dp[1][1], dp[1][0]);
return 0;
}
【模版】图的强连通分量
#include <iostream>
#include <vector>
using namespace std;
const int N = 5e5 + 5;
int vis[N], st[N];//st模拟栈，vis记录是否入栈
int scc[N], sz[N], sc;//sc记录所在SCC的编号，scc记录在第几个SCC，sz记录大小
int dfn[N], low[N];//dfn记录遍历次序，low记录祖先
vector<int> g[N];
int n, m, dfncnt, top;
inline void tarjan(int u)
{
dfn[u] = low[u] = ++dfncnt;
st[++top] = u;//入栈
vis[u] = 1;
for(int i = 0; i < g[u].size(); i++){
int v = g[u][i];
if(!dfn[v]){//如果没被访问
tarjan(v);//继续往下搜索
low[u] = min(low[u], low[v]);
}
else if(vis[v]){
low[u] = min(low[u], dfn[v]);
}
}
if(dfn[u] == low[u]){
sc++;//记录编号
while(s[top] != u){//栈顶不等于u
scc[s[top]] = sc;//记录SCC
sz[sc]++;//第sc个SCC大小++
st[s[top]] = 0;//出栈
top--;//出栈
}
//将u记录到SCC中
scc[s[top]] = sc;
sz[sc]++;
st[s[top]] = 0;
top--;
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
g[u].push_back(v);//有向图
}
for(int i = 1; i <= n; i++){
if(!dfn[i]) tarjan(i);//输出
}
return 0;
}
【模版】图的割点和桥
割点
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 1e6 + 5;
vector<int> g[N];
int dfn[N], low[N];
int ans[N], vis[N];
int n, m, res, dfncnt, root;
inline void tarjan(int u, int fa)
{
dfn[u] = low[u] = ++dfncnt;//时间戳
int child = 0;
for(int i = 0; i < g[u].size(); i++){
int v = g[u][i];
if(!dfn[v]){
child++;
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(dfn[u] <= low[v]){//是割点
if(child > 1 || u != root) ans[u] = 1;//标记
}
}
else if(v != fa) low[u] = min(low[u], dfn[v]);
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i++){
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i = 1; i <= n; i++){
if(!dfn[i]){
root = i;
tarjan(i, i);
}
}
for(int i = 1; i <= n; i++){
if(ans[i]) res++;
}
cout << res << "\n";
for(int i = 1; i <= n; i++){
if(ans[i]) cout << i << " ";
}
return 0;
}
桥