UvaLive 6534 Join two kingdoms 樹形DP+二分
來源：程序員人生 發布時間：2014-10-04 08:00:00 閱讀次數：3558次
鏈接：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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
