Problem

给定一棵有边权的树。树上每个点是黑或白的。黑白点能两两交换。

求符合任意一个白点到最近黑点的距离小于等于x时，黑白点交换次数最少为多少。

Solution

明显是一题树形DP。我们先跑一边Floyd。

F[i][j][k]表示以i为根的子树中，连向结点j，子树中已经确定有k个是黑点所需要的最小交换次数。

G[i][k]表示以i为根的子树，已经确定有k个是黑点所需要的最小交换次数。

设当前根为x，子结点为y，连向结点i，总共确定了k个黑点，新确定了l个黑点，转移方程为：

F[x][i][k]=min(min{f[x][i][k-l]+best[y][l]},min{f[x][i][k-l+1]+f[y][i][l]-!col[i]});

Notice

本道题很容易卡内存

Code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define sqz main#define ll long long#define reg register int#define rep(i, a, b) for (reg i = a; i <= b; i++)#define per(i, a, b) for (reg i = a; i >= b; i--)#define travel(i, u) for (reg i = head[u]; i; i = edge[i].next)const int N = 500, INF = 0x3f3f;const double eps = 1e-6, phi = acos(-1);ll mod(ll a, ll b) {if (a >= b || a < 0) a %= b; if (a < 0) a += b; return a;}ll read(){ ll x = 0; int zf = 1; char ch; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}void write(ll y) { if (y < 0) putchar('-'), y = -y; if (y > 9) write(y / 10); putchar(y % 10 + '0');}short F[N + 1][N + 1][N + 1], G[N + 1][N + 1];int Dis[N + 1][N + 1], head[N + 1], Size[N + 1], Cost[N + 1], num = 0, Sum = 0, n, m;struct node{    int vet, next, val;}edge[2 * N + 5];void add(int u, int v, int w){    edge[++num].vet = v;    edge[num].next = head[u];    edge[num].val = w;    head[u] = num;}void dp(int u, int fa){    travel(i, u)    {        int v = edge[i].vet;        if (v == fa) continue;        dp(v, u);    }    rep(i, 1, n)    {        if (Dis[u][i] > m) continue;        Size[u] = 1;  F[u][i][1] = 1 - Cost[i];        travel(j, u)        {            int v = edge[j].vet;            if (v == fa) continue;            per(k, min(Size[u] + Size[v], Sum), 0)            {                int now = INF, First = max(k - Size[u], 0);                rep(l, First, min(k, Size[v])) now = min(now, min(F[u][i][k - l] + G[v][l], l == First ? INF : F[u][i][k - l + 1] + F[v][i][l] - (1 - Cost[i])));                F[u][i][k] = now;            }            Size[u] += Size[v];        }    }    rep(i, 1, min(Sum, Size[u]))        rep(j, 1, n) G[u][i] = min(G[u][i], F[u][j][i]);}int sqz(){    memset(Dis, INF, sizeof Dis); memset(F, INF, sizeof F); memset(G, INF, sizeof G);    n = read(), m = read();    rep(i, 1, n) Cost[i] = read(), Sum += Cost[i];    rep(i, 1, n - 1)    {        int u = read(), v = read(), w = read();        add(u, v, w), add(v, u, w);        Dis[u][v] = Dis[v][u] = w;    }    rep(i, 1, n) Dis[i][i] = 0;    rep(k, 1, n)        rep(i, 1, n)            rep(j, 1, n)                Dis[i][j] = min(Dis[i][j], Dis[i][k] + Dis[k][j]);    dp(1, 0);    printf("%d\n", G[1][Sum] == INF ? -1 : G[1][Sum]);    return 0;}