自动搬运

查看原文

来自洛谷，原作者为

	uuku **

搬运于2025-08-24 22:39:28，当前版本为作者最后更新于2022-07-13 22:55:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

不难发现，每个小镇花费的价钱只与该小镇建了多少条公路有关，与和哪个小镇建的无关。而每个小镇修建的条数就是最后生成的途中该点的度数，记为 $du_i$。

所以我们不妨从每个小镇的角度进行求解。将每个小镇修建下一条公路的代价排序后取最小值。显然修建 $m$ 条道路，即 $\sum\limits_{i=1}^n du_i=2m$。所以只需取 $2m$ 次最小值即可。

上述过程可以用堆维护。

但是还没结束，还要满足图连通和没有自环两个条件。

图连通的一个显然的必要条件是 $\forall i \in [1,n],du_i>0$。

无自环的一个显然的必要条件是 $\forall i \in [1,n],du_i\le m$。

下面给出构造方案以证明充分性：

我们只需不断的将当前度数最小值的点连向度数最大值的点即可。

证明连通性

考虑当当前的度数最小值是 $1$ 时，连了这条边之后它将无法再和其它点连边。但是连了这条边之后，它将和当前的度数最大的点连通。

而之前和它连通的点（可能没有），也会间接的和剩下的点连通。

也就是说每个度数变为 $0$ 的点都会直接或间接的和当前剩下的度数不为 $0$ 的点连通。

所以最终这 $n$ 个点会连通。

证明无自环

考虑用反证法，假设最终会产生自环，即 $\exists i \in [1,n],du_i>0$。而由于总度数是偶数，每次连边也会使总度数减 $2$。所以 $du_i\ge 2$ 且 $du_i \bmod 2=0$。

$i$ 会有两种情况：

1. $du_i$ 一直是最大值，那么意味着一直是将 $i$ 与其他点连边，即 $du_i>2m-du_i$，这与上面要求的 $du_i\le m$ 矛盾。

2. 存在 $j$，满足在最开始时 $du_j>du_i$。那么当 $du_j$ 减到 $du_i$ 时，根据上述过程不难发现，在此之后会满足 $|du_i-du_j|\le 1$。而根据假设此时 $du_i-du_j\ge 2$。产生矛盾。

所以假设不成立，即最后不会产生自环。

时间复杂度 $O(m\log n)$

示例代码：

#define pli pair<ll,int>
const int N = 2e5 + 10;
int n, m, du;
ll ans;
struct P{
	int id, a, b, c, cnt;
	inline void rd(int i){id = i, cin >> a >> b >> c;}
	inline ll get(){cnt++; return (1ll * a * cnt + b) * cnt + c;}
} v[N];
priority_queue<pli, vector<pli>, greater<pli>> q;
pli now;
inline bool cmp(P x, P y){return x.cnt > y.cnt;}
int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> m, du = m << 1;
	for(int i = 1; i <= n; ++i) v[i].rd(i);
	
	for(int i = 1; i <= n; ++i) ans += v[i].get();
	du -= n;
	
	for(int i = 1; i <= n; ++i) q.push(make_pair(v[i].get(), i));
	
	while(du--)
	{
		now = q.top(), q.pop();
		ans += now.first;
		if(v[now.second].cnt == m){v[now.second].cnt++;continue;}
		q.push(make_pair(v[now.second].get(), now.second));		
	}
	for(int i = 1; i <= n; i++) v[i].cnt--; 
	
	cout<<ans<<'\n';
	
	sort(v + 1, v + n  + 1, cmp);
	int l = 1, r = n;
	while(v[r].cnt == 0) r--;
	while(l < r)
	{
		if(v[1].cnt == 1)break;
		cout<<v[r].id<<' '<<v[l].id<<'\n';
		v[r].cnt--, v[l].cnt--;
		l++;
		if(v[l].cnt <= v[1].cnt && v[1].cnt) l = 1;
		if(!v[r].cnt) r--;
		if(l == r && v[l].cnt)swap(v[l], v[1]), l = 1;
	}
	if(v[1].cnt)
	{
		for(int i = 2; i <= n; i++)
			if(v[i].cnt)
			{
				cout<<v[i].id<<' '<<v[i-1].id<<"\n";
				v[i].cnt--, v[i-1].cnt--;
			}
	}
	return 0;
}

赛时选手提供的爆标思路

同样只考虑每个点的度数，显然会有一个最大值，我们不妨直接二分这个最大值。然后可以用二次函数求根公式快速计算每个点选了多少次。然后判断总度数是否达到 $2m$ 且每个点度数仍符合上述条件即可。复杂度可以做到 $O(n\log V+m)$。