题解 P7146 【[THUPC2021 初赛]独立】

· · 题解

瞎几把写的乱搞。

首先拿那个 maker 玩一玩，可以发现环数一般都很小，随了蛮久好像最大就 7 的样子。

所以可以把涉及到的 14 个点拿出来，枚举选/不选，树形背包。

然后这样是 \mathcal O(4^{cnt}\cdot n) 的，过不去。

然后可以发现一般是不连通的，有效的连通块大小大概是几千的样子（具体多少我不记得了）然后只对这些连通块 dp，印象中可以跑到比较后的点了，但还是过不去。

然后可以发现每条环边都是返祖边的，那么有效枚举量只有 3^{cnt} 的，先枚举每条返祖边贡献/不贡献，对于不贡献的情况只需要枚举儿子的选择情况。

复杂度就是 \mathcal O(3^{cnt}\cdot \textrm{size}) 了。\rm size 是涉及到的树的大小，cnt 是环数。

代码很丑，修修补补过的。

#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define mp make_pair
#define pi pair<int, int>
#define pb push_back
#define vi vector<int>
#define int long long
int gi() {
    char cc = getchar() ; int cn = 0, flus = 1 ;
    while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
    while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
    return cn * flus ;
}
const int inf = 1e14 + 7 ; 
const int P = 1e9 + 7 ; 
const int N = 2e5 + 5 ; 
const int M = 30 ; 
int n, m, cnt, A[N], Ans, dp[N][2], zk[N], zt[N], g[N], rt[N] ; 
int head[N], fa[N], st[M], top, c[M], zmy, f[N] ;
int ban[N] ; 
struct E {
    int to, next, w ; 
} e[N] ; 
map<pi, int> S ;
struct node {
    int x, y, z ; 
};
node ST[15] ; int num ; 
int fd(int x) {
    return (fa[x] == x) ? fa[x] : fa[x] = fd(fa[x]) ; 
}
void add(int x, int y, int z) {
    e[++ cnt] = (E){ y, head[x], z }, head[x] = cnt,
    e[++ cnt] = (E){ x, head[y], z }, head[y] = cnt ; 
}
void merge(int x, int y, int zz) {  
    int u = fd(x), v = fd(y) ;
    fa[u] = v, add(x, y, zz) ; 
} 
int dfn[N], color ; 
void dfs(int x, int ff) {
    zk[x] = 1 ; 
    Next( i, x ) {
        int v = e[i].to ; if(v == ff) continue ; 
        if(ban[i]) continue ; 
        dfs(v, x) ; 
        dp[x][0] += max(dp[v][1], dp[v][0]) ;
        dp[x][1] += max(dp[v][1] - e[i].w, dp[v][0]) ; 
    }
}
void Dfs(int x, int ff) {
    dfn[x] = ++ color ;
    if(x == ff) rt[x] = 1 ;  
    Next( i, x ) {
        int v = e[i].to ; if(v == ff) continue ; 
        if( !dfn[v] ) Dfs( v, x ), g[x] |= g[v] ;
        else if(dfn[v] < dfn[x]) 
        ST[++ num] = (node){v, x, e[i].w}, ban[i] = 1, ban[i ^ 1] = 1, g[x] = 1 ; 
    }
}
int h[N], qls, cc[100], ttop ; 
int root[N], fgo ; 
signed main()
{
    int xx, yy, zz ; cnt = 1 ; 
    n = gi(), m = gi(), xx = gi(), yy = gi(), A[0] = gi(), zz = gi() ; 
    rep( i, 1, n ) A[i] = (A[i - 1] * 101 + 137) % P ; 
    rep( i, 1, n ) fa[i] = i ; 
    rep( i, 1, m ) {
        xx = (xx * 101 + 137) % P, yy = (yy * 101 + 137) % P,
        zz = (zz * 101 + 137) % P ; 
        int x = xx % n + 1, y = yy % n + 1 ; 
        if(!S[mp(x, y)] && (x != y)) 
            S[mp(x, y)] = S[mp(y, x)] = 1, merge(x, y, zz) ; 
    }
    rep( i, 1, n ) if(!dfn[i]) Dfs(i, i) ; 
    for(re int i = 1; i <= num; ++ i)
    st[++ top] = ST[i].x, st[++ top] = ST[i].y ; 
    sort(st + 1, st + top + 1) ; 
    rep( i, 1, top ) if(st[i] != st[i - 1]) c[++ zmy] = st[i] ; 
    int limit = (1 << zmy) - 1 ; 
    rep( i, 1, zmy ) f[c[i]] = 1 ; 
    int SA = 0 ; 
    rep( i, 1, n ) dp[i][0] = 0, dp[i][1] = A[i] ;
    rep( i, 1, n ) if(rt[i] && (!g[i])) dfs(i, i), SA += max(dp[i][0], dp[i][1]) ; 
    rep( i, 1, n ) if(!zk[i]) h[++ qls] = i ; 
    rep( i, 1, n ) if(!zk[i] && rt[i]) root[++ fgo] = i ; 
    limit = (1 << num) - 1 ; 
    for(re int AC = 0; AC <= limit; ++ AC) {
        int fSA = SA ; 
        rep( j, 1, zmy ) zt[c[j]] = 0 ;
        for(re int j = 1; j <= num; ++ j) {
            if(AC & (1 << (j - 1))) 
            fSA -= ST[j].z, zt[ST[j].x] = 1, zt[ST[j].y] = 1 ; 
        }
        int lim = (AC ^ limit) ; 
        for(re int T = lim; ; T = (T - 1) & lim) {
            rep( i, 1, qls ) zk[h[i]] = 0, dp[h[i]][1] = A[h[i]], dp[h[i]][0] = 0 ; 
            rep( j, 1, zmy ) if(zt[h[j]]) dp[h[j]][0] = -inf ; 
            rep( j, 1, num ) {
                if(!((1 << (j - 1)) & lim)) continue ; 
                if((1 << (j - 1)) & T) 
                dp[ST[j].x][0] = -inf, dp[ST[j].y][1] = -inf ; 
                else 
                dp[ST[j].x][1] = -inf ; 
            }
            int ans = fSA ; 
            rep( i, 1, fgo ) dfs(root[i], root[i]), ans += max( dp[root[i]][0], dp[root[i]][1] ) ; 
            Ans = max(Ans, ans) ; 
            if(!T) break ; 
        }
    }
    cout << Ans << endl ; 
    return 0 ;
}