思路

明显的最大权闭合子图，把实验和器材连边，并且变通一下边权，求最大流并记录最小割上的点即可。输入输出略显毒瘤。

代码

// LOJ6001.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2000, INF = 0x3f3f3f3f;
int m, n, s, t, head[MAX_N], current, cur[MAX_N], dep[MAX_N], tmpx;
bool vis[MAX_N];
string tmp;
struct edge
{
    int to, nxt, weight;
} edges[MAX_N << 2];
void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].weight = weight, head[src] = current++;
}
bool bfs()
{
    memset(dep, 0, sizeof(dep)), memset(vis, 0, sizeof(vis));
    queue<int> q;
    q.push(s), dep[s] = 1;
    do
    {
        int u = q.front();
        q.pop(), vis[u] = true;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (edges[i].weight > 0 && !dep[edges[i].to])
                dep[edges[i].to] = dep[u] + 1, q.push(edges[i].to);
    } while (!q.empty());
    return dep[t] != 0;
}
int dfs(int u, int flow)
{
    if (u == t || flow == 0)
        return flow;
    for (int &i = cur[u]; i != -1; i = edges[i].nxt)
        if (dep[edges[i].to] == dep[u] + 1 && edges[i].weight > 0)
        {
            int to = edges[i].to, fl = dfs(to, min(flow, edges[i].weight));
            if (fl > 0)
            {
                edges[i].weight -= fl, edges[i ^ 1].weight += fl;
                return fl;
            }
        }
    return 0;
}
int dinic()
{
    int ans = 0;
    while (bfs())
    {
        for (int i = 1; i <= n + m + 2; i++)
            cur[i] = head[i];
        while (int flow = dfs(s, INF))
            ans += flow;
    }
    return ans;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d\n", &m, &n);
    s = n + m + 1, t = s + 1;
    int ans = 0;
    for (int i = 1; i <= m; i++)
    {
        getline(cin, tmp);
        stringstream ss;
        ss << tmp, ss >> tmpx;
        addpath(s, i, tmpx), addpath(i, s, 0);
        ans += tmpx;
        while (ss >> tmpx)
            addpath(i, tmpx + m, INF), addpath(tmpx + m, i, 0);
    }
    for (int i = 1; i <= n; i++)
        scanf("%d", &tmpx), addpath(i + m, t, tmpx), addpath(t, i + m, 0);
    ans -= dinic();
    queue<int> q;
    for (int i = 1; i <= m; i++)
        if (vis[i])
            q.push(i);
    while (!q.empty())
    {
        int pt = q.front();
        q.pop(), printf("%d", pt);
        if (!q.empty())
            printf(" ");
    }
    puts("");
    for (int i = 1; i <= n; i++)
        if (vis[i + m])
            q.push(i);
    while (!q.empty())
    {
        int pt = q.front();
        q.pop(), printf("%d", pt);
        if (!q.empty())
            printf(" ");
    }
    puts("");
    printf("%d", ans);
    return 0;
}

简述

李超树得名于其发明者——杭州学军中学的李超大神。这个数据结构主要用于解决动态维护（上\下）凸包，是一个非常神仙的东西，主要难点在于处理线段树上的懒惰标记。

算法代码与解释

这个算法有下面几个函数：

• INTERSECT(k1, k2, b1, b2)：求两直线交点的横坐标。
• UPDATE(k, b, l, r, p)：向李超树中加入直线。
• QUERY(qx, l, r, p)：询问当横坐标为\(qx\)时纵坐标的高度。

我们先来思考 UPDATE 操作。考虑以下几种情形：

• 如果我们发现该区间未储存直线，那么我们直接赋值即可。
• 如果我们发现原先有了直线，那么求出两端点上两直线的函数值，待加入直线在\(l\)上的函数值为\(ff\)，在\(r\)上的函数值为\(fb\)，待比较直线在\(l\)上的函数值为\(gf\)，在\(r\)上的函数值为\(gb\)。我们考虑下面几种情况：
  • 如果两直线平行（也就是\(ff,fb\)与\(gf,gb\)有相同的大小关系时），那么我们直接比较高度取最高\最低的直线。
  • 如果两直线有交点，我们求出交点的横坐标\(intx\)，分别进行考虑进行左右儿子更新即可。

例题

// BZ1568.cpp
#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define lson (p << 1)
#define rson ((p << 1) | 1)
using namespace std;
const int MAX_Q = 100020, MAX_N = 50010, ENDPOINT = 50000;
int n, tmpx;
char opt[10];
double lnk[MAX_N << 2], lnb[MAX_N << 2], tmpw, tmpz;
bool tag[MAX_N << 2];
double intersect(double k1, double b1, double k2, double b2) { return 1.0 * (b2 - b1) / (k1 - k2); }
void update(double k, double b, int l, int r, int p)
{
    if (tag[p])
    {
        double ff = k * l + b, gf = lnk[p] * l + lnb[p], fb = k * r + b, gb = lnk[p] * r + lnb[p];
        if (ff <= gf && fb <= gb)
            return;
        else if (ff >= gf && fb >= gb)
        {
            lnk[p] = k, lnb[p] = b;
            return;
        }
        double intx = intersect(k, b, lnk[p], lnb[p]);
        if (ff >= gf)
            if (intx <= mid)
                update(k, b, l, mid, lson);
            else
                update(lnk[p], lnb[p], mid + 1, r, rson), lnk[p] = k, lnb[p] = b;
        else if (intx > mid)
            update(k, b, mid + 1, r, rson);
        else
            update(lnk[p], lnb[p], l, mid, lson), lnk[p] = k, lnb[p] = b;
    }
    else
        lnk[p] = k, lnb[p] = b, tag[p] = true;
}
double query(int qx, int l, int r, int p)
{
    double ans = 0;
    if (tag[p])
        ans = max(ans, 1.0 * qx * lnk[p] + lnb[p]);
    if (l == r)
        return ans;
    if (qx <= mid)
        ans = max(ans, query(qx, l, mid, lson));
    else
        ans = max(ans, query(qx, mid + 1, r, rson));
    return ans;
}
int main()
{
    scanf("%d", &n);
    while (n--)
    {
        scanf("%s", opt + 1);
        if (opt[1] == 'Q')
            scanf("%d", &tmpx), printf("%d\n", (int)(query(tmpx, 1, ENDPOINT, 1) / 100.0));
        else
            scanf("%lf%lf", &tmpw, &tmpz), update(tmpz, tmpw - tmpz, 1, ENDPOINT, 1);
    }
    return 0;
}