头像

Ncik




在线 


最近来访(931)
用户头像
Brokenheart100
用户头像
lym.
用户头像
xiaojia
用户头像
哈哈哈_314
用户头像
zero096
用户头像
tomousw
用户头像
1eave
用户头像
冰之韵
用户头像
空尘y
用户头像
蓬蒿人
用户头像
ACG2021
用户头像
WangJY
用户头像
lindi530
用户头像
Narity
用户头像
NULL_20
用户头像
arthur15
用户头像
Hanasaki
用户头像
心升明月
用户头像
大雪莱
用户头像
保底不歪抽早柚

活动打卡代码 AcWing 854. Floyd求最短路

Ncik
1天前
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;

inline void chmin(int& x, int y) { if (x > y) x = y; }

int main() {
    int n, m, q;
    cin >> n >> m >> q;

    const int INF = 1001001001;
    vector d(n, vector<int>(n, INF));
    rep(i, n) d[i][i] = 0;
    rep(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        --a; --b;
        chmin(d[a][b], c);
    }

    rep(k, n)rep(i, n)rep(j, n) {
        chmin(d[i][j], d[i][k]+d[k][j]);
    }

    rep(qi, q) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        int ans = d[a][b];
        if (ans > INF/2) puts("impossible");
        else cout << ans << '\n';
    }

    return 0;
}



Ncik
1天前
// Dinic 板子
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
#include  <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i <  (n); ++i)
#define INF 1e18

using namespace std;
using ll = long long;

template <typename Cap>
struct dinic{
  struct edge{
    int to, rev;
    Cap cap;
    edge(int to, int rev, Cap cap): to(to), rev(rev), cap(cap) {}
  };
  int N;
  vector<vector<edge>> G;
  dinic() {}
  dinic(int N): N(N), G(N) {}
  void add_edge(int from, int to, Cap cap){
    G[from].push_back(edge(to, G[to].size(), cap));
    G[to].push_back(edge(from, G[from].size() - 1, 0));
  }
  Cap dfs(vector<int> &d, vector<int> &iter, int v, int t, Cap f){
    if (v == t){
      return f; 
    }
    while (iter[v] < G[v].size()){
      int w = G[v][iter[v]].to;
      if (G[v][iter[v]].cap > 0 && d[v] < d[w]){
        Cap f2 = dfs(d, iter, w, t, min(f, G[v][iter[v]].cap));
        if (f2 > 0){
          G[v][iter[v]].cap -= f2;
          G[w][G[v][iter[v]].rev].cap += f2;
          return f2;
        }
      }
      iter[v]++;
    }
    return 0;
  }
  Cap max_flow(int s, int t){
    Cap flow = 0;
    while (true){
      vector<int> d(N, -1);
      d[s] = 0;
      queue<int> Q;
      Q.push(s);
      while (!Q.empty()){
        if (d[t] != -1){
          break;
        }
        int v = Q.front();
        Q.pop();
        for (auto &e : G[v]){
          int w = e.to;
          if (e.cap > 0 && d[w] == -1){
            d[w] = d[v] + 1;
            Q.push(w);
          }
        }
      }
      if (d[t] == -1){
        break;
      }
      vector<int> iter(N, 0);
      while (true){
        Cap f = dfs(d, iter, s, t, INF);
        if (f == 0){
          break;
        }
        flow += f;
      }
    }
    return flow;
  }
};

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    int n, m, s, t;
    cin >> n >> m >> s >> t;
    --s; --t;

    dinic<ll> g(n);
    rep(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        --a; --b;
        g.add_edge(a, b, c);
    }

    ll ans = g.max_flow(s, t);
    cout << ans << '\n';

    return 0;
}



Ncik
1天前

算法

(拆点、最大流)

抛去饮料的因素,先求如何分配使得尽可能多的牛分配到自己喜欢的食物。不难发现,这是个二分图匹配模型。
建立源点和汇点,源点向所有牛建一条容量为 $1$ 的边,牛向各自喜欢的食物建一条容量为 $1$ 的边,所有食物向汇点建一条容量为 $1$ 的边。那么,这个图的最大流就是所求解,故通过最大流便可解决二分图匹配的问题。

回到这道题,多了饮料这个条件
尝试运用类似方法建图:
源点向所有食物建一条容量为 $1$ 的边,食物向喜欢它的牛建一条容量为 $1$ 的边,牛向它喜欢的饮料建一条容量为 $1$ 的边,所有饮料再向汇点建一条容量为 $1$ 的边。
如此建图,求得的最大流是否就是所求解呢?
答案是否定的,由于一开始忽略了每头牛只能分配一种食物和饮料这一条件,导致一头牛可能会被多条流访问。
所以这里采用拆点,将每头牛拆成食物一侧的牛和饮料一侧的牛,食物向食物一侧的牛建一条容量为 $1$ 的边,饮料一侧的牛向饮料建一条容量为 $1$ 的边,同时食物一侧的牛再向相应的饮料一侧的牛建一条容量为 $1$ 的边,问题得以解决。

C++ 代码

#include  <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i <  (n); ++i)
#define INF 1e9

using namespace std;

template <typename Cap>
struct dinic{
  struct edge{
    int to, rev;
    Cap cap;
    edge(int to, int rev, Cap cap): to(to), rev(rev), cap(cap) {}
  };
  int N;
  vector<vector<edge>> G;
  dinic() {}
  dinic(int N): N(N), G(N) {}
  void add_edge(int from, int to, Cap cap){
    G[from].push_back(edge(to, G[to].size(), cap));
    G[to].push_back(edge(from, G[from].size() - 1, 0));
  }
  Cap dfs(vector<int> &d, vector<int> &iter, int v, int t, Cap f){
    if (v == t){
      return f; 
    }
    while (iter[v] < G[v].size()){
      int w = G[v][iter[v]].to;
      if (G[v][iter[v]].cap > 0 && d[v] < d[w]){
        Cap f2 = dfs(d, iter, w, t, min(f, G[v][iter[v]].cap));
        if (f2 > 0){
          G[v][iter[v]].cap -= f2;
          G[w][G[v][iter[v]].rev].cap += f2;
          return f2;
        }
      }
      iter[v]++;
    }
    return 0;
  }
  Cap max_flow(int s, int t){
    Cap flow = 0;
    while (true){
      vector<int> d(N, -1);
      d[s] = 0;
      queue<int> Q;
      Q.push(s);
      while (!Q.empty()){
        if (d[t] != -1){
          break;
        }
        int v = Q.front();
        Q.pop();
        for (auto &e : G[v]){
          int w = e.to;
          if (e.cap > 0 && d[w] == -1){
            d[w] = d[v] + 1;
            Q.push(w);
          }
        }
      }
      if (d[t] == -1){
        break;
      }
      vector<int> iter(N, 0);
      while (true){
        Cap f = dfs(d, iter, s, t, INF);
        if (f == 0){
          break;
        }
        flow += f;
      }
    }
    return flow;
  }
};

int main() {
    int n, f, d;
    cin >> n >> f >> d;

    // 0~n-1: 食物一侧的牛
    // n~2n-1: 饮料一侧的牛
    // 2n~2n+f-1: 食物
    // 2n+f~2n+f+d-1: 饮料
    int sv = f+d+n*2, tv = sv+1; 
    dinic<int> g(tv+1);
    // 在源点和食物之间连边
    rep(i, f) g.add_edge(sv, n*2+i, 1);
    // 在饮料和汇点之间连边
    rep(i, d) g.add_edge(n*2+f+i, tv, 1);
    // 在食物一侧的牛和饮料一侧的牛之间连边
    rep(i, n) g.add_edge(i, n+i, 1);
    rep(i, n) {
        int cf, cd, x;
        cin >> cf >> cd;

        // 在食物和食物一侧的牛连边
        while (cf--) {
            cin >> x;
            --x;
            g.add_edge(n*2+x, i, 1);
        }

        // 在饮料一侧的牛和饮料连边
        while (cd--) {
            cin >> x;
            --x;
            g.add_edge(n+i, n*2+f+x, 1);
        }
    }

    int ans = g.max_flow(sv, tv);
    cout << ans << '\n';

    return 0;
}


活动打卡代码 AcWing 886. 求组合数 II

Ncik
2天前
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using std::istream;
using std::ostream;
using ll = long long;

//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
    ll x;
    mint(ll x=0):x((x%mod+mod)%mod) {}
    mint operator-() const {
        return mint(-x);
    }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        return mint(*this) += a;
    }
    mint operator-(const mint a) const {
        return mint(*this) -= a;
    }
    mint operator*(const mint a) const {
        return mint(*this) *= a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint a) {
        return *this *= a.inv();
    }
    mint operator/(const mint a) const {
        return mint(*this) /= a;
    }
};
istream& operator>>(istream& is, mint& a) {
    return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
    return os << a.x;
}

// combination mod prime
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
} comb(100005);

int main() {
    int n;
    cin >> n;

    rep(i, n) {
        int a, b;
        cin >> a >> b;
        cout << comb(a, b) << '\n';
    }

    return 0;
}


活动打卡代码 AcWing 885. 求组合数 I

Ncik
2天前
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using std::istream;
using std::ostream;
using ll = long long;

//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
    ll x;
    mint(ll x=0):x((x%mod+mod)%mod) {}
    mint operator-() const {
        return mint(-x);
    }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        return mint(*this) += a;
    }
    mint operator-(const mint a) const {
        return mint(*this) -= a;
    }
    mint operator*(const mint a) const {
        return mint(*this) *= a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint a) {
        return *this *= a.inv();
    }
    mint operator/(const mint a) const {
        return mint(*this) /= a;
    }
};
istream& operator>>(istream& is, mint& a) {
    return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
    return os << a.x;
}

// combination mod prime
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
} comb(2005);

int main() {
    int n;
    cin >> n;

    rep(i, n) {
        int a, b;
        cin >> a >> b;
        cout << comb(a, b) << '\n';
    }

    return 0;
}



Ncik
2天前

算法

(期望、组合数学)

首先,既然选取 $K$ 个数的组合是等概率选取的,那么其对应的概率就是 $\frac{1}{\binom{N}{K}}$

然后根据期望的线性性,我们可以考虑分别求最大期望和最小期望

下面只介绍求最大期望的做法,最小期望同理

  • 固定一个数作为所选数中的最大值,那么它的贡献就是从剩余数里取 $k-1$ 个数的方案数
  • 先对序列进行升序排序
  • 然后分别将序列的后 $N-K+1$ 个数作为最大数,对于其他 $K-1$ 个数,最大数之后的数就不用考虑了,只需在前面剩下的数里取即可
  • 求出这些数的贡献之和,再将它与概率做乘积即可得到最大期望

C++ 代码

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using ll = long long;
using mint = modint998244353;

// combination mod prime
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
} comb(200005);

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    rep(i, n) cin >> a[i];

    sort(a.begin(), a.end());

    mint s_max;
    for (int i = n-1; i >= k-1; --i) {
        s_max += a[i]*comb(i, k-1);
    }
    mint s_min;
    rep(i, n-k+1) {
        s_min += a[i]*comb(n-1-i, k-1);
    }

    mint ans = s_max - s_min;
    ans /= comb(n, k);
    cout << ans.val() << '\n';

    return 0;
}



Ncik
2天前

题目描述

给你一张包含 $n$ 个点和 $m$ 条边的无向带权图。要求从起点沿若干条边走到终点,再走回起点,同时每条边只能走一次。求最短的路径长度。


算法

(最小费用流)

可以将题目转化为求两条从 $1$ 到 $n$ 不想交的路径,使得路径长度之和最小。
若将 $1$ 到 $n$ 想象成 $1$ 到 $n$ 的流,而路径长度为边权总和,则可以很容易地利用费用流解决:
对给定的每一条边,附加容量为 $1$,限制其只能被选择一次,费用为边权。
建立源点和汇点,由源点向点 $1$ 建一条容量为 $2$、费用为 $0$ 的边,由点 $n$ 向汇点建一条容量为 $2$、费用为 $0$ 的边。
然后求解该网络的最小费用最大流即可。

总结:

本题巧妙地建立源点和汇点,其中源点向点 $1$ 以及点 $n$ 向汇点建边,费用为 $0$ 表示这条边是条虚边,即对结果无影响的边,容量为 $2$ 限制只能通过两条路径。
这种在求解费用流时通过新建源点和汇点,并连接相应容量边以保证通过流的容量的技巧十分重要。
注意,有时候费用最小的流往往不是最大流。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define INF 1e18

using namespace std;
using ll = long long;

template <typename Cap, typename Cost>
struct primal_dual {
    struct edge{
        int to, rev;
        Cap cap;
        Cost cost;
        edge(int to, int rev, Cap cap, Cost cost): to(to), rev(rev), cap(cap), cost(cost) {}
    };
    int N;
    vector<vector<edge>> G;
    primal_dual(){}
    primal_dual(int N): N(N), G(N){}
    void add_edge(int from, int to, Cap cap, Cost cost){
        int id1 = G[from].size();
        int id2 = G[to].size();
        G[from].push_back(edge(to, id2, cap, cost));
        G[to].push_back(edge(from, id1, 0, -cost));
    }
    pair<Cap, Cost> min_cost_flow(int s, int t, Cap F=INF){
        Cap flow = 0;
        Cost cost = 0;
        vector<Cost> h(N, 0);
        while (flow < F){
            vector<Cap> m(N, INF);
            vector<Cost> d(N, INF);
            vector<int> pv(N, -1);
            vector<int> pe(N, -1);
            vector<bool> used(N, false);
            priority_queue<pair<Cost, int>, vector<pair<Cost, int>>, greater<pair<Cost, int>>> pq;
            pq.push(make_pair(0, s));
            d[s] = 0;
            while (!pq.empty()){
                int v = pq.top().second;
                pq.pop();
                if (!used[v]){
                    used[v] = true;
                    if (v == t){
                        break;
                    }
                    int cnt = G[v].size();
                    for (int i = 0; i < cnt; i++){
                        int w = G[v][i].to;
                        if (!used[w] && G[v][i].cap > 0){
                            Cost tmp = G[v][i].cost - h[w] + h[v];
                            if (d[w] > d[v] + tmp){
                                d[w] = d[v] + tmp;
                                m[w] = min(m[v], G[v][i].cap);
                                pv[w] = v;
                                pe[w] = i;
                                pq.push(make_pair(d[w], w));
                            }
                        }
                    }
                }
            }
            if (!used[t]){
                break;
            }
            for (int i = 0; i < N; i++){
                if (used[i]){
                    h[i] -= d[t] - d[i];
                }
            }
            Cap c = min(m[t], F - flow);
            for (int i = t; i != s; i = pv[i]){
                G[pv[i]][pe[i]].cap -= c;
                G[i][G[pv[i]][pe[i]].rev].cap += c;
            }
            flow += c;
            cost += c * (-h[s]);
        }
        return make_pair(flow, cost);
    }
};

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    int sv = 0, tv = n+1;
    primal_dual<int, ll> g(tv+1);
    g.add_edge(sv, 1, 2, 0);
    g.add_edge(n, tv, 2, 0);
    rep(i, m) {
        int u, v, w;
        cin >> u >> v >> w;
        g.add_edge(u, v, 1, w);
        g.add_edge(v, u, 1, w);
    }

    ll ans = g.min_cost_flow(sv, tv, 2).second;
    cout << ans << '\n';

    return 0;
}


活动打卡代码 AcWing 2174. 费用流

Ncik
2天前
// 原始对偶
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define INF 1e18

using namespace std;
using ll = long long;

template <typename Cap, typename Cost>
struct primal_dual {
    struct edge{
        int to, rev;
        Cap cap;
        Cost cost;
        edge(int to, int rev, Cap cap, Cost cost): to(to), rev(rev), cap(cap), cost(cost) {}
    };
    int N;
    vector<vector<edge>> G;
    primal_dual(){}
    primal_dual(int N): N(N), G(N){}
    void add_edge(int from, int to, Cap cap, Cost cost){
        int id1 = G[from].size();
        int id2 = G[to].size();
        G[from].push_back(edge(to, id2, cap, cost));
        G[to].push_back(edge(from, id1, 0, -cost));
    }
    pair<Cap, Cost> min_cost_flow(int s, int t, Cap F){
        Cap flow = 0;
        Cost cost = 0;
        vector<Cost> h(N, 0);
        while (flow < F){
            vector<Cap> m(N, INF);
            vector<Cost> d(N, INF);
            vector<int> pv(N, -1);
            vector<int> pe(N, -1);
            vector<bool> used(N, false);
            priority_queue<pair<Cost, int>, vector<pair<Cost, int>>, greater<pair<Cost, int>>> pq;
            pq.push(make_pair(0, s));
            d[s] = 0;
            while (!pq.empty()){
                int v = pq.top().second;
                pq.pop();
                if (!used[v]){
                    used[v] = true;
                    if (v == t){
                        break;
                    }
                    int cnt = G[v].size();
                    for (int i = 0; i < cnt; i++){
                        int w = G[v][i].to;
                        if (!used[w] && G[v][i].cap > 0){
                            Cost tmp = G[v][i].cost - h[w] + h[v];
                            if (d[w] > d[v] + tmp){
                                d[w] = d[v] + tmp;
                                m[w] = min(m[v], G[v][i].cap);
                                pv[w] = v;
                                pe[w] = i;
                                pq.push(make_pair(d[w], w));
                            }
                        }
                    }
                }
            }
            if (!used[t]){
                break;
            }
            for (int i = 0; i < N; i++){
                if (used[i]){
                    h[i] -= d[t] - d[i];
                }
            }
            Cap c = min(m[t], F - flow);
            for (int i = t; i != s; i = pv[i]){
                G[pv[i]][pe[i]].cap -= c;
                G[i][G[pv[i]][pe[i]].rev].cap += c;
            }
            flow += c;
            cost += c * (- h[s]);
        }
        return make_pair(flow, cost);
    }
};

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    int n, m, s, t;
    cin >> n >> m >> s >> t;

    primal_dual<int, ll> g(n+1);
    rep(i, m) {
        int u, v, c, w;
        cin >> u >> v >> c >> w;
        g.add_edge(u, v, c, w);
    }

    auto [flow, cost] = g.min_cost_flow(s, t, INF);
    cout << flow << ' ' << cost << '\n';

    return 0;
}


活动打卡代码 AcWing 521. 运输计划

Ncik
2天前
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::max;
using std::vector;

const int MX = 300005;

int n, m;
vector<int> to[MX];
int dist[MX];
int dep[MX];
vector<int> co[MX];

int par[MX][20];
void dfs(int v, int p=0) {
    for (int i = 1; i < 20; ++i) {
        par[v][i] = par[par[v][i-1]][i-1];
    }
    rep(i, to[v].size()) {
        int u = to[v][i];
        if (u == p) continue;
        dist[u] = dist[v] + co[v][i];
        dep[u] = dep[v]+1;
        par[u][0] = v;
        dfs(u, v);
    }
}

int LCA(int a, int b) {
    if (dep[a] > dep[b]) std::swap(a, b);
    int gap = dep[b]-dep[a];
    for (int i = 19; i >= 0; --i) {
        int len = 1<<i;
        if (gap >= len) {
            gap -= len;
            b = par[b][i];
        }
    }
    if (a == b) return a;
    for (int i = 19; i >= 0; --i) {
        int na = par[a][i];
        int nb = par[b][i];
        if (na != nb) a = na, b = nb;
    }
    return par[a][0];
}

int d[MX];
void dfs2(int v, int p=0) {
    for (int u : to[v]) {
        if (u == p) continue;
        dfs2(u, v);
        d[v] += d[u];
    }
}

int len[MX], s[MX], t[MX], lca[MX];
bool judge(int x) {
    int cnt = 0, mx = 0;
    memset(d, 0, sizeof d);
    rep(i, m) {
        if (len[i] > x) {
            d[s[i]]++;
            d[t[i]]++;
            d[lca[i]] -= 2;
            mx = max(mx, len[i]-x);
            cnt++;
        }
    }
    dfs2(1);
    for (int v = 2; v <= n; ++v) { // d[i]==cnt意味着它是交集
        if (d[v] == cnt and dist[v]-dist[par[v][0]] >= mx) return true;
    }
    return false;
}

int main() {
    cin >> n >> m;

    rep(i, n-1) {
        int a, b, t;
        cin >> a >> b >> t;
        to[a].push_back(b); co[a].push_back(t);
        to[b].push_back(a); co[b].push_back(t);
    }

    dfs(1);

    rep(i, m) {
        cin >> s[i] >> t[i];
        lca[i] = LCA(s[i], t[i]);
        len[i] = dist[s[i]] - dist[lca[i]] + dist[t[i]] - dist[lca[i]];
    }

    int wa = -1, ac = 1001001001;
    while (abs(wa-ac) > 1) {
        int wj = (wa+ac)/2;
        if (judge(wj)) ac = wj; else wa = wj;
    }

    cout << ac << '\n';

    return 0;
}



Ncik
3天前

算法

(二分答案、贪心、LCA、树上差分) $O(n\log n)$

题意:

给你一颗带权树,以及 $M$ 条路径。现在可以把其中一条边的边权变为 $0$,问最长的路径最短是多少?

分析:

暴力删边,删完统计每条路径的长度
复杂度:$O(n^2m)$

$m=1$
只需求出唯一路径上的所有边并计算边权和以及最大边权(暴力往上跳并记录即可)
边权和减去最大边权即为答案
复杂度:$O(n)$

对于链的情况
统计长度,修改边权(别忘记改回来)可以优化一下
前缀和维护
复杂度:$O(n(n+m))$

三者结合期望得分约为 $40$

正解:
可以看到完成工作的时间等于所有运输时间的最大值
既然要最小化最大值,那就可以二分
二分答案运输时间,看是否能满足要求

计算每一条运输计划需要的时间,用倍增 $\operatorname{LCA}$
如果时间大于 $\operatorname{mid}$,那就说明这条路径上至少得改一条边
把所有时间超过 $\operatorname{mid}$ 的路径取出来,求交集 $I$

如果 $I$ 为空,那显然无法改造
否则,肯定是改造 $I$ 中边权最大的那条边,然后再检查每条计划是否时间都不超过 $\operatorname{mid}$

求树上的交集,只需要路径上的每条边都 +1
这个用树上差分即可实现
假设路径 $x \to y$,$x$ 和 $y$ 的 $\operatorname{LCA}$ 为 $z$
那么给 $x$ +1,$y$ +1,$z$ -2 即可
最后扫描一遍把等于 $\operatorname{cnt}$ ($\operatorname{cnt}$ 为超过 $\operatorname{mid}$ 的路径数量)的边取出来,再求最大的边权即可

使用倍增预处理出 $\operatorname{LCA}$ 和每条计划的运输时间
判定 $\operatorname{mid}$ 是否可行的时间复杂度是 $O(n)$
总的时间复杂度就是 $O(n\log n)$

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::max;
using std::vector;

const int MX = 300005;

int n, m;
vector<int> to[MX];
int dist[MX];
int dep[MX];
vector<int> co[MX];

int par[MX][20];
void dfs(int v, int p=0) {
    for (int i = 1; i < 20; ++i) {
        par[v][i] = par[par[v][i-1]][i-1];
    }
    rep(i, to[v].size()) {
        int u = to[v][i];
        if (u == p) continue;
        dist[u] = dist[v] + co[v][i];
        dep[u] = dep[v]+1;
        par[u][0] = v;
        dfs(u, v);
    }
}

int LCA(int a, int b) {
    if (dep[a] > dep[b]) std::swap(a, b);
    int gap = dep[b]-dep[a];
    for (int i = 19; i >= 0; --i) {
        int len = 1<<i;
        if (gap >= len) {
            gap -= len;
            b = par[b][i];
        }
    }
    if (a == b) return a;
    for (int i = 19; i >= 0; --i) {
        int na = par[a][i];
        int nb = par[b][i];
        if (na != nb) a = na, b = nb;
    }
    return par[a][0];
}

int d[MX];
void dfs2(int v, int p=0) {
    for (int u : to[v]) {
        if (u == p) continue;
        dfs2(u, v);
        d[v] += d[u];
    }
}

int len[MX], s[MX], t[MX], lca[MX];
bool judge(int x) {
    int cnt = 0, mx = 0;
    memset(d, 0, sizeof d);
    rep(i, m) {
        if (len[i] > x) {
            d[s[i]]++;
            d[t[i]]++;
            d[lca[i]] -= 2;
            mx = max(mx, len[i]-x);
            cnt++;
        }
    }
    dfs2(1);
    for (int v = 2; v <= n; ++v) { // d[i]==cnt意味着它是交集
        if (d[v] == cnt and dist[v]-dist[par[v][0]] >= mx) return true;
    }
    return false;
}

int main() {
    cin >> n >> m;

    rep(i, n-1) {
        int a, b, t;
        cin >> a >> b >> t;
        to[a].push_back(b); co[a].push_back(t);
        to[b].push_back(a); co[b].push_back(t);
    }

    dfs(1);

    rep(i, m) {
        cin >> s[i] >> t[i];
        lca[i] = LCA(s[i], t[i]);
        len[i] = dist[s[i]] - dist[lca[i]] + dist[t[i]] - dist[lca[i]];
    }

    int wa = -1, ac = 1001001001;
    while (abs(wa-ac) > 1) {
        int wj = (wa+ac)/2;
        if (judge(wj)) ac = wj; else wa = wj;
    }

    cout << ac << '\n';

    return 0;
}