首页 > ACM题库 > HDU-杭电 > HDU 3994-Mission Impossible[解题报告]HOJ
2015
04-14

HDU 3994-Mission Impossible[解题报告]HOJ

Mission Impossible

问题描述 :

I.M.F.(Impossible Missions Force) is a top secret spy organization in U.S. Ethan Hunt have serviced in this organization for many years. Now, he is retired and serves as a spy in a big company. Although he is very excellent, he would make mistakes. For example, last time he invaded another company to find some programming code. When he risked his life to steal the last few pages of the code, he found that all of the letters on them are only “}”. His boss is very angry. So, Ethan must finish this new mission and he needs your help.
Horse Racing

In this new mission, Ethan successfully gets a big file in a computer and decided to send this file from this computer to his boss’s computer though the internet. We can assume the file is made of C small parts and Ethan could only send one part each unit time.

The network consists of n (n <= 200) computers, Ethan sits next to computer 1, his boss sits next to computer 2. There exists a probability p[i][j] between computer i and computer j, which means the probability of successfully transferring each part from i to j is p[i][j]. However, all of these links in the network are unidirectional (i.e. p[i][j] may be different from p[j][i]). We defined the e[i][j] as the expected time to send each part from i to j. For example, if p[i][j] = 10%, e[i][j] = 10 units.

Horse Racing

You may find that the probability would be very tiny and the expected time could be very large since the route may be extremely long. Fortunately, Ethan knows that he has m teammates sit next to several computers. He can choose these computers as storage to shorten the transferring time. (i.e. each of the n computers could be used as node in any route, but only these m computers could be used as storages. Each attempt to send a small part, successful or unsuccessful, takes exactly one unite time, regardless of the number of links on the route.) So, he can do this mission as follows:
  • Choose a computer which includes the file (i.e. C parts of information) as computer u.
  • Choose another computer his boss or some teammate sits next to as computer v, and then takes time to transfer the file from u to v. If any part fails to be transferred, it will be resent immediately.
  • When the file is sent to his boss’s computer, the mission is finished.

To satisfy his boss, Ethan must choose a route to make the total expected time from computer 1(the computer near him) to computer 2(the computer near his boss) minimum. You need to tell Ethan the minimum total expected time.

It is an impossible mission aha? Why not have a try. It’s easier than expected.

输入:

The first line contains an integer T, which means there are T test cases. Each test case is preceded by a blink line.

In each test case, you know n (2 <= n <= 200), which means the number of computers. Then an n*n matrix p(n) is following. p[i][j] means the probability of successfully transferring each part from i to j. You may assume that 0 <= p[i][j] <= 100.

Next line contains m (m <= n) means there are m computer that could serve as storage (i.e. the number of computers near Ethan, his teammates or his boss). Then a line contains m integer shows these computers. You may assume that it must contains computer 1 and computer 2.

The last line tells you there C parts in the big file. C is an integer which insure the answer is less than 1 000 000 000.

输出:

The first line contains an integer T, which means there are T test cases. Each test case is preceded by a blink line.

In each test case, you know n (2 <= n <= 200), which means the number of computers. Then an n*n matrix p(n) is following. p[i][j] means the probability of successfully transferring each part from i to j. You may assume that 0 <= p[i][j] <= 100.

Next line contains m (m <= n) means there are m computer that could serve as storage (i.e. the number of computers near Ethan, his teammates or his boss). Then a line contains m integer shows these computers. You may assume that it must contains computer 1 and computer 2.

The last line tells you there C parts in the big file. C is an integer which insure the answer is less than 1 000 000 000.

样例输入:

2

5
0 1 20 0 0
0 0 0 0 0
0 0 0 50 90
0 20 0 0 0
0 0 0 90 0
3
1 2 5
10

4
0 100 0 0
100 0 100 0
0 100 0 100
0 0 100 0
0
1

样例输出:

111.111111
1.000000

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define MaxN 200
#define eps 1e-8
double dp[MaxN+5][MaxN+5];
double tmp[MaxN+5][MaxN+5];
int n;
int c;
int m;
int lst[MaxN+5];
void floyd(bool flag){
	int i,j,k;
	if (flag){
		for (k=0;k<n;k++){
			for (i=0;i<n;i++){
				for (j=0;j<n;j++){
					if ((i==j) || (j==k) || (i==k)) continue;
					if (dp[i][j]<dp[i][k]*dp[k][j]){
						dp[i][j]=dp[i][k]*dp[k][j];
					}
				}
			}
		}
		return;
	}
	for (k=0;k<n;k++){
		for (i=0;i<n;i++){
			for (j=0;j<n;j++){
				if ((i==j) || (j==k) || (i==k)) continue;
				if (dp[i][k]>=0 && dp[k][j]>=0 && (dp[i][j]<0 || dp[i][j]>dp[i][k]+dp[k][j])){
					dp[i][j]=dp[i][k]+dp[k][j];
				}
			}
		}
	}
}
bool iszero(double a)
{
		return a<eps;
}
void init(){
	int i,j;
	scanf("%d",&n);	
	for (i=0;i<n;i++){
		for (j=0;j<n;j++){
			scanf("%lf",&dp[i][j]);
			dp[i][j]=dp[i][j]/100.0;
		}
	}
	floyd(1);
	scanf("%d",&m);
	
//	cout<<"m:"<<m<<endl;
	for (i=0;i<m;i++){
		scanf("%d",&lst[i]);
	}
	for (i=0;i<m;i++){
		if (lst[i]==1) break;
	}
	if (i==m) lst[m++]=1;
	for (i=0;i<m;i++){
		if (lst[i]==2) break;
	}
	if (i==m) lst[m++]=2;
	sort(lst,lst+m);
//	cout<<"m:"<<m<<endl;
	for (i=0;i<m;i++){
		for (j=i+1;j<m;j++){
			tmp[i][j]=dp[lst[i]-1][lst[j]-1];
			tmp[j][i]=dp[lst[j]-1][lst[i]-1];
		}
//		cout<<lst[i]<<endl;
	}
/*	for (i=0;i<m;i++){
		for (j=0;j<m;j++){
			printf("%lf ",tmp[i][j]);
		}
		printf("\n");
	}
	for (i=0;i<n;i++){
		for (j=0;j<n;j++){
			printf("%lf ",dp[i][j]);
		}
		printf("\n");
	}*/
	for (i=0;i<m;i++){
		for (j=0;j<m;j++){
			if (iszero(tmp[i][j]))dp[i][j]=-1;
			else dp[i][j]=1.0/tmp[i][j];
			if (iszero(tmp[j][i]))dp[j][i]=-1;
			else dp[j][i]=1.0/tmp[j][i];
		}
	}
/*	for (i=0;i<m;i++){
		for (j=0;j<m;j++){
			printf("%lf ",dp[i][j]);
		}
		printf("\n");
	}*/
	n=m;
	scanf("%d",&c);
	floyd(0);
}
void solve(){
	printf("%.6lf\n",dp[0][1]*c);
}
int main()
{
	int t;
	scanf("%d",&t);
	while (t--){
		init();
		solve();
	}
	return 0;
}

  1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  2. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……