首页 > ACM题库 > HDU-杭电 > HDU 4443-Lost-动态规划-[解题报告]HOJ
2015
07-16

HDU 4443-Lost-动态规划-[解题报告]HOJ

Lost

问题描述 :

Finally Biaoge reached the amusement park. But soon he got lost…
The amusement park has N sites and N bidirectional roads connecting these sites. You can start from every site to get to any other site through the roads. Every time Biaoge got to a site, he marked it as visited and then chose a new site which was connected directly to it and not visited yet. If there were more than one site meet the conditions, Biaoge would choose randomly with equal possibility.
Biaoge also chose the first site among N sites randomly with equal possibility and then repeated this process until there was no site to go.
Calculate the possibility for each site of being the last site which Biaoge would visit. And output the sum of five largest possibilities.

输入:

There are multiple test case.
For each test case the first line contains an Integer N(5≤N≤100000) indicating the number of sites(All sites are labeled from 1 to N) . And then N lines follow. Each line contains two Integer x,y(1≤x,y≤N)indicating two sites connected by the road.
The input end with N=0.
Obviously there is exactly one loop in the abstracted graph. It is guaranteed that the length of loop is between 3 and 30.

输出:

There are multiple test case.
For each test case the first line contains an Integer N(5≤N≤100000) indicating the number of sites(All sites are labeled from 1 to N) . And then N lines follow. Each line contains two Integer x,y(1≤x,y≤N)indicating two sites connected by the road.
The input end with N=0.
Obviously there is exactly one loop in the abstracted graph. It is guaranteed that the length of loop is between 3 and 30.

样例输入:

5
5 2
2 4
4 5
3 4
1 2
10
5 8
8 3
3 1
1 5
2 1
10 8
7 8
6 7
4 10
9 10
0

样例输出:

1.00000
0.91250

这题太恶心了。。。应该是我做过的最难的树形dp,那个圈超恶心。。。区域赛的时候只有两个队过了这道题,一个是上交的秘银,还有一个是北理工的Keshik,无限膜拜他们!!!

我的代码有点长。。500多行吧。。大部分是用来调试的,细节比较多,调了一天一夜才ac。。。艹!

然后说下方法吧~

第一步是找出这个圈,怎么找呢?边双联通tarjan算法呗~这个简单

把这个圈拆开,于是形成了3-30颗树,因为题目说圈只有3-30个点

对于每个树进行树形dp,求出往上推的概率(dpx和dps,dps是dpx的总和)

然后在圈上dp,求出圈上每个点互相影响的概率,分顺时针(go)和逆时针(back)

再从圈出发往下推,求出推到每个节点的概率(dpy)

最后统计,有两种点会停止,一种是叶节点,还有一种是圈上度为2的节点,选出前5个相加就好了~o(∩_∩)o ~

#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<cstring>
#include<iomanip>
using namespace std;
#ifdef _WIN32
#define i64 __int64
#define out64 "%I64d\n"
#define in64 "%I64d"
#else
#define i64 long long
#define out64 "%lld\n"
#define in64 "%lld"
#endif
/************ for topcoder by zz1215 *******************/
#define FOR(i,a,b)      for( int i = (a) ; i <= (b) ; i ++)
#define FF(i,a)        for( int i = 0 ; i < (a) ; i ++)
#define FFD(i,a,b)      for( int i = (a) ; i >= (b) ; i --)
#define S64(a)          scanf(in64,&a)
#define SS(a)           scanf("%d",&a)
#define LL(a)           ((a)<<1)
#define RR(a)           (((a)<<1)+1)
#define pb              push_back
#define pf              push_front
#define X               first
#define Y               second
#define CL(Q)           while(!Q.empty())Q.pop()
#define MM(name,what)   memset(name,what,sizeof(name))
#define MC(a,b)         memcpy(a,b,sizeof(b))
#define MAX(a,b)        ((a)>(b)?(a):(b))
#define MIN(a,b)        ((a)<(b)?(a):(b))
#define read            freopen("in.txt","r",stdin)
#define write           freopen("out.txt","w",stdout)

const int inf = 0x3f3f3f3f;
const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;
const double oo = 10e9;
const double eps = 10e-9;
const double pi = acos(-1.0);
const int maxn = 100011;

vector<int>v[maxn];
vector<int>g[maxn];
vector<int>s;
int n;
double nn;
int t[maxn];
int f[maxn];
int dfn[maxn];
int low[maxn];
int df,nf;
bool ins[maxn];
int tot;
bool hash[maxn];
int yes[33];
double go[33][33];
double back[33][33];
double dpx[maxn];
double dpy[maxn];
bool vis[maxn];
int cnt[maxn];
double dp[maxn];
double dps[maxn];
vector<double>ans;

void tarjan(int now)
{
    low[now] = dfn[now] = df++;
    s.push_back(now);
    ins[now]=true;
    int to;
    for(int i=0;i<g[now].size();i++)
    {
        to = g[now][i];
        if(!dfn[to])
        {
            t[to]=now;
            tarjan(to);
            low[now] = min(low[to],low[now]);
        }
        else if(to!=t[now])
        {
            low[now]=min(dfn[to],low[now]);
        }
    }
    if(dfn[now] == low[now])
    {
        while(s.back() != now)
        {
            to = s.back();
            f[to] = nf;
            s.pop_back();
            ins[to]=false;
        }
        to = s.back();
        s.pop_back();
        ins[to]=false;
        f[to] = nf++;
    }
    return ;
}

void dfs(int now)
{
	vis[now] = true;
	int to;
	for(int i=0;i<g[now].size();i++)
	{
		to = g[now][i];
		if(!ins[to] && !vis[to])
		{
			cnt[now]++;
		}
	}
    for(int i=0;i<g[now].size();i++)
	{
		to = g[now][i];
		if(!ins[to] && !vis[to])
		{
			dfs(to);
			dps[now]+=dpx[to];
			if(ins[now])
			{
				dpx[now]+=2.0*dpx[to]/double(cnt[now]+1.0);
			}
			else
			{
				dpx[now]+=dpx[to]/double(cnt[now]);
			}
		}
	}
	if(ins[now])
	{
		double temp = 2.0/double(cnt[now]+2.0);
		dpx[now] += nn*temp;
	}
	else
	{
        double temp = 1.0/double(cnt[now]+1.0);
		dpx[now] += nn*temp;
	}
	return ;
}

void df2(int now)
{
	vis[now]=true;
	int to;
	for(int i=0;i<g[now].size();i++)
	{
		to = g[now][i];
		if(!ins[to] && !vis[to])
		{
			dpy[to] = dpy[now]/double(cnt[now]);
			dpy[to] += nn*double(cnt[to])/double(cnt[to]+1.0);
			if(ins[now])
			{
				dpy[to]+=(dps[now]-dpx[to])/(cnt[now]+1.0);
			}
			else
			{
				dpy[to]+=(dps[now]-dpx[to])/double(cnt[now]);
			}
			df2(to);
		}
	}
	if(!cnt[now])
	{
		dp[now] = dpy[now];
	}
	return ;
}


void find()
{
	int now=s[0];
	int to;
	vis[now] = true;
	bool ok;
	while(true)
	{
		ok = false;
		for(int i=0;i<g[now].size();i++)
		{
			to = g[now][i];
			if(ins[to] && !vis[to])
			{
				vis[to]=true;
				s.pb(to);
				now = to;
				ok = true;
				break;
			}
		}
		if(!ok) break;
	}
	return ;
}

void start()
{
/*	MM(f,0);
	MM(t,0);
	MM(dfn,0);
	MM(low,0);
	MM(ins,false);*/
	for(int i=0;i<=n;i++)
	{
		f[i]=0;
		t[i]=0;
		dfn[i]=0;
		low[i]=0;
		ins[i]=false;
	}
	s.clear();
	df=nf=1;
	tarjan(1);
	nf--;
	for(int i=1;i<=n;i++)
	{
		v[f[i]].pb(i);
	}
	int tv;
	for(int i=1;i<=nf;i++)
	{
		if(v[i].size()>1)
		{
			tv=i;
			break;
		}
	}
	s.clear();
	tot = v[tv].size();
//	MM(ins,false);
//	MM(vis,false);
	for(int i=0;i<=n;i++)
	{
		ins[i]=false;
		vis[i]=false;
	}
	for(int i=0;i<v[tv].size();i++)
	{
		ins[v[tv][i]] = true;
	}
	s.pb(v[tv][0]);
	find();
	int now,to;
	MM(yes,0);
	for(int i=0;i<s.size();i++)
	{
		now = s[i];
		for(int j=0;j<g[now].size();j++)
		{
			to = g[now][j];
			if(!ins[to])
			{
				yes[i]++;
			}
		}
	}
 	MM(go,0);
	MM(back,0);
	int ss = s.size();
	for(int i=0;i<ss;i++)
	{
		if(yes[i])
		{
			go[i][(i+1)%ss]=1.0/(yes[i]+1.0);
			back[i][(i-1+ss)%ss]=1.0/(yes[i]+1.0);
		}
		else
		{
			go[i][(i+1)%ss]=1.0;
			back[i][(i-1+ss)%ss]=1.0;
		}
	}
	for(int u=2;u<ss;u++)
	{
		for(int i=0;i<ss;i++)
		{
			go[i][(i+u)%ss]=go[i][(i+u-1)%ss]*go[(i+u-1)%ss][(i+u)%ss];
			back[i][(i-u+ss)%ss]=back[i][(i-(u-1)+ss)%ss]*back[(i-(u-1)+ss)%ss][(i-u+ss)%ss];
		}
	}

/*	MM(vis,false);
	MM(dpx,0);
	MM(dpy,0);
	MM(dp,0);
	MM(dps,0);
	MM(cnt,0);*/
	for(int i=0;i<=n;i++)
	{
		vis[i]=false;
		dpx[i]=0;
		dpy[i]=0;
		dp[i]=0;
		dps[i]=0;
		cnt[i]=0;
	}

	double temp;

	for(int i=0;i<ss;i++)
	{
		if(yes[i])
		{
			dfs(s[i]);
		}
	}

	for(int i=0;i<ss;i++)
	{
		if(!yes[i]) continue;
		for(int j=0;j<ss;j++)
		{
			if(j==i)
			{
				temp = double(yes[i])/(yes[i]+2.0);
				dpy[s[j]]+=temp*nn;
				continue;
			}
			if(!yes[j]) continue;
			temp = dpx[s[i]]*go[i][j];
			temp *= yes[i]+1.0;
			temp /= 2.0;
			if((i-j+ss)%ss==1)
			{
				dpy[s[j]]+=temp;
			}
			else
			{
				temp/=yes[j]+1.0;
				temp*=yes[j];
				dpy[s[j]]+=temp;
			}
			temp = dpx[s[i]]*back[i][j];
			temp *= yes[i]+1.0;
			temp /= 2.0;
			if((i-j+ss)%ss==ss-1)
			{
				dpy[s[j]]+=temp;
			}
			else
			{
				temp/=yes[j]+1.0;
				temp*=yes[j];
				dpy[s[j]]+=temp;
			}
		}
	}

	for(int i=0;i<ss;i++)
	{
		if(yes[i]) continue;
 		for(int j=0;j<ss;j++)
		{
			if(yes[j])
			{
				temp = nn*go[i][j]*0.5;
			    if((i-j+ss)%ss==1)
				{
					dpy[s[j]]+=temp;
				}
				else
				{
					temp/=yes[j]+1.0;
					temp*=yes[j];
					dpy[s[j]]+=temp;
				}
				temp = nn*back[i][j]*0.5;
				if((i-j+ss)%ss==ss-1)
				{
					dpy[s[j]]+=temp;
				}
				else
				{
					temp/=yes[j]+1.0;
					temp*=yes[j];
					dpy[s[j]]+=temp;
				}
			}
		}
	}

//	MM(vis,0);
	for(int i=0;i<=n;i++)
	{
		vis[i]=0;
	}

	for(int i=0;i<ss;i++)
	{
		if(yes[i])
		{
			df2(s[i]);
		}
	}

	for(int i=0;i<ss;i++) if(yes[i])
	{
        if(!yes[(i+1)%ss])
		{
			temp = dpx[s[i]]*back[i][(i+1)%ss];
			temp *= yes[i]+1.0;
			temp /= 2.0;
			dp[s[(i+1)%ss]] += temp;
		}
		if(!yes[(i-1+ss)%ss])
		{
			temp = dpx[s[i]]*go[i][(i-1+ss)%ss];
			temp *= yes[i]+1.0;
			temp /= 2.0;
			dp[s[(i-1+ss)%ss]] += temp;
		}
	}

	for(int i=0;i<ss;i++) if(!yes[i])
	{
		if(!yes[(i+1)%ss])
		{
			dp[s[(i+1)%ss]] += nn*back[i][(i+1)%ss]*0.5;
		}
		if(!yes[(i-1+ss)%ss])
		{
			dp[s[(i-1+ss)%ss]] += nn*go[i][(i-1+ss)%ss]*0.5;
		}
	}

	ans.clear();
	for(int i=1;i<=n;i++)
	{
		if(dp[i]>eps)
		{
			ans.pb(dp[i]);
		}
	}
	for(int i=1;i<=5;i++)
	{
		ans.pb(0.0);
	}
	sort(ans.begin(),ans.end());
/*	for(int i=0;i<ss;i++)
	{
		cout<<i<<" | "<<s[i]<<endl;
	}
	cout<<"yes **"<<endl;

	for(int i=0;i<ss;i++)
	{
		cout<<s[i]<<" ** "<<yes[i]<<endl;
	}

	cout<<"**"<<endl;
	cout<<"go"<<endl;
	for(int i=0;i<ss;i++)
	{
		cout<<i<<"** ";
		for(int j=0;j<ss;j++)
		{
			cout<<go[i][j]<<" | ";
		}
		cout<<endl;
	}

	cout<<"back"<<endl;
	for(int i=0;i<ss;i++)
	{
		cout<<i<<"** ";
		for(int j=0;j<ss;j++)
		{
			cout<<back[i][j]<<" | ";
		}
		cout<<endl;
	}

	cout<<"****"<<endl;
	for(int i=1;i<=n;i++)
	{
		cout<<i<<" |dpx "<<dpx[i] << " |dpy "<<dpy[i]<<endl;
	}

	for(int i=1;i<=n;i++)
	{
		cout<<i<<" |f[i] "<<f[i]<<endl;
	}

	for(int i=1;i<=n;i++)
	{
		cout<<i<<" = " <<dp[i]<<endl;
	}*/
	return ;
}

int main()
{
	while(cin>>n)
	{
		if(!n) return 0;
		nn = n;
		nn = 1.0/nn;
		for(int i=0;i<=n;i++)
		{
			v[i].clear();
			g[i].clear();
		}
		int now,to;
		for(int i=1;i<=n;i++)
		{
			SS(now);
			SS(to);
			g[now].pb(to);
			g[to].pb(now);
		}
		start();
		double re=0.0;
		int ix = ans.size()-1;
		for(int i=1;i<=5;i++)
		{
			re+=ans[ix--];
		}
		printf("%.5lf\n",re);
	}
	return 0;
}


版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/zz_1215/article/details/8136840