当前位置：首页 > news >正文

UVa 11751 Installing Diagnostic Software

news 2026/3/27 0:08:30

题目描述

你被任命为一个有线网络的管理员。网络中有nnn个设备（编号000到n−1n-1n−1），由mmm条线路连接。你有一个诊断软件，安装在某个设备上后，可以监控与该设备相连的所有线路。你需要在一些设备上安装这个软件，使得每条线路至少被它的一个端点设备监控。

安装软件的时间因设备而异：在编号为iii的设备上安装需要2i2^i2i单位时间。你只有一份软件拷贝，不能同时安装在多台机器上，因此总安装时间就是所选设备的安装时间之和。

你的目标是最小化总安装时间。

输入格式

每个测试用例以两个整数nnn和mmm开头（1≤n≤10001 \leq n \leq 10001≤n≤1000，0≤m≤250000 \leq m \leq 250000≤m≤25000）。接下来mmm行，每行两个不同的整数uuu和vvv（0≤u,v≤n−10 \leq u, v \leq n-10≤u,v≤n−1），表示一条连接设备uuu和vvv的线路。输入以n=m=0n = m = 0n=m=0结束。

输出格式

对于每个测试用例，输出一行nnn位二进制数（无空格）。第iii位为111表示在设备iii上安装了软件，为000表示未安装。

样例输入

3 2 0 1 1 2 4 3 0 1 2 3 1 2 0 0

样例输出

110 010

题目分析

问题本质

这是一个典型的顶点覆盖问题（Vertex Cover\texttt{Vertex Cover}Vertex Cover）的变种：选择一组顶点，使得每条边至少有一个端点被选。但与经典顶点覆盖不同，这里的顶点有权重，且权重是指数增长的2i2^i2i。

权重特性

安装时间2i2^i2i具有非常重要的性质：

20=12^0 = 120=1
21=22^1 = 221=2
22=42^2 = 422=4
23=82^3 = 823=8
…

关键观察：任何编号较大的节点的代价，大于所有比它编号小的节点代价之和。即：
∑j=0i−12j=2i−1<2i\sum_{j=0}^{i-1} 2^j = 2^i - 1 < 2^ij=0∑i−12j=2i−1<2i

这意味着：

选择一个大节点（如i=3i=3i=3，代价888）永远不如选择所有比它小的节点（代价总和777）
在贪心策略中，我们应该尽可能选择小节点，避免选择大节点

贪心策略的直觉

对于每条边(u,v)(u, v)(u,v)，假设u<vu < vu<v（即uuu是较小节点）：

如果必须选一个端点来覆盖这条边，选uuu（代价2u2^u2u）比选vvv（代价2v2^v2v）更优
如果uuu已经被选，那么这条边已经被覆盖，不需要再选vvv
如果uuu没被选，那么为了覆盖这条边，我们必须选uuu（因为选vvv代价更大）

这个直觉引导我们：对于每条边，优先考虑选较小的端点。

解题思路

算法设计

基于上述分析，我们可以设计如下贪心算法：

边的预处理：对于每条边(a,b)(a, b)(a,b)，将其表示为(((大节点, 小节点)))，即保证第一个分量大于等于第二个分量。
排序：将所有边按大节点从大到小排序。如果大节点相同，则按小节点从大到小排序。
贪心选择：遍历排序后的边。对于当前边(big,small)(\texttt{big}, \texttt{small})(big,small)：
- 如果大节点big\texttt{big}big尚未被选，则选择小节点small\texttt{small}small
- 否则，跳过（这条边已被覆盖）
输出结果：输出nnn位二进制数，表示每个设备是否被选。

为什么按大节点排序？

按大节点从大到小排序的目的是：

优先处理大节点较大的边
这样可以尽早确定大节点是否需要被覆盖
当处理到某条边时，如果它的大节点已经被之前的边覆盖，那么我们可以安全地跳过它

正确性证明

定理：上述贪心算法得到的是最优解。

证明思路：

可行性：算法保证每条边至少有一个端点被选。对于边(big,small)(\texttt{big}, \texttt{small})(big,small)：
- 如果big\texttt{big}big被选，则边被覆盖
- 如果big\texttt{big}big没被选，算法会选small\texttt{small}small，边也被覆盖
最优性：假设存在更优解S∗S^*S∗，考虑算法与S∗S^*S∗的第一个不同选择的边。由于权重指数增长，任何选择大节点而不选小节点的情况都会导致代价更大，因此算法的选择不会劣于最优解。

详细证明可以用数学归纳法或交换论证完成。

时间复杂度

排序：O(mlog⁡m)O(m \log m)O(mlogm)
遍历：O(m)O(m)O(m)
总时间复杂度：O(mlog⁡m)O(m \log m)O(mlogm)，对于m≤25000m \leq 25000m≤25000完全可行

代码实现

// Installing Diagnostic Software// UVa ID: 11751// Verdict: Accepted// Submission Date: 2026-02-26// UVa Run Time: 0.000s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 边的结构体，big 是大节点，small 是小节点structEdge{intbig;intsmall;};// 比较函数：先按 big 降序，big 相同时按 small 降序boolcmp(constEdge&a,constEdge&b){if(a.big!=b.big)returna.big>b.big;returna.small>b.small;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,m;while(cin>>n>>m&&(n||m)){vector<Edge>edges(m);vector<bool>chosen(n,false);// 读入边，并确保 big 是大节点，small 是小节点for(inti=0;i<m;++i){inta,b;cin>>a>>b;if(a>=b){edges[i].big=a;edges[i].small=b;}else{edges[i].big=b;edges[i].small=a;}}// 按 big 从大到小排序sort(edges.begin(),edges.end(),cmp);// 贪心选择：如果大节点没被选，则选小节点for(constauto&e:edges){if(!chosen[e.big]){chosen[e.small]=true;}}// 输出结果for(inti=0;i<n;++i)cout<<(chosen[i]?'1':'0');cout<<'\n';}return0;}