HDU 3409-Chase (Tree DP)
一群警察部署在街道的Ｎ个路口堵截一个贼，贼不会重复到达某个路口，且从一个路口到下一个路口所选择的路径都是最短的。如果没有被抓住，贼会不停的奔跑直到跑不动了。如果停下后没有被警察抓住，那他就不会被抓住了。给定街道路口的分布和距离，以及在某个路口部署Ｍ个警察抓到贼的概率。求部署警力所能达到的最大捕获概率。
http://www.acmerblog.com/hdu-3409-chase-5435.html
Also check code at http://www.cnblogs.com/woaishizhan/p/3189813.html
Problem Description
Jack the Robber appears again! He just robbed a bank in town and is running away with a huge amount of dollar cash. Senior FBI agent Don Epps is taking responsibility to catch him. He must deploy his men immediately to hold up and capture Jack on some spot in town. Because this task is extremely urgent and crucial, Don asks his brother Charlie Epps, the mathematics professor in the University of CalSci, to help him find the theoretically best deployment.
Let us assume that the town can be described as N spots (numbered from 0 to N-1) and M bidirectional roads between those N spots. Jack the Robber starts running from Spot 0. After several rounds of chasing and fleeing in the past, Don summarized Jack’s rules of escape:
1.He will never visit a spot more than once.
2.He is an expert about the geography of this town, so no matter which spot he reaches, the route he has traveled is always the shortest path from Spot 0 to that spot. To simplify the situation, we assume that there is only one shortest path from Spot 0 to any other spot.
3.He has no certain destination spot to go. He just runs AS FAR AS HE CAN, following the two rules above. As you may see, if he never gets caught, he will definitely come to a spot where he has to stop because if he keeps running, he will violate the two rules above. When he reaches a spot where he has to stop and is not arrested by FBI at that spot, he hides and FBI will never find him.
4.When he comes to a spot and is NOT captured by FBI at that spot, he will randomly choose a road to continue running. Of course, his choice can’t conflict with the above mentioned rules. The term “randomly” means that he chooses each valid road on the same probability.
Even if Jack gets to a spot where agents are already deployed, he may still get a chance to run away. For example, if the spot is very crowded, even all agents are deployed there, Jack may still run away easily. So Charlie finds out an N×(P+1) probability matrix PT. PT(i, j) represents the probability of j FBI agents deployed at spot i arresting Jack when Jack comes to Spot i. For example, PT(0, 1) can be only 5%, which means sending only 1 agent to the initial spot may miss the target in large probability, because the agent may be killed by Jack. In another case, if Spot 5 is suitable for capturing and 10 agents are deployed there, PT(5, 10) may be over 80%. Of cause, PT(i, 0) is always 0.
According to the given matrix PT, you need to help Charlie to figure out the best way to deploy agents in which the probability of catching the robber reaches the maximum.
Let us assume that the town can be described as N spots (numbered from 0 to N-1) and M bidirectional roads between those N spots. Jack the Robber starts running from Spot 0. After several rounds of chasing and fleeing in the past, Don summarized Jack’s rules of escape:
1.He will never visit a spot more than once.
2.He is an expert about the geography of this town, so no matter which spot he reaches, the route he has traveled is always the shortest path from Spot 0 to that spot. To simplify the situation, we assume that there is only one shortest path from Spot 0 to any other spot.
3.He has no certain destination spot to go. He just runs AS FAR AS HE CAN, following the two rules above. As you may see, if he never gets caught, he will definitely come to a spot where he has to stop because if he keeps running, he will violate the two rules above. When he reaches a spot where he has to stop and is not arrested by FBI at that spot, he hides and FBI will never find him.
4.When he comes to a spot and is NOT captured by FBI at that spot, he will randomly choose a road to continue running. Of course, his choice can’t conflict with the above mentioned rules. The term “randomly” means that he chooses each valid road on the same probability.
Even if Jack gets to a spot where agents are already deployed, he may still get a chance to run away. For example, if the spot is very crowded, even all agents are deployed there, Jack may still run away easily. So Charlie finds out an N×(P+1) probability matrix PT. PT(i, j) represents the probability of j FBI agents deployed at spot i arresting Jack when Jack comes to Spot i. For example, PT(0, 1) can be only 5%, which means sending only 1 agent to the initial spot may miss the target in large probability, because the agent may be killed by Jack. In another case, if Spot 5 is suitable for capturing and 10 agents are deployed there, PT(5, 10) may be over 80%. Of cause, PT(i, 0) is always 0.
According to the given matrix PT, you need to help Charlie to figure out the best way to deploy agents in which the probability of catching the robber reaches the maximum.
Input
Input contains several test cases. In the first line of each case, there are two integers N (N<=100) and M (M<=10000), representing the number of spots and the number of roads between them.
Next M lines describe all roads. In each line, there are three integers a, b and c (0<=a, b<N, 0<c<=10000), representing a road of length c between Spot a and Spot b. Pay attention that there may be more than one roads between two spots, as well as some roads may come into a self-loop (a=b).
The following line contains an integer P (0<P<=50), representing the total number of agents. Following N lines describe the probability matrix PT. PT(i,j) (0<= PT(i,j)<=1) represents the probability that robber can be captured by j FBI agents in Spot i when he comes to Spot i . We don’t give the leftmost column of the matrix for they are all zero, so the matrix only has P columns. In other words, the first number you read from the matrix is PT(0,1) .
The input file ends with a line that contains “0 0".
Next M lines describe all roads. In each line, there are three integers a, b and c (0<=a, b<N, 0<c<=10000), representing a road of length c between Spot a and Spot b. Pay attention that there may be more than one roads between two spots, as well as some roads may come into a self-loop (a=b).
The following line contains an integer P (0<P<=50), representing the total number of agents. Following N lines describe the probability matrix PT. PT(i,j) (0<= PT(i,j)<=1) represents the probability that robber can be captured by j FBI agents in Spot i when he comes to Spot i . We don’t give the leftmost column of the matrix for they are all zero, so the matrix only has P columns. In other words, the first number you read from the matrix is PT(0,1) .
The input file ends with a line that contains “0 0".
Output
For each test case, output a single line with a real number, representing the largest probability that the robber can be captured if all agents are deployed in the best way. The answer needs to be transferred into percentage pattern and rounded to 2 digits after decimal point.
Sample Input
4 4 0 1 1 0 2 2 1 3 3 2 3 1 2 0.01 0.1 0.5 0.8 0.5 0.8 0.7 0.9 0 0
Sample Output
60.00
http://www.acmerblog.com/hdu-3409-chase-5435.html
struct Edge{ |
014 | int u,v,w; |
015 | int next; |
016 | void assign(int u_,int v_,int w_,int next_){ |
017 | u = u_; v = v_; w = w_; next = next_; |
018 | } |
019 | bool operator < (const Edge& e) const { |
020 | return w > e.w; //这个地方害我WA了6次；这错太隐蔽了!!!!。 |
021 | } |
022 | }edges[maxe]; |
023 |
024 | int head[maxn]; |
025 | vector<int> G[maxn]; |
026 | int cnt; |
027 | int N,M,P; |
028 | double PT[maxn][maxn/2]; |
029 | double dp[maxn][maxn/2]; //dp[i][j]表示以i为根、部署j个警察逮到robber的最大概率； |
030 |
031 |
032 | void addedge(int u,int v,int w){ |
033 | edges[cnt].assign(u,v,w,head[u]); |
034 | head[u] = cnt++; |
035 | edges[cnt].assign(v,u,w,head[v]); |
036 | head[v] = cnt++; |
037 | } |
038 | void Dijkstra(){ |
039 | priority_queue<Edge> Q; |
040 | int d[maxn]; |
041 | bool vis[maxn]; |
042 | memset(d,0x3f,sizeof(d)); |
043 | memset(vis,0,sizeof(vis)); |
044 | for(int i=0;i<N;i++) G[i].clear(); |
045 | Q.push((Edge){0,0,0}); |
046 | d[0] = 0; |
047 | while(!Q.empty()){ |
048 | Edge e = Q.top(); Q.pop(); |
049 | int u = e.u; |
050 | if(vis[u]) continue; |
051 | vis[u] = true; |
052 | if(e.u != e.v){ |
053 | G[e.v].push_back(e.u); |
054 | } |
055 | for(int i=head[u];i!=-1;i=edges[i].next){ |
056 | int v = edges[i].v; |
057 | if(d[v] > d[u] + edges[i].w){ |
058 | d[v] = d[u] + edges[i].w; |
059 | Q.push((Edge){v,u,d[v]}); //把u存进去是为了方便建最短路图； |
060 | } |
061 | } |
062 | } |
063 | } |
064 | void dfs(int u){ |
065 | int child = G[u].size(); |
066 | double son[maxn]; //son[i]表示u的所有儿子节点总共部署i个人逮住robber的概率； |
067 | for(int i=0;i<=P;i++) son[i] = 0; |
068 | if(child == 0){ |
069 | for(int i=1;i<=P;i++){ |
070 | dp[u][i] = PT[u][i]; |
071 | } |
072 | return; |
073 | } |
074 | for(int i=0;i<child;i++){ |
075 | int v = G[u][i]; |
076 | dfs(v); // 求出了dp[v][...]的所有不同概率； |
077 | for(int j=P;j>=0;j--) |
078 | for(int k=0;k<=j;k++) |
079 | son[j] = max(son[j],dp[v][k]/child+son[j-k]); //u的v这个儿子及其子节点部署k个人的最大概率； |
080 | } |
081 | for(int i=P;i>=0;i--) //总共i个人 |
082 | for(int j=0;j<=i;j++){ //u这个节点放j个人 |
083 | dp[u][i] = max(dp[u][i],PT[u][j] + (1-PT[u][j])* son[i-j]); |
084 | } |
085 | } |
086 | int main() |
087 | { |
088 | //freopen("E:\\acm\\input.txt","r",stdin); |
089 |
090 | while(scanf("%d%d",&N,&M) == 2 && N+M){ |
091 | cnt = 0; |
092 | memset(dp,0,sizeof(dp)); |
093 | memset(head,-1,sizeof(head)); |
094 | for(int i=1;i<=M;i++){ |
095 | int a,b,c; |
096 | scanf("%d%d%d",&a,&b,&c); |
097 | if(a == b) continue; |
098 | addedge(a,b,c); |
099 | } |
100 | scanf("%d",&P); |
101 | for(int i=0;i<N;i++) PT[i][0] = 0; |
102 | for(int i=0;i<N;i++) |
103 | for(int j=1;j<=P;j++){ |
104 | scanf("%lf",&PT[i][j]); |
105 | } |
106 | Dijkstra(); //形成以0为根的最短路树；存在G[u]中； |
107 |
108 | dfs(0); |
109 | double ans = 0; |
110 | for(int i=0;i<=P;i++) |
111 | ans = max(ans,dp[0][i]); |
112 | printf("%.2lf\n",ans*100); |
113 | } |
114 | } |
