`
java-mans
  • 浏览: 11343858 次
文章分类
社区版块
存档分类
最新评论

hdu4318 Power transmission 最短路 当数据很大的时候的解决办法 一道题目的解题全过程记录

 
阅读更多

Power transmission

Time Limit: 10000/5000 MS (Java/Others)Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 656Accepted Submission(s): 226


Problem Description
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.

Input
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.

Output
For each test case, output the minimum of loss power while transmitting from node s to node t. The result should be printed with two digits to the right of the decimal point. If power cannot be transmitted from node s to node t, output “IMPOSSIBLE!” in a line.

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

Sample Output
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



题意:

多个点 从一个点往另一个点运输天然气 但是从某点到另外一点是会有损耗的 题中输入的即为损耗的百分数 问从点s到t最少损耗多少

分析: 很明显是最短路问题

但是有个比较卡人的地方 就是最多会有50000个点 数据太大 用map数组存不下 会爆掉

这是我之前的代码 直接MLE 内存超出了


#include<stdio.h>
#include<string.h>
double map[30000+10][30000+10];
double min[30000+10];
int used[30000+10];
int s,t,M,flag,n;
double find_short()

{
	int i,j,pos;
	double mm;
	memset(used,0,sizeof(used));
	used[s]=1;
	for(i=1;i<=n;i++) 
		min[i]=map[s][i];
	min[s]=0;
	for(i=2;i<=n;i++)
	{
		mm=999999999;
		for(j=1;j<=n;j++)
		{
			if(!used[j]&&mm>min[j])
			{
				pos=j;mm=min[j];
			}
		}
		if(mm==999999999) {flag=1;return 0;}
		used[pos]=1;
		for(j=1;j<=n;j++)
		{
			if(!used[j]&&min[pos]+(1.0-min[pos])*map[pos][j]<min[j])
				min[j]=min[pos]+(1.0-min[pos])*map[pos][j];
		}
	}
	return min[t];
}
void init()
{
	int i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			map[i][j]=1;

}
int main()
{
	int i,m,x,y;
	double val,k;
	while(scanf("%d",&n)!=EOF)
	{
		flag=0;
		init();
		for(i=1;i<=n;i++)
		{
			scanf("%d",&m);
			while(m--)
			{
				scanf("%d %d",&x,&y);
				val=y/100.0;
				map[i][x]=val;
			}
		}
		scanf("%d %d %d",&s,&t,&M);
		k=find_short();
		if(flag==1) {printf("IMPOSSIBLE!\n");continue;}
		printf("%.2lf\n",k*M);
	}
	return 0;
}





我们考虑到用链表 就用了数组去模拟链表 保存从当前点能到达的点

队长把写解题报告的任务光荣的交给了我 但是我对看代码表示相当的纠结 所以就自己去写了个 好理解 把自己的贴上

/*
#include<stdio.h>
#include<string.h>
struct haha
{
	int son[55];   //记录从当前点到其它能走到的点
	double son_val[55];  //记录从当前点到其它能走到的点的消耗
	int cnt;//记录存取的儿子个数
}a[50100];
int n,flag,s,t,M,used[50100];
double min[50100];
double find_short()//模拟以前数据比较小的时候的模板
{
      int i,j,pos,cnt;
	  double mm;
	  memset(used,0,sizeof(used));
	  for(i=1;i<=n;i++) min[i]=1;
	  cnt=a[s].cnt;
	  while(cnt--)
	  {
		  min[a[s].son[cnt]]=a[s].son_val[cnt];
	  }
	  used[s]=1;
	  min[s]=0;
	  for(i=2;i<=n;i++)
	  {
		  mm=1;
		  for(j=1;j<=n;j++)
		  {
			  if(!used[j]&&mm>min[j])
			  {
				  pos=j;
				  mm=min[j];
			  }
		  }
		  if(mm==1) {flag=1;return 0;}
		  used[pos]=1;
		  cnt=a[pos].cnt;
	      for(j=0;j<cnt;j++)
		  {
		       if(!used[a[pos].son[j]]&&min[pos]+(1.0-min[pos])*a[pos].son_val[j]<min[a[pos].son[j]])
				     min[a[pos].son[j]]=min[pos]+(1.0-min[pos])*a[pos].son_val[j];
		  }
		
         if(pos==t) return min[t];//这里很重要 不加会超时的哦 
	  }
	  return min[t];

}
int main()
{
	int i,m,x,y;
	double val,k;
	while(scanf("%d",&n)!=EOF)
	{
		flag=0;
		for(i=1;i<=n;i++)
		    a[i].cnt=0;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&m);
			while(m--)
			{
				scanf("%d %d",&x,&y);
				val=y/100.0;
				a[i].son[a[i].cnt]=x;
				a[i].son_val[a[i].cnt++]=val;
			}
		}
	    scanf("%d %d %d",&s,&t,&M);
		k=find_short();
		if(flag==1) {printf("IMPOSSIBLE!\n");continue;}
		printf("%.2lf\n",k*M);
	}
	return 0;
}
*/





为了赶制解题报告 所以我自己写了下(因为比赛时写一半了 所以会比较快) 我就没有很深入的分析队长的代码 我会认真分析下的 因为一个队伍里相互分析代码

对队伍成长非常好的 贴下队长的代码



/*#include <stdio.h>
int v[1003];
struct st
{
	int tt;
    double v;
}dp[50002][52],ds[50002];
int dk[50002];
int end;
void dj(int m,int n)
{
    int i,j,k;
    int max_nu;
	double max;
	for(i=1;i<=n;i++)
    {
		v[i]=0;
		ds[i].v=0;
	}
    ds[m].v=1;
    for(i=1;i<=n;i++)
    {
        max=0;
        for(j=1;j<=n;j++)
        {
            if(ds[j].v>max&&v[j]==0)
            {
                max=ds[j].v;
                max_nu=j;
            }
        }
        v[max_nu]=1;
		int k;
		for(j=0;j<dk[max_nu];j++)
		{
			if(v[dp[max_nu][j].tt]==0&&ds[dp[max_nu][j].tt].v<ds[max_nu].v*dp[max_nu][j].v)
			{
                ds[dp[max_nu][j].tt].v=ds[max_nu].v*dp[max_nu][j].v;
			}
		}
		if(max_nu==end)
			break;
    }
}
int main()
{
    int i,j,m,n,kk;
    int a,b,c1,c2;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=1;i<=50;i++)
		{
			for(j=1;j<=n;j++)
			{
				dp[j][i].v=0;
			}
		}
		for(i=1;i<=n;i++)
		{
	    	scanf("%d",&dk[i]);
			for(kk=0;kk<dk[i];kk++)
			{
				scanf("%d%d",&a,&b);
				dp[i][kk].v=(double)(100-b)/100.0;
				dp[i][kk].tt=a;
			}
		}
		int st;
		double vau;
		scanf("%d%d%lf",&st,&end,&vau);
		dj(st,n);
		vau=(1-ds[end].v)*vau;
		printf("%.2lf\n",vau);
	}
	return 0;
}*/





分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics