首页 > ACM题库 > HDU-杭电 > HDU 4318-Power transmission[解题报告]HOJ
2015
05-23

HDU 4318-Power transmission[解题报告]HOJ

Power transmission

问题描述 :

The project West-East power transmission is famous around the world. It transmits the electricity from western areas to east China. There are many nodes in the power system. Each node is connected with several other nodes in the system by cable. Power can be only transmitted between two connected nodes. For each node, it can’t send power to two or more other nodes at the same time.
As we have all known, power will be loss during the transmission. Bob is the chief engineer of the project. He wants to build a transmission line which send power from one node to another node and minimize the power loss at the same time. Now he asks you to help him solve the problem.

输入:

There are several test cases. For each test case, the first line contains an integer N (0 < N ≤ 50000) which represents the number of nodes in the power system. Then there will be N groups of data following. For the i-th(0 < i ≤ N) group, the first line is an integer ki (ki ≤ 50), which means the node i is connected with ki nodes. The rest of the i-th group data are divided into ki lines. Each line contains an integer ai (0 < ai ≤ N, ai ≠ i) and an integer bi (0 ≤ bi ≤ 100), which represents power can be transmitted from node i to ai and will loss bi% while transmitting. The last line of input data contains three integers separated by single spaces. The first one is s, the second is t (0 < s, t ≤ N), and the third is the total power M (0 < M ≤ 10^6) at node s.

输出:

There are several test cases. For each test case, the first line contains an integer N (0 < N ≤ 50000) which represents the number of nodes in the power system. Then there will be N groups of data following. For the i-th(0 < i ≤ N) group, the first line is an integer ki (ki ≤ 50), which means the node i is connected with ki nodes. The rest of the i-th group data are divided into ki lines. Each line contains an integer ai (0 < ai ≤ N, ai ≠ i) and an integer bi (0 ≤ bi ≤ 100), which represents power can be transmitted from node i to ai and will loss bi% while transmitting. The last line of input data contains three integers separated by single spaces. The first one is s, the second is t (0 < s, t ≤ N), and the third is the total power M (0 < M ≤ 10^6) at node s.

样例输入:

4
2
2 50
3 70
2
1 30
4 20
2
1 10
4 40
0
1 4 100

样例输出:

60.00
Hint
In the sample, the best transmission line is 1 -> 2 -> 4, loss power is 100 * 50% + 100 * (100%-50%)*20% = 60.00

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
const int maxn = 50005;
struct node
{
	int to;
	double val;
	int next;
}e[maxn*105];
int head[maxn];
double dp[maxn];
int tot;
int n;
int s,t,M;
void init()
{
	tot = 0;
	memset(head,-1,sizeof(head));
	memset(dp,0,sizeof(dp));
}
void addedge(int u, int v, double val)
{
	//printf("u = %d v = %d val = %.2lf\n",u,v,val);
	e[tot].to = v;
	e[tot].next = head[u];
	e[tot].val = val;
	head[u] = tot ++;
}

void SPFA()
{
	queue<int> q;
	q.push(s);
	dp[s] = 1.0;
	while(!q.empty()){
		int cur = q.front();
		q.pop();
		//printf("tp = %d\n",cur);
		for(int i=head[cur];i!=-1;i=e[i].next){
			int v = e[i].to;
			if(dp[cur]*e[i].val > dp[v]){
				dp[v] = dp[cur]*e[i].val;
				q.push(v);
			}
		}
	}
}
int main()
{
	while(cin >> n){	
	init();
	for(int i=0;i<n;i++){
		int k,v,val;
		cin >> k;
		while(k --){
			cin >> v >> val;
			v --;
			addedge(i,v,(100.0-val)/100.0);
		}
	}
	cin >> s >> t >> M;
	s--; t --;
	SPFA();
	if(dp[t] == 0)cout << "IMPOSSIBLE!\n";
	else printf("%.2lf\n",(1-dp[t])*M );
	//cout << (1-dp[t])*M << endl;
	}
}