hdu 4035確率dp
2008 ワード
良いテーマです。
具体的な考え方はネットでたくさん言います。
参考ですhttp://www.cnblogs.com/kuangbin/archive/2012/10/03/2711108.htmlこれは、わかりやすく書いてあるような気がします。
コードを保存
具体的な考え方はネットでたくさん言います。
参考ですhttp://www.cnblogs.com/kuangbin/archive/2012/10/03/2711108.htmlこれは、わかりやすく書いてあるような気がします。
コードを保存
#include
using namespace std;
typedef long long LL;
const int maxn = 10000+10;
const double eps = 1e-9;
int T,n;
int head[maxn],_cnt,vist[maxn],degree[maxn];
struct Edge{
int to,next;
}edge[maxn<<1];
inline void init(){
for(int i = 0; i <= n; i++){
head[i] = -1;
vist[i] = 0;
degree[i] = 0;
}
_cnt = 0;
}
inline void ADD(int u,int v){
edge[_cnt].to = v;
edge[_cnt].next = head[u];
head[u] = _cnt++;
}
struct Info{
double ki,ei;
}nxt[maxn];
struct DP{
double Ai,Bi,Ci;
}dp[maxn];
inline void dfs(int now){
vist[now] = 1;
if(head[now] == -1){
dp[now].Ai = nxt[now].ki;
dp[now].Bi = 1.0-nxt[now].ei-nxt[now].ki;
dp[now].Ci = 1.0-nxt[now].ei-nxt[now].ki;
return;
}
double sum_Aj,sum_Bj,sum_Cj;
sum_Aj = sum_Bj = sum_Cj = 0.0;
for(int i = head[now]; ~i; i = edge[i].next){
int v = edge[i].to;
if(!vist[v]){
dfs(v);
sum_Aj += dp[v].Ai;
sum_Bj += dp[v].Bi;
sum_Cj += dp[v].Ci;
}
}
double temp = 1.0-((1-nxt[now].ei-nxt[now].ki)*sum_Bj)/degree[now];
dp[now].Ai = (nxt[now].ki+(1-nxt[now].ei-nxt[now].ki)*sum_Aj/degree[now])/temp;
dp[now].Bi = ((1-nxt[now].ei-nxt[now].ki)/degree[now])/temp;
dp[now].Ci = (1-nxt[now].ei-nxt[now].ki+(1-nxt[now].ei-nxt[now].ki)*sum_Cj/degree[now])/temp;
}
int main(){
int cas = 0;
int u,v;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
init();
for(int i = 1; i < n; i++){
scanf("%d %d",&u,&v);
degree[u]++;
degree[v]++;
ADD(u,v);
ADD(v,u);
}
for(int i = 1; i <= n; i++){
scanf("%lf %lf",&nxt[i].ki,&nxt[i].ei);
nxt[i].ki /= 100.0;
nxt[i].ei /= 100.0;
}
dfs(1);
if(fabs(1-dp[1].Ai) < eps)
printf("Case %d: impossible
",++cas);
else
printf("Case %d: %.6f
",++cas,dp[1].Ci/(1.0-dp[1].Ai));
}
return 0;
}