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

[BZOJ 1040] 骑士

Link:

BZOJ 1040 传送门

Solution:

基环树$dp$

如果仅仅是一棵树,直接树形$dp$即可,维护选与不选两种状态下的方案数

但此题是一个基环树,即除了一个环外是一个树形结构

 

对于环,一般都是将环转化为链处理

我们只需要删掉环上的任意一条边即可将环转化为树,那我们只需要人为判断这条边对答案的贡献就行了

设这条边是$(u,v)$,那么有2种情况

1.不选$u$,那么$v$选不选都行,以$u$为根跑一遍树形$dp$

2.不选$v$,那么$u$选不选都行,以$v$为根跑一遍树形$dp$

 

建图有两种方式:

Solution A:

先将原图建好,$dfs$找到返祖边,删除返祖边

Solution B:

在连边时用并查集维护,如果出现环则不连这条边

 

Solution B 跑得更快些

Code:

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN=1e6+10;

bool vis[MAXN],flag=false;
int n,l,r,dat[MAXN],mat[MAXN];
ll dp[MAXN][2],res=0;
vector<int> G[MAXN];

void dfs(int x,int anc)
{
    vis[x]=true;
    for(int i=0;i<G[x].size() && !flag;i++)
    {
        int v=G[x][i];
        if(v==anc) continue;
        if(vis[v]) 
        {
            flag=true;
            G[x].erase(find(G[x].begin(),G[x].end(),v));
            G[v].erase(find(G[v].begin(),G[v].end(),x));
            l=x;r=v;break;
        }
        dfs(v,x);
    }
}

void Trdp(int x,int anc,int ban)
{
    vis[x]=true;
    if(x==ban) dp[x][1]=0;
    else dp[x][1]=dat[x];
    dp[x][0]=0;
    for(int i=0;i<G[x].size();i++)
    {
        int v=G[x][i];
        if(v==anc) continue;
        Trdp(v,x,ban);
        dp[x][0]+=max(dp[v][0],dp[v][1]);
        dp[x][1]+=dp[v][0];
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&dat[i],&mat[i]);
        G[i].push_back(mat[i]);G[mat[i]].push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[i]) continue;
        ll t=0;flag=false;dfs(i,0);
        Trdp(l,0,r);t=max(dp[l][0],dp[l][1]);
        Trdp(r,0,l);t=max(t,max(dp[r][0],dp[r][1]));
        res+=t;
    }
    printf("%lld",res);
    return 0;
}
Solution A
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN=1e6+10;

vector<int> G[MAXN];
ll dp[MAXN][2],res=0,t=0;
int f[MAXN],n,x,dat[MAXN],l[MAXN],r[MAXN],cnt=0;

int find(int x){return (x==f[x])?x:(f[x]=find(f[x]));}
void Trdp(int x,int anc)
{
    dp[x][0]=0;dp[x][1]=dat[x];
    for(int i=0;i<G[x].size();i++)
    {
        int v=G[x][i];
        if(v==anc) continue;
        Trdp(v,x);
        dp[x][0]+=max(dp[v][1],dp[v][0]);
        dp[x][1]+=dp[v][0];
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&dat[i],&x);
        if(find(i)!=find(x))
        {
            G[x].push_back(i);G[i].push_back(x);
            f[f[i]]=f[x];
        }
        else l[++cnt]=i,r[cnt]=x;
    }
    for(int i=1;i<=cnt;i++)
    {
        Trdp(l[i],0);t=dp[l[i]][0];
        Trdp(r[i],0);t=max(t,dp[r[i]][0]);
        res+=t;
    }
    printf("%lld",res);
    return 0;
}
Solution B

 

Review:

1、处理环的常用方式:将环转化为链

 

2、用并查集维护点集的方式寻找环的效率更高

 

转载于:https://www.cnblogs.com/newera/p/9248351.html

相关文章:

  • mongodb的python访问_python 连接mongodb 使用
  • 实现去哪网中的头部布局
  • 向量点积衡量相似度_点积相似度、余弦相似度、欧几里得相似度
  • document.querySelector()与document.querySelectorAll()
  • html5静默打印_解答:如何实现在打印窗体内容是不弹出打印设置框从而实现静默打印的呢?...
  • Windows下vue-cli脚手架搭建入门一
  • cython 安装升级_20个小招数教你如果快速完成Python 性能优化升级
  • [NOI 2016]循环之美
  • finereport连接oracle_FineReport连接多维数据库示例及操作
  • linux 扩展挂载盘大小_Linux下使用fdisk扩展分区容量
  • JavaScript (function (){}()) 与(function(){})()
  • python assert 不退出_Pytest中断言的重要性,就不需要我重复了吧
  • IDEA中Lombok插件的安装与使用
  • python坦克大战_python资料领取:尚学堂201903期python全栈(0基础到就业)
  • 【leetcode】88. 合并两个有序数
  • 【知识碎片】第三方登录弹窗效果
  • CSS3 聊天气泡框以及 inherit、currentColor 关键字
  • Docker容器管理
  • ES2017异步函数现已正式可用
  • Iterator 和 for...of 循环
  • JS变量作用域
  • Linux下的乱码问题
  • MySQL Access denied for user 'root'@'localhost' 解决方法
  • Spring Cloud Feign的两种使用姿势
  • Sublime text 3 3103 注册码
  • 从0实现一个tiny react(三)生命周期
  • 动手做个聊天室,前端工程师百无聊赖的人生
  • 高程读书笔记 第六章 面向对象程序设计
  • 构建二叉树进行数值数组的去重及优化
  • 前端相关框架总和
  • 前端性能优化--懒加载和预加载
  • 协程
  • 由插件封装引出的一丢丢思考
  • Spring Batch JSON 支持
  • ​​​​​​​​​​​​​​汽车网络信息安全分析方法论
  • ​什么是bug?bug的源头在哪里?
  • (第二周)效能测试
  • (附源码)ssm户外用品商城 毕业设计 112346
  • (九)One-Wire总线-DS18B20
  • (强烈推荐)移动端音视频从零到上手(下)
  • (三)mysql_MYSQL(三)
  • (五)IO流之ByteArrayInput/OutputStream
  • (转)全文检索技术学习(三)——Lucene支持中文分词
  • *Django中的Ajax 纯js的书写样式1
  • .NET / MSBuild 扩展编译时什么时候用 BeforeTargets / AfterTargets 什么时候用 DependsOnTargets?
  • .NET 2.0中新增的一些TryGet,TryParse等方法
  • .NET 8 编写 LiteDB vs SQLite 数据库 CRUD 接口性能测试(准备篇)
  • .NET 材料检测系统崩溃分析
  • .xml 下拉列表_RecyclerView嵌套recyclerview实现二级下拉列表,包含自定义IOS对话框...
  • /bin、/sbin、/usr/bin、/usr/sbin
  • ?.的用法
  • @Documented注解的作用
  • [C#]DataTable常用操作总结【转】
  • [java面试]宇信易诚 广州分公司 java笔试题目回忆录
  • [jQuery]使用jQuery.Validate进行客户端验证(中级篇-上)——不使用微软验证控件的理由...