UvaLive 6534 Join two kingdoms 树形DP+二分
来源：程序员人生 发布时间：2014-10-04 08:00:00 阅读次数：3297次
链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4545
题意：两个国家A，B，分别有N座城市和Q座城市(1 ≤ N, Q ≤ 4 × 10^4)，每个国家里的城市都是树形结构，每条边的权值都是1。现在要随机从两个国家中各选择一个城市来将两个国家连接起来，问连接起来的大国家里面的最长路的期望是多少。
思路：首先用树形DP找出所有点在本国里的能找到的最远距离，并且记录所有最远距离里的最长距离len。然后将B的所有最长路排序，并且对于A的每座城市，当A选择该座城市时，对于B的每座城市得到的最长路是max（len,dp_a[i][0]+dp_b[j][0]+1)，其中dp_a[i][0],dp_b[j][0]分别代表这两座城市能找到的最远距离。用二分找到满足dp_a[i][0]+dp_b[j][0]+1>len的位置，比这个位置大的长度就是dp_a[i][0]+dp_b[j][0]+1,起来的就是len。这样就可以求得期望了。
代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 40005
#define PI acos(-1.0)
#define seed 31//131,1313
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int from_a[maxn],head_a[maxn],top_a;
int from_b[maxn],head_b[maxn],top_b;
double dp_a[maxn][2], dp_b[maxn][2];
double aa[maxn],bb[maxn];
struct Edge
{
int v;
int next;
} edge_a[maxn*2],edge_b[maxn*2];
void init()
{
memset(head_a,-1,sizeof(head_a));
memset(dp_a,0,sizeof(dp_a));
memset(head_b,-1,sizeof(head_b));
memset(dp_b,0,sizeof(dp_b));
top_a=0;
top_b=0;
}
void add_edge_a(int u,int v)
{
edge_a[top_a].v=v;
edge_a[top_a].next=head_a[u];
head_a[u]=top_a++;
}
void add_edge_b(int u,int v)
{
edge_b[top_b].v=v;
edge_b[top_b].next=head_b[u];
head_b[u]=top_b++;
}
void dfs_first(int u,int f,int head[],Edge edge[],int from[],double dp[][2])
{
from[u]=u;
for(int i=head[u]; i!=-1; i=edge[i].next)
{
int v=edge[i].v;
if(v==f)
continue;
dfs_first(v,u,head,edge,from,dp);
if(dp[v][0]+1>dp[u][0])
{
from[u]=v;
dp[u][1]=dp[u][0];
dp[u][0]=dp[v][0]+1;
}
else if(dp[v][0]+1>dp[u][1])
dp[u][1]=dp[v][0]+1;
}
}
void dfs_second(int u,int f,int from[],double dp[][2],int head[],Edge edge[])
{
if(u!=f)
if(from[f]!=u)
{
if(dp[f][0]+1>dp[u][0])
{
from[u]=f;
dp[u][1]=dp[u][0];
dp[u][0]=dp[f][0]+1;
}
else if(dp[f][0]+1>dp[u][1])
dp[u][1]=dp[f][0]+1;
}
else
{
if(dp[f][1]+1>dp[u][0])
{
from[u]=f;
dp[u][1]=dp[u][0];
dp[u][0]=dp[f][1]+1;
}
else if(dp[f][1]+1>dp[u][1])
dp[u][1]=dp[f][1]+1;
}
for(int i=head[u]; i!=-1; i=edge[i].next)
{
int v=edge[i].v;
if(v==f)
continue;
dfs_second(v,u,from,dp,head,edge);
}
}
int main()
{
int T_a,T_b;
while(~scanf("%d%d",&T_a,&T_b))
{
init();
for(int i=1;i<=T_a-1;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge_a(u,v);
add_edge_a(v,u);
}
dfs_first(1,1,head_a,edge_a,from_a,dp_a);
dfs_second(1,1,from_a,dp_a,head_a,edge_a);
for(int i=1;i<=T_b-1;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge_b(u,v);
add_edge_b(v,u);
}
dfs_first(1,1,head_b,edge_b,from_b,dp_b);
dfs_second(1,1,from_b,dp_b,head_b,edge_b);
double cc=0;
double ans=0;
for(int i=1;i<=T_a;i++)
{
if(dp_a[i][0]>cc)
cc=dp_a[i][0];
}
for(int i=1;i<=T_b;i++)
{
bb[i]=dp_b[i][0];
if(bb[i]>cc)
cc=bb[i];
}
sort(bb+1,bb+T_b+1);
double S[maxn];
S[1]=bb[1];
for(int i=2;i<=T_b;i++)
{
S[i]=S[i-1]+bb[i];
}
for(int i=1;i<=T_a;i++)
{
int pos=lower_bound(bb+1,bb+T_b+1,cc-dp_a[i][0]-1)-bb;
ans+=(double)(pos-1)*cc;
ans+=(T_b-pos+1)*(dp_a[i][0]+1)+S[T_b]-S[pos-1];
}
printf("%.3f
",ans/((double)T_a*T_b)+eps);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
