A – 家族

这道题真的是送分题（快要想出来直接暴力枚举+并查集的时候去看了题解，最后发现就是这么 sb）。

考虑枚举频段区间\([L, R]\)（将边进行排序，确定下界之后再枚举上界），这个地方是\(O(m^2)\)的。每次枚举下界的时候都要初始化并查集，然后合并两个集合的时候按照大小来修改答案就行了。

// A.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll INF = 0x3f3f3f3f3f3f3f3f, MAX_N = 1010, MAX_E = 5050;

ll n, m, k, ans = INF, fa[MAX_N], current_ans, siz[MAX_N], dat[MAX_N];

struct edge
{
    ll from, to, frequency;
    bool operator<(const edge& e) const { return frequency < e.frequency; }
} edges[MAX_E];

void ufs_initialize()
{
    for (ll i = 1; i <= n; i++)
        fa[i] = i, siz[i] = 1;
}

ll find(ll x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void unite(ll x, ll y) 
{
    x = find(x), y = find(y);
    if (x == y)
        return;
    if (siz[x] < siz[y])
        swap(x, y);
    current_ans -= dat[siz[x]] + dat[siz[y]];
    fa[y] = fa[x], siz[x] += siz[y];
    current_ans += dat[siz[x]];
}

signed main()
{
    scanf("%lld%lld%lld", &n, &m, &k);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &dat[i]);
    for (ll i = 1; i <= m; i++)
        scanf("%lld%lld%lld", &edges[i].from, &edges[i].to, &edges[i].frequency);
    sort(edges + 1, edges + 1 + m);
    for (ll lbound = 1, lower = edges[1].frequency; lbound <= m; lbound++, lower = edges[lbound].frequency)
    {
        ufs_initialize(), current_ans = dat[1] * n;
        for (ll rbound = lbound, upper = edges[rbound].frequency; rbound <= m; rbound++, upper = edges[rbound].frequency)
        {
            ll width = upper - lower;
            unite(edges[rbound].from, edges[rbound].to);
            if (current_ans >= k)
            {
                ans = min(ans, width);
                break;
            }
        }
    }
    if (ans == INF)
        puts("T_T");
    else
        printf("%lld", ans);
    return 0;
}

B – 供电网络

第二题就开始毒瘤了起来，把题意精简之后就是这样的：

给定一个有源汇点的上下界网络，其中每一条边的费用是关于流量的二次关系。求最小费用可行流即可。

首先忽略二次关系，这道题单建模是很简单的，标准的有源汇的上下界可行流模型，根据每个城市的结余连接超级源点和汇点，根据每个城市购入和输出电力的价格连接源点和汇点。

之后，我们可以把连续的二次关系离散化：也就是，恒定流过的流量为\(1\)，然后每次求完最短路、统计答案之后，考虑继续加边：流量上界为\(1\)下界为\(0\)，且费用为当前与上次流过的差值，也就是\(a_i (x + 1)^2 – b_i (x + 1) – a_i x^2 – b_i x_i = 2 a_i x _+ a_i + b_i\)，根据这个式子可以加一条新边。判断是否可行即可。

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 330, MAX_E = 5050, INF = 0x3f3f3f3f;

int n, m, head[MAX_N], current, di[MAX_N], s, t, S, T, answer, flag[MAX_N][MAX_N];
int dist[MAX_N], upward[MAX_N], flow[MAX_N];

bool vis[MAX_N];

struct edge
{
    int to, nxt, weight, cost;
} edges[MAX_E << 1];

struct side
{
    int u, v, a, b, L, R;
} original_data[MAX_E << 1];

void addpath(int src, int dst, int weight, int cost)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].weight = weight, edges[current].cost = cost;
    head[src] = current++;
}

void addtube(int src, int dst, int lower, int upper, int cost, bool doDi = true)
{
    addpath(src, dst, upper - lower, cost), addpath(dst, src, 0, -cost);
    if (doDi)
        di[dst] += lower, di[src] -= lower;
}

bool spfa()
{
    for (int i = 1; i <= m; i++)
        if (flag[original_data[i].u][original_data[i].v] == original_data[i].L && original_data[i].L < original_data[i].R)
        {
            original_data[i].L++;
            addtube(original_data[i].u, original_data[i].v, 0, 1, original_data[i].a * (2 * original_data[i].L - 1) + original_data[i].b, false);
        }
    memset(dist, 0x3f, sizeof(dist));
    queue<int> q;
    q.push(S), dist[S] = 0, vis[S] = true;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (dist[edges[i].to] > dist[u] + edges[i].cost && edges[i].weight > 0)
            {
                dist[edges[i].to] = dist[u] + edges[i].cost, upward[edges[i].to] = i;
                if (!vis[edges[i].to])
                    vis[edges[i].to] = true, q.push(edges[i].to);
            }
    }
    return dist[T] != INF;
}

void find()
{
    int u = T, i = upward[u];
    while (u != S)
    {
        edges[i].weight--, edges[i ^ 1].weight++;
        answer += edges[i].cost;
        flag[edges[i ^ 1].to][edges[i].to]++, flag[edges[i].to][edges[i ^ 1].to]--;
        u = edges[i ^ 1].to, i = upward[u];
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    s = n + 1, t = s + 1, S = t + 1, T = S + 1;
    for (int i = 1, lft, in, out; i <= n; i++)
    {
        scanf("%d%d%d", &lft, &in, &out);
        if (lft > 0)
            addtube(s, i, lft, lft, 0);
        else if (lft < 0)
            addtube(i, t, -lft, -lft, 0);
        addtube(s, i, 0, INF, in), addtube(i, t, 0, INF, out);
    }
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d%d%d%d", &original_data[i].u, &original_data[i].v,
              &original_data[i].a, &original_data[i].b, &original_data[i].L, &original_data[i].R);
        addtube(original_data[i].u, original_data[i].v, original_data[i].L, original_data[i].L, 0);
        answer += original_data[i].L * (original_data[i].a * original_data[i].L + original_data[i].b);
        flag[original_data[i].u][original_data[i].v] += original_data[i].L;
        flag[original_data[i].v][original_data[i].u] -= original_data[i].L;
    }
    // in searching the possible stream;
    addtube(t, s, 0, INF, 0);
    for (int i = 1; i <= t; i++)
        if (di[i] > 0)
            addtube(S, i, 0, di[i], 0);
        else if (di[i] < 0)
            addtube(i, T, 0, -di[i], 0);
    while (spfa())
        find();
    printf("%d", answer);
    return 0;
}

C – 城市规划

等我把多项式和卷积之类的东西全部搞懂再来写这道毒瘤题吧。

Available Here