资讯详情

有 \(n\) 个点，点带点权 \(d_i\)，保证 \(\sum d_i=mk\)。

试构造一张 \(m\) 条边的图，使得将每个点的权值任意分配到与之相连的所有边上（即每条与之相连边被分到的权值之和为 \(d_i\)）且每条边的权值（两端点对之分配的权值之和）均为 \(k\)。（允许重边自环）

\[m\ge n-2, n\le500,m\le 5\times10^3,k\le5\times10^3 \]

---

首先，每条边的目标权值都是 \(k\)，因此各条边是等价的。我们对边分配点。

感觉上我们应该尽可能先消耗权值更小的点，因为其“平均”来说需要更多来达到目标权值。

考虑 \(m=n-1\) 的情况。由于我们有 \(n\) 个点，而 \(\sum d=mk\)。

那么对于最小值我们有 \(d_{min} \le \frac{mk}n=\frac{n-1}nk\)。

那么对于最大值我们有 \(d_{max} \ge \frac{mk-d_{min}}{n-1}\)。

对于 \(n\ge 2\) 始终有 \(d_{min}+d_{max}=k+\frac{n-2}{n-1}d_{min}\ge k\)

因此我们只需消耗每次的最小值，若不够则用最大值来补，一定合法。

匹配完一条边后，变为一个 \(n'=n-1\)，\(\sum d'=(n-1)k\) 的子问题，不难发现与原问题形式一致。

那么递归解决即可。

对于 \(m\ge n-1\) 的情况，我们只需额外添加 \(d_i=0\) 的虚点，即可归约到上述问题，且虚点不会被使用，可以合法构造。

---

现在我们来讨论 \(m=n-2\) 的情况。

由于大小为 \(n\) 连通块至少包含 \(n-1\) 条边。\(m-2\) 时图至少由两个连通块构成。

因此假如最终存在合法的构造 \(G\)，我们可以将 \(G\) 划分为两个子图 \(G_1,G_2\)，其均满足 \(m'=n'-1\)，\(\sum d'=m'k\)。

回到原问题，这意味着我们需要找到 \(S=[1,n]\) 的一个子集，使得 \(\sum_{i\in S} d_i=(|S|-1)k\)。

整理得

\[\sum_{i\in S}(k-d_i)=k \]

不难发现这是一个 01 背包问题，bitset 优化即可做到 \(\mathcal O(\dfrac{nmk}\omega)\)。

#include <algorithm>
#include <iostream>
#include <bitset>
#include <vector>const int N = 507;
#define rep(i,a,b) for(int i(a);i<=(b);++i)int n, m, k;
int d[5007];inline void solveE(const std::basic_string<int>& g, int m) {rep(i, 1, m) {int min = -1, max = -1;for(auto& i: g) {if(d[i] > 0) { max = min = i; break; }}for(auto& i: g) {if(d[i] == 0) continue;if(d[i] < d[min]) min = i;if(d[i] >= d[max]) max = i;}if(min == -1 || max == -1) exit(-7);std::cout << min << ' ' << std::min(d[min], k);if(d[min] < k) {int t = k - d[min];d[min] = 0;std::cout << " " << max << ' ' << t << "\n";d[max] -= t;} else {d[min] -= k;std::cout << "\n";}}
}const int T = 6e6;
std::bitset<T> bs[N];inline void solveH() {// sum(k-t) = kbs[0][T / 2] = 1;int p = 0;rep(i, 1, n) {int t = k - d[i];if(t > 0) bs[i] = bs[i-1] | (bs[i-1] << t);else if(t < 0) bs[i] = bs[i-1] | (bs[i-1] >> -t);else bs[i] = bs[i-1];if(bs[i][k + T/2]) { p = i; break; }}if(p == 0) { std::cout << "-1\n"; return ; }int w = k;static int flag[N];rep(i, 1, n) flag[i] = 0;for(int i = p; i >= 1; --i) {if(bs[i-1][w + T/2]) continue;w = w - (k - d[i]), flag[i] = 1;}std::basic_string<int> r1, r2;rep(i, 1, n) (flag[i] ? r1 : r2) += i;solveE(r1, r1.size() - 1), solveE(r2, r2.size() - 1);
}inline void solve() {std::cin >> n >> m >> k;rep(i, 1, n) std::cin >> d[i]; if(m >= n-1) {std::basic_string<int> res;rep(i, 1, n) res += i;solveE(res, m);} else solveH();
}int main() {std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);int t; std::cin >> t; while(t--) solve();
}