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 – 城市规划
等我把多项式和卷积之类的东西全部搞懂再来写这道毒瘤题吧。