[树链剖分]hihocoder1883

描述

有一个无向图，有n个点，m₁条第一类边和m₂条第二类边。第一类边有边权，第二类边无边权。请为第二类的每条边定义一个边权，使得第二类边可能全部出现在该无向图的最小生成树上，同时要求第二类边的边权总和尽可能大。
注：第二类边不会形成环

输入

第一行三个数n，m₂，m₁

接下来m₂行，每行两个数，描述一条第二类边，分别表示两个端点接下来m₁行，每行三个数，描述一条第一类边，分别表示两个端点和边权

对于30%的数据，n ≤ 5

对于60%的数据，n ≤ 1000

对于100%的数据，1 ≤ n ≤ 100000, m₁ ≤ 2 × n, m₂ < n

输出

输出一个数，表示第二类边的权值总和最大可能为多少。（若可能为无穷大则输出-1）

样例输入

样例输出

题解：

将所有第二类边权当作0处理，先构造出生成树。

之后对于不在生成树上的边e，我们尝试加入e，如果构成的环中有一条边大于e则将那条边用e代替更优。

所以我们构造出生成树后，令第二类边权值为x = inf，每次对于一条不在生成树中的边权值w，让环上的第二类边权值x = min(x, w)，即树上的链赋值操作，树链剖分即可。

 #include <bits/stdc++.h>

 #define ll long long

 #define ull unsigned long long

 #define st first

 #define nd second

 #define pii pair<int, int>

 #define pil pair<int, ll>

 #define pli pair<ll, int>

 #define pll pair<ll, ll>

 #define tiii tuple<int, int, int>

 #define pw(x) ((1LL)<<(x))

 #define lson l, m, rt<<1

 #define rson m+1, r, rt<<1|1

 #define sqr(x) ((x)*(x))

 #define SIZE(A) ((int)(A.size()))

 #define LENGTH(A) ((int)(A.length()))

 #define FIN freopen("A.in","r",stdin);

 #define FOUT freopen("A.out","w",stdout);

 using namespace std;

 /***********/

 template<typename T>

 bool scan (T &ret) {

     char c;

     int sgn;

     if (c = getchar(), c == EOF) return ; //EOF

     while (c != '-' && (c < '' || c > '') ) c = getchar();

     sgn = (c == '-') ? - : ;

     ret = (c == '-') ?  : (c - '');

     while (c = getchar(), c >= '' && c <= '') ret = ret *  + (c - '');

     ret *= sgn;

     return ;

 }

 template<typename N,typename PN>inline N flo(N a,PN b){return a>=?a/b:-((-a-)/b)-;}

 template<typename N,typename PN>inline N cei(N a,PN b){return a>?(a-)/b+:-(-a/b);}

 template<typename T>inline int sgn(T a) {return a>?:(a<?-:);}

 template<class T> int countbit(const T &n) { return (n==)?:(+countbit(n&(n-))); }

 template <class T1, class T2>

 bool gmax(T1 &a, const T2 &b) { return a < b? a = b, :;}

 template <class T1, class T2>

 bool gmin(T1 &a, const T2 &b) { return a > b? a = b, :;}

 template <class T> inline T lowbit(T x) {return x&(-x);}

 template<class T1, class T2>

 ostream& operator <<(ostream &out, pair<T1, T2> p) {

     return out << "(" << p.st << ", " << p.nd << ")";

 }

 template<class A, class B, class C>

 ostream& operator <<(ostream &out, tuple<A, B, C> t) {

     return out << "(" << get<>(t) << ", " << get<>(t) << ", " << get<>(t) << ")";

 }

 template<class T>

 ostream& operator <<(ostream &out, vector<T> vec) {

     out << "("; for(auto &x: vec) out << x << ", "; return out << ")";

 }

 void testTle(int &a){

     while() a = a*(ll)a%;

 }

 const ll inf = 0x3f3f3f3f;

 const ll INF = 1e17;

 const int mod = 1e9+;

 const double eps = 1e-;

 const int N = +;

 const double pi = acos(-1.0);

 /***********/

 struct Edge{

     int x, y, w;

 };

 Edge edge1[N+N], edge2[N];

 vector<pii> ve[N];

 int n, m1, m2;

 int fa[N];

 int findf(int x) { return x == fa[x]? x: fa[x] = findf(fa[x]);}

 int dfn, f[N], fdis[N], d[N], size[N], son[N], top[N], st[N], en[N];

 struct Node {

     int maxval;

     int tag;

 };

 Node T[N<<];

 int a[N];

 void pushup(int rt) {

     T[rt].maxval = max(T[rt<<].maxval, T[rt<<|].maxval);

 }

 void pushdown(int rt) {//区间赋的值递增，之后赋的值必大于之前赋的值，故已有赋值则可跳过

     if(T[rt].tag) {

         if(!T[rt<<].tag&&T[rt<<].maxval > T[rt].tag)

             T[rt<<].tag = T[rt].tag;

         if(!T[rt<<|].tag&&T[rt<<|].maxval > T[rt].tag)

             T[rt<<|].tag = T[rt].tag;

         T[rt].tag = ;

     }

     if(T[rt].tag) {

         if(!T[rt<<].tag&&T[rt<<].maxval > T[rt].tag)

             T[rt<<].tag = T[rt].tag;

         if(!T[rt<<|].tag&&T[rt<<|].maxval > T[rt].tag)

             T[rt<<|].tag = T[rt].tag;

         T[rt].tag = ;

     }

 }

 void build(int l, int r, int rt) {

     if(l == r) {

         T[rt] = {a[l], };

         return ;

     }

     int m = (l+r) >> ;

     build(lson);

     build(rson);

     pushup(rt);

 }

 void update(int L, int R, int val, int l, int r, int rt) {

     if(L <= l&&r <= R) {

         if(T[rt].tag == ||T[rt].tag > val) T[rt].tag = val;

         return ;

     }

     pushdown(rt);

     int m = (l+r) >> ;

     if(L <= m) update(L, R, val, lson);

     if(R > m) update(L, R, val, rson);

 }

 void dfs(int x){

     size[x] = ;

     for(pii e: ve[x]) {

         int y = e.st;

         if(y != f[x]){

             f[y] = x, d[y] = d[x]+;

             fdis[y] = e.nd;

             dfs(y), size[x] += size[y];

             if(size[y] > size[son[x]])

                 son[x] = y;

         }

     }

 }

 void dfs2(int x, int y){

     st[x] = ++dfn; top[x] = y;  a[dfn] = fdis[x];

     if(son[x]) dfs2(son[x], y);

     for(pii e: ve[x]) {

         int y = e.st;

         if(y != son[x]&&y != f[x])

             dfs2(y, y);

     }

     en[x]=dfn;

 }

 //查询x,y两点的lca

 int lca(int x,int y){

     for(;top[x]!=top[y];x=f[top[x]])if(d[top[x]]<d[top[y]]) swap(x, y);

     return d[x]<d[y]?x:y;

 }

 //x是y的祖先，查询x到y方向的第一个点

 int lca2(int x, int y){

     int t;

     while(top[x]!=top[y])t=top[y],y=f[top[y]];

     return x==y?t:son[x];

 }

 //对x到y路径上的点进行操作

 void chain(int x, int y, int val){

     for(;top[x]!=top[y];x=f[top[x]]){

         if(d[top[x]]<d[top[y]]) swap(x, y);

         //change(st[top[x]],st[x]);

         update(st[top[x]], st[x], val, , n, );

     }

     if(d[x]<d[y]) swap(x, y);

     //change(st[y],st[x]);

     update(st[y], st[x], val, , n, );

 }

 long long ans;

 bool solve(int l, int r, int rt) {

     if(T[rt].maxval != inf) return true;

     if(l == r) {

         if(T[rt].tag == ) return false;

         ans += T[rt].tag;

         return true;

     }

     pushdown(rt);

     int m = (l+r) >> ;

     return solve(lson) && solve(rson);

 }

 int main() {

     scanf("%d%d%d", &n, &m2, &m1);

     for(int i = , x, y; i < m2; i++) {

         scanf("%d%d", &x, &y);

         edge2[i] = {x, y, };

     }

     for(int i = , x, y, w; i < m1; i++) {

         scanf("%d%d%d", &x, &y, &w);

         edge1[i] = {x, y, w};

     }

     sort(edge1, edge1+m1, [](Edge e1, Edge e2) {  return e1.w < e2.w; });

     for(int i = ; i <= n; i++) fa[i] = i;

     for(int i = ; i < m2; i++) {

         Edge e = edge2[i];

         int fx = findf(e.x), fy = findf(e.y);

         if(fx != fy) {

             fa[fx] = fy;

             ve[e.x].push_back({e.y, inf});

             ve[e.y].push_back({e.x, inf});

         }

     }

     vector<Edge> tmp;

     for(int i = ; i < m1; i++) {

         Edge e = edge1[i];

         int fx = findf(e.x), fy = findf(e.y);

         if(fx != fy) {

             fa[fx] = fy;

             ve[e.x].push_back({e.y, e.w});

             ve[e.y].push_back({e.x, e.w});

         }

         else tmp.push_back(e);//将e.x -> e.y路径上的边w = min(w, e.w);

     }

     dfs();

      dfs2(, );

     build(, n, );

     for(Edge e: tmp) {

         int x = e.x, y = e.y, w = e.w;

         int ancestor = lca(x, y);

         if(ancestor != x) {

             int xx = lca2(ancestor, x);

             chain(xx, x, w);

         }

         if(ancestor != y) {

             int yy = lca2(ancestor, y);

             chain(yy, y, w);

         }

     }

     printf("%lld\n", solve(, n, )? ans: -);

     return ;

 }

巴特西

[树链剖分]hihocoder1883

描述

输入

输出

最新文章

热门文章