注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

pku 1926 Pollution  

2009-11-22 21:35:20|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Description

The managers of a chemical plant, which is notorious for its high pollution, plan to adopt a newly developed device in order to reduce the amount of contaminants emitted. However, engineers in the plant are against this plan, as they doubt the usefulness of the device. As engineers only believe in experimental results, managers decide to hire programmers to make a numerical experiment to convince the engineers.

The new pollution-reducing device consists of several tanks with pipes connecting the tanks. You may assume there is at most one pipe between two tanks. Two tanks are called adjacent if a pipe connects them. When operating, the contaminant circulates in the device among these tanks.
pku 1926 Pollution - 东月之神 - 东月之神

As shown in the Figure-1, the contaminant in one tank in time t, will equally distribute into all adjacent tanks in the time t+1. In other words, if we use Xit to denote the amount of contaminant in tank i at time t, we can use the following formula:

pku 1926 Pollution - 东月之神 - 东月之神

where Iij=1 if tank i and tank j are adjacent, otherwise Iij=0, and where dj is the number of tanks adjacent to tank j. If no tank is adjacent to tank i, we have Xit+1=Xit.
The managers, as well as the engineers, want to know that given the initial amount of contaminant in each tank, how the contaminant will be distributed in all the tanks after a long period of time in circulation. Namely, given Xi0 for all i, what are Xit when the difference between Xit and Xit+1 is so small that it can be ignored. You may assume that this condition will ALWAYS be attained from an initial case in this problem.

Input

The first line of the input contains one integer T (1 <= T <= 10), the number of test cases. T cases then follow. For each test case, the first line consists of two integers: N and M where(1 <= N <= 100, 0 <= M <= N*(N-1)/2), is the number of tanks and pipes. The following N lines give the initial amount of contaminant for each tank, which are nonnegative real numbers and no larger than 100. Then the next M lines give the tanks that each pipe connects, as "A B" (1 <= A, B <= N, A != B) denotes there is a pipe between tank A and tank B.

Output

For each test case, output the final amount of contaminant Xit+1 (one per line), followed by a blank line. The number should be rounded to three digits after the decimal point.

Sample Input

2
3 3
1
0
0
1 2
2 3
3 1
4 4
1
0
0
1
1 2
2 3
3 1
3 4

Sample Output

0.333
0.333
0.333

0.500
0.500
0.750
0.250
 
代码如下:
#include <iostream>
#include <cstdio>
using namespace std;
double a[110], result[110], sumx;
int xx, yy, f[110], n, m, ll, c[110], v[110][110], sumy, b[110],hash[110];
void dfs(int k)
{
 sumx += a[k];
 sumy += f[k];
 hash[k] = 1;
 ++ll;
 c[ll] = k;
 for(int i = 0; i < b[k]; i++)
  if(hash[v[k][i]] == 0)
   dfs(v[k][i]);  
}
int main()
{
 int t, i, j, kk; 
 cin >> t;
 while(t--)
 {
  
  cin >> n >> m;
  for(i = 1; i <= n; i++)
   cin >> a[i];
  for(i = 1;i <= n; i++)
  {
   f[i] = 0;
   result[i] = 0;
   hash[i] = 0;
   b[i] = 0;
   for(j = 1; j <= n; j++)
    v[i][j] = 0;
  }
  for(i = 0; i < m; i++)
  {
   cin >> xx >> yy;
   v[xx][b[xx]] = yy;
   v[yy][b[yy]] = xx;
   b[xx]++;
   b[yy]++;
   f[xx]++;
   f[yy]++;
  }
  for(i = 1; i <= n; i++)
  {
   if(hash[i] == 0)
   {
    for(kk = 0; kk <= n; kk++) 
     c[kk] = 0;
    sumx = 0;
    sumy = 0;
    ll = -1;
    dfs(i);
    if(ll == 0) result[c[0]] = sumx;
    else
    {
     for(j = 0; j <= ll; j++)
      result[c[j]] = f[c[j]] * sumx / sumy;
    }
   }
  }
  for(i= 1; i <= n; i++)
    printf("%.3lf\n", result[i]);
  cout << endl;
 }
return 0;
}
  评论这张
 
阅读(152)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017