该题给出N个点M条边的无向无环图,在尽量少的节点上放灯,使得所有边都被照亮,每个节点将照亮与它相连的边。在放灯数量最少的前提下要求被两盏灯同时照亮的的边数应尽量大。
该题难点在于如何同时做到放灯最少和被两栈等同时照亮的最大。
首先统一到 “求最小” 的问题中来,问题转化为:在放灯数x最少的情况下使得仅被一条个等照亮的边数c最小。
定义一个较大的数M,使其超过题目情况中 c 的和的上界,该题可定义为2000.
则把状态转换为使得 M * x + c 最小。
那么最后放灯数应该是 ans / M, 仅被一个灯照亮的边数为: ans % M
还是忍不住贴个代码。。
# include <cstdio> # include <cstring> # include <algorithm> # define rep(i, n) for (int i = 0; i < n; ++i ) using namespace std; const int M = 2000; int n, m; struct edge { int v, next; }e[2009]; int h[1003], tot; void add(int a, int b) { e[++tot].v = b; e[tot].next = h[a]; h[a] = tot; } bool v[2003]; int f[2003][2]; void dfs(int x, int fa) { int j; v[x] = true; f[x][0] = 0; f[x][1] = M; for (int i = h[x]; i; i = e[i].next) { j = e[i].v; if ( !v[j] ) dfs(j, x); if ( j == fa ) continue; f[x][1] += min(f[j][0] + 1, f[j][1]); f[x][0] += f[j][1] + 1; } } int main() { int t, a, b; scanf("%d", &t); while ( t-- ) { memset(h, 0, sizeof h); memset(v, false, sizeof v); tot = 0; scanf("%d%d", &n, &m); rep(i, m) { scanf("%d%d", &a, &b); add(a, b); add(b, a); } int ans = 0; rep(i, n) if ( !v[i] ) { dfs(i, -1); ans += min(f[i][0], f[i][1]); } printf("%d %d %d\n", ans/M, m - ans % M, ans % M); } return 0; }