题目大意:给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)的更多相关文章
-
HDU 4126 Genghis Khan the Conqueror MST+树形dp
题意: 给定n个点m条边的无向图. 以下m行给出边和边权 以下Q个询问. Q行每行给出一条边(一定是m条边中的一条) 表示改动边权. (数据保证改动后的边权比原先的边权大) 问:改动后的最小生成树的权 ...
-
HDU 4126 Genghis Khan the Conqueror 最小生成树+树形dp
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4126 Genghis Khan the Conqueror Time Limit: 10000/50 ...
-
hdu4756 Install Air Conditioning(MST + 树形DP)
题目请戳这里 题目大意:给n个点,现在要使这n个点连通,并且要求代价最小.现在有2个点之间不能直接连通(除了第一个点),求最小代价. 题目分析:跟这题一样样的,唉,又是原题..先求mst,然后枚举边, ...
-
hdu4126Genghis Khan the Conqueror (最小生成树+树形dp)
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 327680/327680 K (Java/Others) Total Submiss ...
-
MST + 树形 dp
Genghis Khan(成吉思汗)(1162-1227), also known by his birth name Temujin(铁木真) and temple name Taizu(元太祖), ...
-
hdu 4756 MST+树形dp ****
题意:给你n(n = 1000)个二维点,第一个点是power plant,还有n - 1个点是dormitories.然后现在知道有一条寝室到寝室的边是不能连的,但是我们不知道是哪条边,问这种情况下 ...
-
HDU 4756 Install Air Conditioning (MST+树形DP)
题意:n-1个宿舍,1个供电站,n个位置每两个位置都有边相连,其中有一条边不能连,求n个位置连通的最小花费的最大值. 析:因为要连通,还要权值最小,所以就是MST了,然后就是改变一条边,然后去找出改变 ...
-
hdu4126(MST + 树形dp
题意: 这个题目和hdu4756差不多,是给你一个图,然后是q次改变边的权值,权值只增不减,最后问你每次改变之后的最小树的平均值是多少. 思路:(prim+树形dp) 先跑一边 ...
-
HDU-4126 Genghis Khan the Conqueror 树形DP+MST (好题)
题意:给出一个n个点m条边的无向边,q次询问每次询问把一条边权值增大后问新的MST是多少,输出Sum(MST)/q. 解法:一开始想的是破圈法,后来想了想应该不行,破圈法应该只能用于加边的情况而不是修 ...
随机推荐
-
ASP.net Core部署说明(Ubuntu) [转]
最近在学习asp.net core,当然学习的目的是想了解一下,Asp.net core是否真的能够是先跨平台部署. 根据目前官网资料说明,asp.net core只有在Redhat 企业版上,才能够 ...
-
C# DateTime.ToString的坑
当需要将时间类型转换为字符串类型时,一般直接使用datetime.ToString()方法即可 1.直接使用ToString(),不带任何参数,代码如下 static void Main(string ...
-
原生 js 写分页
欢迎留言或者加本人QQ172360937咨询 这段代码是用原生 js 写的一个分页的效果 <!doctype html> <html lang="en"> ...
-
BizTalk开发系列(三) 单机环境下的BizTalk Server 2006 R2安装
大部分的开发环境都是在单机环境下进行的,今天整理了一下BizTalk Server 2006 R2在单机环境下的安装步骤. 1. 软件需求 在独立服务器中完整安装BizTalk Server 2006 ...
-
字符串匹配--Karp-Rabin算法
主要特征 1.使用hash函数 2.预处理阶段时间复杂度O(m),常量空间 3.查找阶段时间复杂度O(mn) 4.期望运行时间:O(n+m) 本文地址:http://www.cnblogs.com/a ...
-
http://blog.csdn.net/jiazimo/article/details/17265061
http://blog.csdn.net/jiazimo/article/details/17265061
-
SQL Server 索引视图 聚簇索引
创建示例: 朋友的网站速度慢,让我帮忙看下,他用的SQL Server里面 有一个文章表里面有30多万条记录 还有一个用户表里面也差不多17万记录 偏偏当初设计的时候没有冗余字段 很多帖子信息需要JO ...
-
docker 中运行 redis 服务
先使用 dockerfile 创建一个 redis 容器 FROM ubuntu:latest RUN apt-get update RUN apt-get -y install redis-serv ...
-
C++虚函数表原理
C++中的虚函数的作用主要是实现了多态的机制.关于多态,简而言之就是用父类型别的指针指 向其子类的实例,然后通过父类的指针调用实际子类的成员函数.这种技术可以让父类的指针有“多种形态”,这是一种泛型技 ...
-
TextView 设置超过几行后显示省略号
android:lines="5" android:ellipsize="end"