2022-11-12总结

PolarSea 与边割集

Description

给定一棵 $n$ 个点的无向树，边带权，树上每个点有三种状态：无归属、属于 SolarPea、属于 PolarSea。

SolarPea 和 PolarSea 想要断掉一些边，使得对于每一对点 $(x,y)$，若 $x$ 属于 SolarPea，$y$ 属于 PolarSea，则 $x,y$ 不连通。

求断掉的边的最小权值和。

Input

第一行包含一个整数 $n$。

接下来 $n-1$ 行，每行包含三个数 $u,v,w$， 表示一条连接 $u,v$，权值为 $w$ 的边。保证给出的是一棵树。

接下来一行，首先包含一个数 $s$，表示属于 SolarPea 的点数。接下来 $s$ 个不同的数 $a_1,\cdots,a_s$，表示所有属于 SolarPea 的点。

接下来一行，首先包含一个数 $p$，表示属于 PolarSea 的点数。接下来 $p$ 个不同的数 $b_1,\cdots,b_p$，表示所有属于 PolarSea 的点。

保证 $a$ 和 $b$ 无交。

Output

输出一行包含一个整数，表示最小代价。

Hint

$1 \le n \le 10^5, 0 \le s,p \le s+p \le n, 1 \le u,v \le n, 1 \le w \le 10^3$。

Solution

简单树形 DP，把 homeless 的点随便分给 S 或者 P 集合就行了。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5+10;
const int INF = 0x3f3f3f3f;

struct edge { int to, cost; };

int n, s, p;
int col[N];
ll f[N][2];
vector<edge> ver[N];

void dfs(int x, int fa);

int main()
{
    read(n);
    for(int i = 1; i < n; i++)
    {
        int a, b, w; read(a, b, w);
        ver[a].push_back({b, w});
        ver[b].push_back({a, w});
    }
    
    memset(col, -1, sizeof(col));
    read(s);
    for(int i = 1, x; i <= s; i++)
        read(x), col[x] = 0;
    read(p);
    for(int i = 1, x; i <= p; i++)
        read(x), col[x] = 1;
    
    dfs(1, 0);
    
    print("{}", min(f[1][0], f[1][1]));
}

void dfs(int x, int fa)
{
    for(edge i : ver[x])
    {
        if(i.to == fa) continue;
        dfs(i.to, x);
        f[x][0] += min(f[i.to][0], f[i.to][1]+i.cost);
        f[x][1] += min(f[i.to][1], f[i.to][0]+i.cost);
    } 
    if(col[x] != -1) f[x][col[x]^1] = INF;
}

PolarSea 与 IOI

PolarSea 被选入南极洲国家队，代表南极洲参加 IOI。

IOI 共有 $n$ 道题目，主办方赛前公布了一个大小为 $n$ 的可重集 $A$，其中每个元素表示一道题的难度。

对于难度为 $x$ 的题目，PolarSea 需要花费总共 $x$ 分钟才能把这道题 ac。由于 PolarSea 的比赛习惯很差，他从来不打暴力，所以如果他在难度为 $x$ 的题上花的时间 $<x$，这道题它将得不到任何分数。

众所周知，IOI 的题目是按字典序排序的，所以 PolarSea 不知道每道题的难度，只知道它们难度的可重集是 $A$。由于是 IOI 赛制，PolarSea 时刻知道每道题自己是否通过了以及在每道题上已经花的时间。

PolarSea 只有做出至少 $m$ 道题才能拿到 $Au$，作为南极洲领队，你想知道 PolarSea 使用最优策略（不包括打暴力）下最坏要花多长时间才能拿到 $Au$。

Input

输入第一行包含一个整数 $T$，表示数据组数。接下来是 $T$ 组数据。

每组数据的第一行包含两个整数 $n,m$ ，用空格隔开。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示题目难度的可重集，用空格隔开。

Output

对每组数据输出一行，包含一个整数，表示 PolarSea 使用最优策略最坏要花多长时间能通过 $m$ 题。

Hint

$T \le 5, 1 \le m \le n \le 2000, 1 \le a_i \le 10^6$。

Solution

由于最坏情况自己能求出来，所以实时知道自己过了哪些题只能判断当前是否不是最坏情况，那么我们不用管知道自己过了哪些题对策略的影响，就当必然是最坏情况即可。

我们把 $a_i$ 排序，设第 $i$ 道题花费了 $b_i$ 的时间，则最坏情况就是把 $b_i$ 也排序并一一对应。

于是问题变为：给定一个 $n$ 个点 $(i,a_i)$ 构成的右下阶梯，求一个 $n$ 个点 $(i,b_i)$ 构成的右下阶梯，使得有 $m$ 个 $i$ 满足 $a_i=b_i$。

$f(i,j)$ 表示 $a_j = b_j$ 有 $i$ 个位置满足 $k \le j, a_k=b_k$ 的最小代价，转移方程 $f(i,j) = \min_{k<i}\{f(i-1,k) + a_j(j-k)\}$。

直接转移是 $O(Tn^2m)$ 的。使用斜率优化即可做到 $O(Tnm)$。

#include <bits/stdc++.h>
using namespace std;

typedef double db;
const int N = 2005;

int n, m;
int a[N];
int f[N][N];
int st[N], top;

void solve();
db X(int i, int k) { return k; };
db Y(int i, int k) { return f[i-1][k]; }
db slope(int i, int a, int b) { return (Y(i,a)-Y(i,b))/(X(i,a)-X(i,b)); }

signed main()
{
    int t; cin >> t;
    while(t --> 0) solve();
}

void solve()
{
    read(n, m);
    for(int i = 1; i <= n; i++)
        read(a[i]);
    
    sort(a+1, a+n+1, greater<int>());
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    
    for(int i = 1; i <= m; i++)
    {
        st[top=1] = i-1;
        for(int j = i; j <= n; j++)
        {
            while(top > 1 and slope(i, st[top-1], st[top]) > a[j]) top--;
            int k = st[top];
            f[i][j] = f[i-1][k] + a[j]*(j-k);
            while(top > 1 and slope(i, st[top-1], j) > slope(i, st[top], j)) top--;
            st[++top] = j;
        }
    }
    int ans = INT_MAX;
    for(int i = m; i <= n; i++)
        ans = min(ans, f[m][i]);
    print("{}\n", ans);
}