CF1773J Jumbled Trees

Para · 2023-01-06 14:58:47 · 题解

操作数不超过 2m 似乎是一个非常有用的提示。

每次要找一棵生成树进行操作，于是对原图建出一棵 \text{dfs} 树，那么剩下的边呢？它们可以替换掉 \text{dfs} 树上的边。

比如设一条非树边为 x，它可以替换掉 y，可以通过对替换前后的两棵生成树分别进行进行操作，等价的做到 x 边 +e，y 边 -e，其他边权值不变。

将可以互相替换的数再连边建立新图，会形成若干个连通块，将每一个连通块中抽出一棵生成树保留，图就变成了一个森林。会发现之前对边加减 e 的操作是不改变边权总和的，唯一能改变边权总和的就只有对最开始的生成树进行操作，所以只需判断一下是否能操作最开始的生成树，使得每一个连通块中的和为它们最终需要达到的和，能满足就可以构造出一组解（每棵树里面从叶子往上满足每个点需求就行了），实现的精细一点可以做到 m 次操作，时间复杂度 O(nm)。

（开始和与个数模意义下均为 0 没判断被卡傻了）

可以顺便看一下 P8156，同样的套路。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define inf 1e9
#define pii pair <int, int>
int mod = 1e9 + 7;
inline int read () {
    int x = 0, f = 1;
    char ch = getchar ();
    while (ch < '0' || ch > '9') f = ((ch == '-') ? -1 : f), ch = getchar ();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar ();
    return x * f;
}
inline void write (int x) {
    if (x < 0) x = -x, putchar ('-');
    if (x >= 10) write (x / 10);
    putchar (x % 10 + '0');
}
inline int quickmod (int x, int y) {
    x %= mod;
    int Ans = 1;
    while (y) {
        if (y & 1) Ans = (Ans * x) % mod;
        x = (x * x) % mod;
        y >>= 1;
    }
    return Ans;
}
inline void Add(int &x, int y) {
    x += y;
    if(x >= mod) x -= mod;
}
inline void Dec(int &x, int y) {
    x -= y;
    if(x < 0) x += mod;
}
struct UnionSet {
    int fa[1005];
    inline void makeSet(int x) {
        for(int i = 1; i <= x; i++) fa[i] = i;
    }
    int findSet(int x) {
        if(x == fa[x]) return x;
        return fa[x] = findSet(fa[x]);
    }
    void unionSet(int x, int y) {
        x = findSet(x), y = findSet(y);
        if(x == y) return ;
        fa[x] = y; 
    }
}U;
int n, m;
struct Edge {
    int u, v, e;
}edge[1005];
struct st {
    int v, id;
    st() {}
    st(int A, int B) {
        v = A, id = B;
    }
};
vector <st> G[1005];
vector <int> V[1005];
int Fa[1005], dep[1005], val[1005], vis[1005];
vector <int> bas, P;
vector <vector <int> > Ans;
int visbas[1005];
void dfs(int x, int fa) {
    Fa[x] = fa, dep[x] = dep[fa] + 1;
    vis[x] = 1;
    for(auto y : G[x]) {
        if(vis[y.v]) continue;
        bas.push_back(y.id);
        visbas[y.id] = 1;
        val[y.v] = y.id;
        dfs(y.v, x); 
    }
}
int cnt;
inline void print(int x, int y, int e) {//x += e, y -= e;
    Dec(edge[x].e, e), Add(edge[y].e, e); 
    if(visbas[x]) {
        cnt = 0; 
        P[cnt++] = (-e % mod + mod) % mod;
        for(auto i : bas) if(i != x) P[cnt++] = i;
        P[cnt++] = y;
        Ans.push_back(P);

        cnt = 0;
        P[cnt++] = (e % mod + mod) % mod;
        for(auto i : bas) P[cnt++] = i;
        Ans.push_back(P);
    }
    else {
        cnt = 0;
        P[cnt++] = (e % mod + mod) % mod;
        for(auto i : bas) if(i != y) P[cnt++] = i;
        P[cnt++] = x;
        Ans.push_back(P);

        cnt = 0;
        P[cnt++] = (-e % mod + mod) % mod;
        for(auto i : bas) P[cnt++] = i;
        Ans.push_back(P);
    }
}

inline void add(int u, int v) {
    if(U.findSet(u) == U.findSet(v)) return ;
    V[u].push_back(v);
    V[v].push_back(u);
//  printf("[%lld %lld]\n", u, v);
    U.unionSet(u, v);
}
int s[1005], op[1005];
void dfs2(int x, int fa) {
    for(auto y : V[x]) {
        if(y == fa) continue;
        dfs2(y, x);
    }
    if(fa) print(x, fa, edge[x].e);
    else if(edge[x].e) {
        puts("-1");
        exit(0);
    }
}
signed main () {
//  freopen ("1.in", "r", stdin);
//  freopen (".out", "w", stdout);
    n = read(), m = read(), mod = read();
    P.resize(n);
    for(int i = 1; i <= m; i++) {
        int u = read(), v = read(), e = read();
        edge[i].u = u, edge[i].v = v, edge[i].e = e;
        G[u].push_back(st(v, i));
        G[v].push_back(st(u, i));
    }
    dfs(1, 0);
    U.makeSet(m);
    for(int i = 1; i <= m; i++) {
        if(visbas[i]) continue;
        int u = edge[i].u, v = edge[i].v;
        while(u != v) {
            if(dep[u] < dep[v]) swap(u, v);
            add(i, val[u]);
            u = Fa[u];
        }
    }
    memset(vis, 0, sizeof vis);
    for(int i = 1; i <= m; i++) {
        op[U.findSet(i)] += visbas[i];
        Add(s[U.findSet(i)], edge[i].e);
    }
    int nd = 0;
    for(int i = 1; i <= m; i++) if(!nd) nd = s[U.findSet(i)] * quickmod(op[U.findSet(i)], mod - 2) % mod;
    for(int i = 1; i <= m; i++) if(nd * op[U.findSet(i)] % mod != s[U.findSet(i)]) return printf("-1\n") & 0;

    cnt = 0;
    P[cnt++] = (nd % mod + mod) % mod;
    for(auto i : bas) P[cnt++] = i, Dec(edge[i].e, nd);
    Ans.push_back(P);

    for(int i = 1; i <= m; i++) if(U.findSet(i) == i) dfs2(i, 0); 
//  return 0;
    write((int)Ans.size()), putchar('\n');
    for(auto x : Ans) {
        for(auto y : x) write(y), putchar(' ');
        putchar('\n');
    }
    return 0;
}
/*
2 2 2
1 2 1
2 1 0
*/