题解 P4992 【查房】

ztz11 · 2018-11-04 11:46:50 · 题解

思路：

这道题告你n-1条边就是骗你的

部分分也是骗你的

这道题连对边5分钟的事

一个点对另一个点有影响当且仅当这个点在另一个点的前一时刻被查

且这两个点之间有边相连

我们加上超级根节点后可以建一棵树

跑树形DP即可

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rij register int j
#define rii register int i
using namespace std;
int head[1000005],n,m,tim[1000005],bj[1000005];
double dp[1000005],gl[1000005];
int bnt;
struct road{
    int to,nxt;
}x[2000005];
int a,b,c;
inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f?x:-x;
}
void add(int from,int to)
{
//    cout<<from<<" "<<to<<endl;
    bnt++;
    x[bnt].to=to;
    x[bnt].nxt=head[from];
    head[from]=bnt;
}
void dplast(int wz)
{
    double ans=1.0;
    for(rii=head[wz];i!=0;i=x[i].nxt)
    {
        dplast(x[i].to);
        ans*=(1-dp[x[i].to]);
    }
    ans*=gl[wz];
    dp[wz]=1-ans;
}
int main()
{
//    freopen("cf8.in","r",stdin);
//    freopen("cf8.out","w",stdout);
    n=rd();m=rd();a=rd();b=rd();c=rd();
    for(rii=1;i<=m;i++)
    {
        int k;k=rd();
//        scanf("%d",&k);
        for(rij=1;j<=k;j++)
        {
            int bh=rd();
//            scanf("%d",&bh);
            tim[bh]=i;
        }
    }
    for(rii=1;i<=n-1;i++)
    {
        int from=rd(),to=rd();
//        scanf("%d%d",&from,&to);
        if(tim[from]-tim[to]==1)
        {
            add(from,to);
            bj[to]++;
        }
        if(tim[to]-tim[from]==1)
        {
            add(to,from);
            bj[from]++;
        }
    }
    for(rii=1;i<=n;i++)
    {
        if(bj[i]==0)
        {
            add(0,i);
        }
    }
    for(rii=1;i<=n;i++)
    {
        scanf("%lf",&gl[i]);
    }
    dplast(0);
//    for(rii=1;i<=n;i++)
//    {
//        printf("%.4lf ",dp[i]);
//    }
    double maxn=max(dp[a],max(dp[b],dp[c]));
    if(dp[a]==maxn)
    {
        printf("%d\n",a);
    }
    else
    {
        if(maxn==dp[b])
        {
            printf("%d\n",b);
        }
        else
        {
            printf("%d\n",c);
        }
    }
    printf("%.4lf",maxn);
}