[UVa10859 – Placing Lampposts]DP状态表示的转换。

该题给出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;
}

[UVa10859 – Placing Lampposts]DP状态表示的转换。》上有1条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>