839C Journey (简单dfs)

Journey

题意

Seven Kingdoms 上有n个城市，他们之间由n-1条路连接，每个城市之间都无向连通，从第一个城市出发，每条路长度为1，若一个城市有x条岔路通向其他城市，那么这些城市的概率相同，均为1/x，走过的城市不会再走，那么一直走到走不了为止，求期望的路径长度？

思路

一看就是简单搜索，搜遍每条路，（zz的人永远不好好看题目，不是简单的路径/路的数量啊！），这里用结构体+vector来存图，结构体中加一个变量fencha来表示路径的分叉点，跑一下就好了。

看！代码

#include <bits/stdc++.h>
using namespace std;
struct node{
    vector<int>next;
    double fencha;
};
int n;
double all=0,way=0;
int viss[100010];
node city[100010];
void solve(int cur,int step,int vis[])
{
    int len=city[cur].next.size();
    int flag=0;
    for(int i=0;i<len;i++)
        if(!vis[city[cur].next[i]])
            flag++;
    for(int i=0;i<len;i++)
    {
        if(!vis[city[cur].next[i]])
        {
            vis[city[cur].next[i]]=true;
            city[city[cur].next[i]].fencha=city[cur].fencha*flag;
            solve(city[cur].next[i],step+1,vis);
            vis[city[cur].next[i]]=false;
        }
    }
    if(flag==0||len==0)
        all+=(1.0/city[cur].fencha)*step;
}

int main()
{
    scanf("%d",&n);
    int a,b;
    if(n==1)
    {
        printf("0.000000000000000\n");
        return 0;
    }
    for(int i=0;i<n-1;i++)
    {
        scanf("%d%d",&a,&b);
        city[a].next.push_back(b);
        city[b].next.push_back(a);
        viss[a]=viss[b]=false;
        city[a].fencha=city[b].fencha=1;
    }
    viss[1]=true;
    solve(1,0,viss);
    printf("%.15f\n",all);
    return 0;
}