Placing Lampposts------UVA10859-----DP

最新推荐文章于 2020-03-14 21:53:23 发布

dr5459

最新推荐文章于 2020-03-14 21:53:23 发布

阅读量1k

点赞数

分类专栏：动态规划

本文链接：https://blog.csdn.net/dr5459/article/details/9412963

版权

动态规划专栏收录该内容

63 篇文章

订阅专栏

题目地址：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1800

题目意思：

给你N个点，M条边

你可以在一个点放灯，或者不放

要求，放尽量少的灯，使所有边亮，使同时被两盏灯照亮的边尽量多，要你输出灯数，被两个灯照亮的变数，只被一个灯照亮的灯数

解题思路：

优化目标有两个，使得灯数a尽量少，使得被两个灯的边数b尽量多

在这里可以转化一下，就是恰被一盏灯照亮的边数c尽量少

下面就是学到的东西了，当我们同时需要优化两个变量a,c，要求首先满足a最小的情况下，使得c尽量小

我们可以引入一个值x=Ma+c，在这里的M是一个很大的值，是一个比c的理论最大值和a的最小理论值之差还要大的值

为什么？因为如果两个a不同的，无论c相差多少，仍然是a起决定性的作用，实在是太聪明了

则我们的目标就是使x的值尽量小，那么x/M的整数部分就是灯数，x%M就是只被一个灯照亮的，m-x%M就是被两个灯照亮的

我们令dp[i][j]表示在i节点，如果j=1表示父亲节点放灯，0则反之，的x的最小值

那么对i来说，有两个决策

如果在i放灯

那么dp[i][j] = sum(dp[k][1])+M，如果j=0且i不是根的话，还要+1，因为i和他的父亲节点这条边只被一个灯照亮

如果在i不放灯，必须j=1（不然边就无法照亮）

那么dp[i][j] = sum(dp[k][0])，如果i不是根，还要加1，因为i和他的父亲节点这条边只被一个灯照亮

通过边DFS边DP的思路就可以把结果求出来

另外还要引入vis，因为这个里面可能不是联通的，那么可能有多棵树，而且加入vis还可以剪枝

下面上代码：

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;

const int maxn = 1010;
const int M = 2000;

vector<int> ma[maxn];
bool vis[maxn][2];
int dp[maxn][2];
int n,m;

int qdp(int i,int j,int fa)
{
    if(vis[i][j])
        return dp[i][j];
    vis[i][j] = true;
    int &ans = dp[i][j];

    //先在i这里放灯
    ans = M;
    //再遍历所有的子树
    for(int k=0;k<ma[i].size();k++)
    {
        if(ma[i][k] != fa)
            ans += qdp(ma[i][k],1,i);
    }
    if(j==0 && fa>=0)
        ans++;

    //再就是在i节点不放,前提条件就是父亲节点放了，或者i就是根
    if(j || fa<0)
    {
        int ans2 = 0;
        for(int k=0;k<ma[i].size();k++)
        {
            if(ma[i][k] != fa)
                ans2 += qdp(ma[i][k],0,i);
        }
        if(fa>=0)
            ans2++;
        ans = min(ans,ans2);
    }

    return ans;
}


int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n;i++)
            ma[i].clear();

        memset(vis,false,sizeof(vis));
        int a,b;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            ma[a].push_back(b);
            ma[b].push_back(a);
        }
        int ans = 0;
        for(int i=0;i<=n;i++)
        {
            if(!vis[i][0])//这里是遇到了一棵新的树，则就将i作为树根，那么他的的父亲节点就是-1
                ans+=qdp(i,0,-1);
        }

        printf("%d %d %d\n",ans/M,m-ans%M,ans%M);

    }
    return 0;
}