最优比率生成树

#include <bits/stdc++.h>

#define INF 1e9

using namespace std;

const int N = 1010, M = N << 1;
const double eps = 1e-5;

int n, m;
struct Node{
    int x, y, h;
}a[N];
double dist[N];
bool st[N];

double get_dist(int i, int j){
    int dx = a[i].x - a[j].x;
    int dy = a[i].y - a[j].y;
    return sqrt(dx * dx + dy * dy);
}
bool check(double mid){
    double ans = 0;
    for(int i = 1;i <= n; ++ i){
        int t = -1;
        for(int j = 1;j <= n; ++ j){
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        st[t] = true;
        ans += dist[t];
        for(int j = 1;j <= n; ++ j){
            if(!st[j] && dist[j] > dist[t] + abs(a[j].h - a[t].h) - mid * get_dist(t, j))
                dist[j] = dist[t] + abs(a[j].h - a[t].h) - mid * get_dist(j, t);
        }
    }
    return ans >= 0.0;
}

int main(){

    while(scanf("%d", &n), n){

        for(int i = 1;i <= n; ++ i) dist[i] = INF;
        for(int i = 1;i <= n; ++ i) st[i] = false;
        for(int i = 1;i <= n; ++ i) scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].h);
        double l = 0, r = 1e9 + 10;
        while(r - l > eps){
            double mid = (l + r) / 2;
            if(check(mid)) l = mid;
            else r = mid;
        }
        printf("%.3f\n", r);
    }
    return 0;
}

最短路径树个数

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

#define LL long long

using namespace std;

const int N = 2e3, M = 2e6, mod = 2147483647;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
LL ans = 1;
LL cnt[N];
int dist[N];
bool st[N];

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void prim(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    cnt[1] = 1;

    for(int i = 1;i < n;i ++ ){
        int t = -1;
        for(int j = 1;j <= n;j ++ )
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        st[t] = true;
        for(int j = h[t];~j;j = ne[j]){
            int ver = e[j];
            if(!st[ver] && dist[ver] > dist[t] + w[j]){
                dist[ver] = dist[t] + w[j];
                cnt[ver] = 1;
            }else if(!st[ver] && dist[ver] == dist[t] + w[j]) cnt[ver] ++ ;
        }
    }
}
int main(){
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while(m -- ){
        int a, b, c; scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    prim();
    for(int i = 1;i <= n;i ++ ) ans = (ans * cnt[i]) % mod;
    printf("%lld\n", ans);
    return 0;
}

背包单调队列

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20010;

int dp[N], pre[N], q[N];
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        memcpy(pre, dp, sizeof(dp));
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = 0; j < v; ++j) {
            int head = 0, tail = -1;
            for (int k = j; k <= m; k += v) {

                if (head <= tail && k - s*v > q[head])
                    ++head;

                while (head <= tail && pre[q[tail]] - (q[tail] - j)/v * w <= pre[k] - (k - j)/v * w)
                    --tail;

                if (head <= tail)
                    dp[k] = max(dp[k], pre[q[head]] + (k - q[head])/v * w);

                q[++tail] = k;
            }
        }
    }
    cout << dp[m] << endl;
    return 0;
}

树链剖分

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10, M = N << 1;

int n, m;
int h[N], e[M], ne[M], tr_w[N], Idx;
int depth[N], fa[N], sz[N], son[N];
int dfn[N], timestamp, w[N], top[N];
struct Node{
    int l, r;
    int lc, rc;
    LL sum, lazy_tag;
}tr[N << 1];
int idx, root;

void add(int a, int b){
    e[Idx] = b, ne[Idx] = h[a], h[a] = Idx ++ ;
}
void dfs1(int u, int father){
    fa[u] = father;
    depth[u] = depth[father] + 1;
    sz[u] = 1;
    int maxsize = -1;
    // cout << u << " ";
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        if(j == father) continue;
        dfs1(j, u);
        sz[u] += sz[j];
        if(sz[j] > maxsize){
            maxsize = sz[j];
            son[u] = j;
        }
    }
}
void dfs2(int u, int t){
    top[u] = t;
    dfn[u] = ++ timestamp;
    w[timestamp] = tr_w[u];
    // cout << u << " ";
    if(!son[u]) return ;
    dfs2(son[u], t);
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        if(j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}
void newnode(int &u, int l, int r){
    u = ++ idx;
    tr[u].lc = tr[u].rc = 0;
    tr[u].l = l, tr[u].r = r;
    tr[u].lazy_tag = 0;
}
void pushup(int u){
    tr[u].sum = tr[tr[u].lc].sum + tr[tr[u].rc].sum;
}
void pushdown(int u){
    if(!tr[u].lazy_tag) return ;
    int lc = tr[u].lc, rc = tr[u].rc;
    tr[lc].sum += (tr[lc].r - tr[lc].l + 1) * tr[u].lazy_tag;
    tr[rc].sum += (tr[rc].r - tr[rc].l + 1) * tr[u].lazy_tag;
    tr[lc].lazy_tag += tr[u].lazy_tag;
    tr[rc].lazy_tag += tr[u].lazy_tag;
    tr[u].lazy_tag = 0;
}
void build(int &u, int l, int r){
    if(!u) newnode(u, l, r);
    if(l == r){
        tr[u].sum = w[r];
        return ;
    }
    int mid = l + r >> 1;
    build(tr[u].lc, l, mid);
    build(tr[u].rc, mid + 1, r);
    pushup(u);
}
void modify(int &u, int L, int R, int val){
    int l = tr[u].l, r = tr[u].r;
    if(l >= L && r <= R){
        tr[u].lazy_tag += val;
        tr[u].sum += (tr[u].r - tr[u].l + 1) * val;
        return ;
    }
    pushdown(u);
    int mid = l + r >> 1;
    if(L <= mid) modify(tr[u].lc, L, R, val);
    if(R > mid) modify(tr[u].rc, L, R, val);
    pushup(u);
}
LL query(int &u, int L, int R){
    int l = tr[u].l, r = tr[u].r;
    if(l >= L && r <= R) return tr[u].sum;
    int mid = l + r >> 1;
    pushdown(u);
    LL sum = 0;
    if(L <= mid) sum += query(tr[u].lc, L, R);
    if(R > mid) sum += query(tr[u].rc, L, R);
    return sum;
}
void mchain(int x, int y, int val){
    while(top[x] != top[y]){
        if(depth[top[x]] < depth[top[y]])
            swap(x, y);
        modify(root, dfn[top[x]], dfn[x], val);
        x = fa[top[x]];
    }
    if(depth[x] > depth[y]) swap(x, y);
    modify(root, dfn[x], dfn[y], val);
}
LL qchain(int x, int y){
    LL res = 0;
    while(top[x] != top[y]){
        if(depth[top[x]] < depth[top[y]])
            swap(x, y);
        res += query(root, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if(depth[x] > depth[y]) swap(x, y);
    res += query(root, dfn[x], dfn[y]);
    return res;
}
void mson(int x, int val){
    modify(root, dfn[x], dfn[x] + sz[x] - 1, val);
}
LL qson(int x){
    return query(root, dfn[x], dfn[x] + sz[x] - 1);
}
int main(){

    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 1;i <= n;i ++ ) cin >> tr_w[i];
    for(int i = 1;i < n;i ++ ){
        int a, b; cin >> a >> b;
        add(a, b), add(b, a);
    }
    dfs1(1, 1);
    dfs2(1, 1);
    build(root, 1, timestamp);
    // cout << n << " " << timestamp << " " << root << endl;

    cin >> m;
    while(m -- ){
        int op; cin >> op;
        if(op == 1){
            int u, v, k; cin >> u >> v >> k;
            mchain(u, v, k);
        }else if(op == 2){
            int u, k; cin >> u >> k;
            mson(u, k);
        }else if(op == 3){
            int u, v; cin >> u >> v;
            cout << qchain(u, v) << endl;
        }else{
            int u; cin >> u;
            cout << qson(u) << endl;
        }
    }

    return 0;
}