hdu4126Genghis Khan the ConquerorGenghis Khan the Conqueror(MST+树形DP)

时间:2022-04-22 00:44:13

题目请戳这里

题目大意:给n个点,m条边,每条边权值c,现在要使这n个点连通。现在已知某条边要发生突变,再给q个三元组,每个三元组(a,b,c),(a,b)表示图中可能发生突变的边,该边一定是图中的边。c表示该边新的权值,c只可能比原来的权值大。给的q条边发生突变的概率是一样的。求突变后连通n个点最小代价期望值。

题目分析:如果没有那条突变的边,就是求一个mst。但是因为有一条边要突变,每条边突变的概率相同,都为1/q。所以要枚举所有的q条边,求出该边突变后最小生成树代价。q条边分2类:一类是生成树中的边,第二类不是生成树中的边。

第二类边很好处理,既然本身不是生成树中的边。那么这条边突变后权值变大,现在要使权值最小,这条边不选就是了,所以总代价依然是原图的mst。

第一类边发生突变的话,那么去掉这条边后原来的mst就被分成了2个子树,所以我们要找到解决办法就是寻找这2个子树之间的次短边(最小边是去掉的那条生成树中的边)。比较一下,如果这条次短边的权值小于这条突变的生成树上的边,那么就要换掉这条边,否则保留。

现在的关键是求去掉某条边生成树边后,2个子树的最小距离。很容易想到一个O(n^3)的算法:枚举每条生成树边(u,v),分别从u和v开始沿着生成树边遍历,求出两两点间最小值。可是复杂度未免太高。借助dp的思想,可以将这个过程复杂度降一个n。

考虑次过程的这样一个性质:求某个点i到以点j为根的树的最短距离=min(i到j所有子树的最短距离,i到j的最短距离),那么可以枚举起点i,从i点开始沿着mst的边dfs,每经过一条边,那么这条边可以将n个点分成2部分,一部分含i,另一部分不含i(废话),利用dfs的性质,对于从i出发沿着生成树的边遍历到的每个点,当要离开这个点的时候,保证其所有的子树都已经遍历完毕,那么i到j的子树的最短距离就确定了,那么以到达j的边为割边,i到j这颗子树的最短距离就有了。每一次从i点的dfs表示的是枚举割边后包含i的子树和不包含i的子树之间的最小距离。枚举每个点,就能得到对于所有生成树的边,dp[u][v]表示以(u,v)为割边的两颗子树的最短距离。

好NB的DP!

汉语组织的可能不是很好,具体画图吧,好容易懂的。

详情请见代码:

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 3005;
const int M = 1000005;
const int inf = 0x3f3f3f3f;
int dp[N][N],dis[N][N],cost[N][N],lowcost[N],pre[N];
bool used[N][N],flag[N];
int head[N],num;
double ans;
int n,m,q,mst;
struct node
{
int to,next;
}e_mst[M];
void build(int s,int e)
{
e_mst[num].to = e;
e_mst[num].next = head[s];
head[s] = num ++;
}
void prim()
{
int i,j;
mst = 0;
memset(flag,false,sizeof(flag));
for(i = 0;i < n;i ++)
{
lowcost[i] = dis[0][i];
pre[i] = 0;
}
flag[0] = true;
for(i = 1;i < n;i ++)
{
int minn = inf;
int v;
for(j = 0;j < n;j ++)
{
if(lowcost[j] < minn && flag[j] == false)
{
minn = lowcost[j];
v = j;
}
}
mst += minn;
used[pre[v]][v] = used[v][pre[v]] = true;
build(pre[v],v);
build(v,pre[v]);
flag[v] = true;
for(j = 0;j < n;j ++)
{
if(flag[j] == false && lowcost[j] > dis[v][j])
{
lowcost[j] = dis[v][j];
pre[j] = v;
}
}
}
}
int dfs(int cur,int u,int fa)//用cur更新cur点所在的子树和另外子树的最短距离
{
int ret = inf;
for(int i = head[u];~i;i = e_mst[i].next)//沿着生成树的边遍历
{
if(e_mst[i].to == fa)
continue;
int tmp = dfs(cur,e_mst[i].to,u);//用cur更新的以当前边(u,e_mst[i].to)为割边的两个子树最短距离
ret = min(tmp,ret);//以(fa,u)为割边的2个子树的最短距离
dp[u][e_mst[i].to] = dp[e_mst[i].to][u] = min(dp[u][e_mst[i].to],tmp);
}
if(fa != cur)//生成树边不更新
ret = min(ret,dis[cur][u]);
return ret;
}
void solve()
{
int i,j;
int a,b,c;
int sum = 0;
memset(head,-1,sizeof(head));
num = 0;
prim();
for(i = 0;i < n;i ++)
dfs(i,i,-1);
scanf("%d",&q);
for(i = 0;i < q;i ++)
{
scanf("%d%d%d",&a,&b,&c);
if(used[a][b])
{
if(c < dp[a][b])
sum += (mst - dis[a][b] + c);
else
sum += (mst - dis[a][b] + dp[a][b]);
}
else
sum += mst;
}
ans = (double)sum/(double)q;
printf("%.4lf\n",ans);
}
int main()
{
int i,j,a,b,c;
while(scanf("%d%d",&n,&m),(m + n))
{
for(i = 0;i < n;i ++)
for(j = 0;j < n;j ++)
{
dp[i][j] = inf;
used[i][j] = false;
if(i == j)
dis[i][j] = 0;
else
dis[i][j] = inf;
}
for(i = 0;i < m;i ++)
{
scanf("%d%d%d",&a,&b,&c);
dis[a][b] = dis[b][a] = c;
}
solve();
}
return 0;
}
//921MS 80028K

hdu4126Genghis Khan the ConquerorGenghis Khan the Conqueror(MST+树形DP)的更多相关文章

  1. HDU 4126 Genghis Khan the Conqueror MST&plus;树形dp

    题意: 给定n个点m条边的无向图. 以下m行给出边和边权 以下Q个询问. Q行每行给出一条边(一定是m条边中的一条) 表示改动边权. (数据保证改动后的边权比原先的边权大) 问:改动后的最小生成树的权 ...

  2. HDU 4126 Genghis Khan the Conqueror 最小生成树&plus;树形dp

    题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4126 Genghis Khan the Conqueror Time Limit: 10000/50 ...

  3. hdu4756 Install Air Conditioning&lpar;MST &plus; 树形DP&rpar;

    题目请戳这里 题目大意:给n个点,现在要使这n个点连通,并且要求代价最小.现在有2个点之间不能直接连通(除了第一个点),求最小代价. 题目分析:跟这题一样样的,唉,又是原题..先求mst,然后枚举边, ...

  4. hdu4126Genghis Khan the Conqueror &lpar;最小生成树&plus;树形dp&rpar;

    Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 327680/327680 K (Java/Others) Total Submiss ...

  5. MST &plus; 树形 dp

    Genghis Khan(成吉思汗)(1162-1227), also known by his birth name Temujin(铁木真) and temple name Taizu(元太祖), ...

  6. hdu 4756 MST&plus;树形dp &ast;&ast;&ast;&ast;

    题意:给你n(n = 1000)个二维点,第一个点是power plant,还有n - 1个点是dormitories.然后现在知道有一条寝室到寝室的边是不能连的,但是我们不知道是哪条边,问这种情况下 ...

  7. HDU 4756 Install Air Conditioning &lpar;MST&plus;树形DP&rpar;

    题意:n-1个宿舍,1个供电站,n个位置每两个位置都有边相连,其中有一条边不能连,求n个位置连通的最小花费的最大值. 析:因为要连通,还要权值最小,所以就是MST了,然后就是改变一条边,然后去找出改变 ...

  8. hdu4126&lpar;MST &plus; 树形dp

    题意:       这个题目和hdu4756差不多,是给你一个图,然后是q次改变边的权值,权值只增不减,最后问你每次改变之后的最小树的平均值是多少. 思路:(prim+树形dp)       先跑一边 ...

  9. HDU-4126 Genghis Khan the Conqueror 树形DP&plus;MST &lpar;好题&rpar;

    题意:给出一个n个点m条边的无向边,q次询问每次询问把一条边权值增大后问新的MST是多少,输出Sum(MST)/q. 解法:一开始想的是破圈法,后来想了想应该不行,破圈法应该只能用于加边的情况而不是修 ...

随机推荐

  1. ASP&period;net Core部署说明(Ubuntu) &lbrack;转&rsqb;

    最近在学习asp.net core,当然学习的目的是想了解一下,Asp.net core是否真的能够是先跨平台部署. 根据目前官网资料说明,asp.net core只有在Redhat 企业版上,才能够 ...

  2. C&num; DateTime&period;ToString的坑

    当需要将时间类型转换为字符串类型时,一般直接使用datetime.ToString()方法即可 1.直接使用ToString(),不带任何参数,代码如下 static void Main(string ...

  3. 原生 js 写分页

    欢迎留言或者加本人QQ172360937咨询 这段代码是用原生 js 写的一个分页的效果 <!doctype html> <html lang="en"> ...

  4. BizTalk开发系列&lpar;三&rpar; 单机环境下的BizTalk Server 2006 R2安装

    大部分的开发环境都是在单机环境下进行的,今天整理了一下BizTalk Server 2006 R2在单机环境下的安装步骤. 1. 软件需求 在独立服务器中完整安装BizTalk Server 2006 ...

  5. 字符串匹配--Karp-Rabin算法

    主要特征 1.使用hash函数 2.预处理阶段时间复杂度O(m),常量空间 3.查找阶段时间复杂度O(mn) 4.期望运行时间:O(n+m) 本文地址:http://www.cnblogs.com/a ...

  6. http&colon;&sol;&sol;blog&period;csdn&period;net&sol;jiazimo&sol;article&sol;details&sol;17265061

    http://blog.csdn.net/jiazimo/article/details/17265061

  7. SQL Server 索引视图 聚簇索引

    创建示例: 朋友的网站速度慢,让我帮忙看下,他用的SQL Server里面 有一个文章表里面有30多万条记录 还有一个用户表里面也差不多17万记录 偏偏当初设计的时候没有冗余字段 很多帖子信息需要JO ...

  8. docker 中运行 redis 服务

    先使用 dockerfile 创建一个 redis 容器 FROM ubuntu:latest RUN apt-get update RUN apt-get -y install redis-serv ...

  9. C&plus;&plus;虚函数表原理

    C++中的虚函数的作用主要是实现了多态的机制.关于多态,简而言之就是用父类型别的指针指 向其子类的实例,然后通过父类的指针调用实际子类的成员函数.这种技术可以让父类的指针有“多种形态”,这是一种泛型技 ...

  10. TextView 设置超过几行后显示省略号

    android:lines="5" android:ellipsize="end"