[확률 과 기대] [사기] 관광 철도

문 제 는 벼룩 나라 가 관광 산업 을 크게 발전 시 키 고 있 고 모든 도시 가 관광지 로 만 들 어 졌 다 는 것 이다.많은 벼룩 들 이 다른 도시 로 여행 을 가 고 싶 어 하지만, 비교적 느리게 뛰 기 때문에, 그들의 소망 은 실현 되 기 어렵다.이때 C 군 은 기차 라 는 교통수단 이 있다 는 말 을 듣 고 철 도 를 빨리 달리 자 상업 기 회 를 잡 아 철도 회 사 를 설립 하여 벼룩 왕 에 게 두 도시 사이 에 철 도 를 건설 하 라 고 물 었 다.그러나 작은 C 는 길 을 갈 라 놓 지 않 기 때문에 기 차 는 한 도시 에 도착 한 후에 원래 의 길 로 돌아 가지 않 고 랜 덤 으로 이 도시 와 철도 로 연 결 된 다른 도시 로 향 할 수 밖 에 없다.벼룩 왕 은 많은 주민 들 에 게 의견 을 구 했 지만 벼룩 들 은 그다지 만 족 스 럽 지 못 했다. 철 도 를 건설 한 후에 3 개 도시 (출발 도시 포함) 만 유람 하고 돌아 올 수도 있 기 때문이다. 그들 은 몇 개의 도 시 를 더 유람 하고 싶 어 하기 때문이다.그래서 벼룩 왕 은 작은 C 에 게 모든 벼룩 이 기 차 를 타고 몇 개의 도 시 를 더 유람 할 수 있 도록 방안 을 제공 해 달라 고 요구 했다.
C 군 은 벼룩 왕 에 게 방안 을 제공 했다.벼룩 왕 은 이 방안 에서 각 도시 의 주민 들 이 여행 하 는 기대 시간 (기 차 를 설치 하여 모든 철 도 를 지 나 는 시간 은 1) 을 알 고 싶 어 합 니 다. 벼룩 왕 을 도와 주세요.입력 형식 입력 의 첫 줄 은 두 개의 정수 n, m 를 포함 하 는데 그 중에서 n 은 도시 의 수량 을 나타 내 고 m 는 방안 중의 철도 조 수 를 나타 낸다.다음 m 행 은 각 줄 에 두 개의 정수 u, v 를 포함 하고 방안 에서 도시 u 와 도시 v 사이 에 철도 가 있다 는 것 을 나타 낸다.보증 방안 에 무 거 운 변 이 없고 두 도시 간 에 철 도 를 거 쳐 직접 또는 간접 적 으로 도착 할 수 있 으 며 기 차 는 임 의 철도 에서 임 의 도시 로 간 후에 반드시 갈 길이 있 을 것 이다.출력 형식 은 n 줄 을 출력 하고 i 줄 은 실수 tBi 를 포함 하 며 방안 B 에서 도시 i 의 주민 관광 에 대한 기대 시간 을 나타 낸다.출력 값 과 실제 값 사이 의 절대 또는 상대 적 인 오차 가 1e - 9 를 초과 하지 않도록 충분 한 소수 자릿수 를 출력 해 야 합 니 다.
  제 가 잘 못 했 습 니 다. 그 전에 블 루 브리지 컵 은 모두 물 문제 가 많다 고 생각 했 습 니 다.이틀 동안 갑자기 문제 고 를 닦 으 려 고 하 다가 어 려 운 문제 에 부 딪 혔 다. 이것 이 바로 그 중의 비교적 변태 적 인 것 이다.우선 저 는 정 해 가 아니 지만 인터넷 에서 정 해 를 찾 지 못 했 습 니 다.찾 을 수 있 는 것 은 오직 이 편 뿐이다.https://blog.csdn.net/weixin_40839812 / article / details / 79769757 은 잘 모 르 겠 고 저 자 는 돌아 갈 수 없 는 조건 을 고려 하지 않 았 고 코드 를 제공 하지 않 았 기 때문에 정확성 이 확실 하지 않다 고 생각 합 니 다.나중에 천천히 연구 해.  다른 생각 이 없 으 면 폭력 을 먼저 때 리 고 기 대 를 하면 확률 을 먼저 구 합 니 다. 돌아 갈 수 없 기 때문에 어느 시간 에 확률 은 2 차원 의 재능 으로 전달 해 야 합 니 다. 출발점 을 1 로 예 로 들 면 우 리 는 T 단계 에서 노드 j 에서 노드 i 까지 의 사건 이 발생 할 확률 p [T] [i] [j] pb [T] [i] [j] pb [T] [i] [j] pb [T] [i] [j] (그 중에서 i 는 출발점 1 이 아 닙 니 다) 를 구 해 야 합 니 다. 이것 은 처리 하기 쉽 습 니 다.T - 1 단계 에서 순서대로 T 단 계 를 내 놓 으 면 됩 니 다. T 단계 에서 출발점 1 로 돌아 갈 확률 을 찾 아 보 세 요. ∑ p b [T - 1] [i] [i] d [i] - 1 \ \ \ sum {\ frac {pb [T - 1] [i]} {d [i] - 1} ∑ d [i] - 1pb [T - 1] [i] [j] (i 와 1 이 연결 되 어 있 지만 j 는 i 가 아 닙 니 다) 이 수 치 를 T 에 곱 하고 답 을 누적 하면 됩 니 다. 충분 한 T 만 있 으 면 됩 니 다.답 은 무한 한 접근 과 진실 한 기대 이다.  정확성 을 고려 해 T 가 클 수록 누적 수치 가 매우 작 냐 는 질문 이 나 올 수 있 습 니 다.나 는 수렴 속 도 를 증명 할 방법 이 없 지만 확률 의 감소 속 도 는 T 가 증가 하 는 속도 보다 훨씬 클 것 같 아서 수렴 이 비교적 빠르다.그래서 첫 번 째 폭력 을 시도 한 것 이 바로 위의 생각 이다.

#include
#include
using namespace std;

double ans,pb[2][25][25];
vector<int> E[25];
int n,m,o;

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<=m;i++)
		scanf("%d%d",&u,&v),E[u].push_back(v),E[v].push_back(u);
	for(int p=1;p<=n;p++)
	{
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				pb[0][i][j]=0;
		for(int q=0;q<E[p].size();q++)
			pb[0][E[p][q]][p]=1.0/E[p].size();
		ans=o=0;
		for(int t=1;t<=300;t++)  //  t T-1
		{
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					pb[o^1][i][j]=0;
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					for(int k=0;k<E[i].size();k++)
						if(E[i][k]!=j)
							if(E[i][k]!=p)
								pb[o^1][E[i][k]][i]+=pb[o][i][j]/(E[i].size()-1);
							else
								ans+=(t+1)*pb[o][i][j]/(E[i].size()-1);			
			o^=1;
		}
		printf("%.12lf
",ans);
	}
	return 0;
}

  남 은 최 악의 순환 은 n 4 n ^ 4 n4 의 효율 이기 때문에 시간 을 300 까지 매 거 하면 안 됩 니 다.5 점 밖 에 얻 지 못 했다. 하 나 는 정확도 가 내 가 생각 했 던 것 보다 높 지 않 았 기 때문이다. 다른 하 나 는 블 루 브리지 가 SPJ (맙소사) 를 사용 하지 않 았 기 때문이다. 즉, 모 르 는 사이 에 문제 의 난이 도 를 증가 시 켰 기 때문에 나 는 12 명의 소 수 를 완전히 일치 시 켜 야 한다.그런데 말 이 야, 나 는 점 수 를 속 이 는 데 아주 능숙 해.우선 더 블 은 모두 롱 더 블 로 만 들 었 다.그 다음 에 n 이 비교적 작다 면 우 리 는 T 를 적당 하 게 확대 하고 더욱 정확 할 수 있다.또한 직관 적 으로 나 에 게 T 가 클 때 확률 pb 배열 간 의 상대 적 인 크기 가 특정한 안정 상태 에 이 를 수 있다 는 것 을 알려 주 었 다. 즉, 출발점 으로 돌아 갈 확률 이 T 가 비교적 클 때 무한 등비 수축 수열 이 될 수 있다 는 것 을 의미한다.절차 검증 을 거 쳐 나의 생각 은 실증 에 이 르 렀 다.그러면 만약 에 이 수열 의 공비 v 를 알 게 된다 면 매 거 진 후에 저 는 급수 적 으로 화 해 를 구 하 는 방식 으로 제 가 적 게 넣 은 부분 을 보충 하면 정확도 가 크게 높 아 질 것 입 니 다.(갑자기 유 휘 가 3.14 를 구 한 후에 비슷 한 보족 법 으로 3.1416 QwQ 를 만 들 었 다 고 생각 했다.) 저 는 제 t 가 l i m lim lim (즉, T = lim + 1) 에 들 어 갔다 고 가정 하고 제 lim 걸음 의 증 가 는 a 입 니 다. 저 는 l i m lim lim 과 l i m - 1 lim - 1 lim - 1 두 걸음 의 원점 으로 돌아 갈 확률 을 공비 v 에 비유 한 다음 에 저희 가 요구 하 는 것 은 ＞ a * 8727 ° T + a * 8727 ° v 2 * 8727 ° (T + 1) 입 니 다.... \ sum {a * v * T + a * v ^ 2 * (T + 1)}.『 8195 』 실천 을 통 해 효과 가 매우 좋다 는 것 을 발견 했다.『 8195 』 개 선 된 폭력:

#include
#include
using namespace std;

int lim;

long double ans,pb[2][25][25],ty,tx;
vector<int> E[25];
int n,m,o;

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<=m;i++)
		scanf("%d%d",&u,&v),E[u].push_back(v),E[v].push_back(u);
	lim=60000000/n/n/n/n;
	for(int p=1;p<=n;p++)
	{
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				pb[0][i][j]=0;
		for(int q=0;q<E[p].size();q++)
			pb[0][E[p][q]][p]=1.0L/E[p].size();
		tx=ty=ans=o=0;
		for(int t=1;t<=lim;t++)
		{
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					pb[o^1][i][j]=0;
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					for(int k=0;k<E[i].size();k++)
						if(E[i][k]!=j)
							if(E[i][k]!=p)
								pb[o^1][E[i][k]][i]+=pb[o][i][j]/(E[i].size()-1);
							else
							{
								ans+=(t+1)*pb[o][i][j]/(E[i].size()-1);
								if(t==lim-1)
									tx+=pb[o][i][j]/(E[i].size()-1);
								else if(t==lim)
									ty+=pb[o][i][j]/(E[i].size()-1);
							}
			o^=1;	
		}
		long double v=0;
		int cnt=0;
		if(tx>0)
			v=ty/tx;
		printf("%.12Lf
",ans+ty*(lim*v+(2*v-v*v)/(1-v))/(1-v));
	}
	return 0;
}

* 8195 점 을 받 았 는데 더 이상 개선 할 방법 이 없어 서 남 은 것 이 무슨 이상 한 데이터 인지 모 르 겠 습 니 다.개인 적 으로 SPJ 에 가면 AC 기회 가 있 을 것 같 아서 요.이렇게 하 자. 요구 가 너무 높 아. 그리고 정 해 를 기대 해.