专栏首页算法修养POJ-1926 Pollution

POJ-1926 Pollution

Pollution Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 4049 Accepted: 1076 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.

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:

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 <string.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;
int a[105][105];
int degree[105];
int n,m;
double c[105];
int vis[105];
void floyed()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(a[i][k]&&a[k][j]&&i!=j)
                    a[i][j]=1;
            }
        }
    }
}
int main()
{
    int t;
    int x,y;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%lf",&c[i]);
        memset(a,0,sizeof(a));
        memset(degree,0,sizeof(degree));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            if(!a[x][y])
            {
               a[x][y]=a[y][x]=1;
               degree[x]++;
               degree[y]++;
            }
        }
        floyed();
        for(int i=1;i<=n;i++)
        {
            if(vis[i])
                continue;
            vis[i]=1;
            double sum=0;
            double num=0;

            sum+=c[i];
            num+=degree[i];
            for(int j=1;j<=n;j++)
            {
                if(!vis[j]&&a[i][j])
                {
                    sum+=c[j];
                    num+=degree[j];
                }
            }
            if(num==0)
            {
                printf("%.3f\n",c[i]);
                continue;
            }
            double p=sum/(double)num;
            printf("%.3f\n",p*degree[i]);
            for(int j=1;j<=n;j++)
            {
                if(!vis[j]&&a[i][j])
                {
                    printf("%.3f\n",p*degree[j]);
                    vis[j]=1;
                }
            }
        }
        printf("\n");
    }
    return 0;

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ-2029 Get Many Persimmon Trees(动态规划)

    Get Many Persimmon Trees Time Limit: 1000MS Memory Limit: 30000K Total ...

    ShenduCC
  • POJ-2336 Ferry Loading II(简单DP)

    Ferry Loading II Time Limit: 1000MS Memory Limit: 65536K Total Submissi...

    ShenduCC
  • HOJ Recoup Traveling Expenses(最长递减子序列变形)

    A person wants to travel around some places. The welfare in his company can cov...

    ShenduCC
  • POJ-2029 Get Many Persimmon Trees(动态规划)

    Get Many Persimmon Trees Time Limit: 1000MS Memory Limit: 30000K Total ...

    ShenduCC
  • Yet Another Walking Robot (Map)

    There is a robot on a coordinate plane. Initially, the robot is located at the p...

    dejavu1zz
  • Common Pitfalls to Avoid when using HTML5 Application Cache

    Application Cache, also known as AppCache, has been a pretty hot topic with web ...

    IMWeb前端团队
  • Common Pitfalls to Avoid when using HTML5 Application Cache

    Application Cache, also known as AppCache, has been a pretty hot topic with web ...

    IMWeb前端团队
  • 基于最大主曲率算法和欧氏距离的指静脉识别 -----附带源码和解析文档

      暑假了就有时间写写博客了,大一的师弟们也要进入算法的领域了,于是我就写了一个简略版基于最大主曲率算法的指静脉识别给他们入门用,

    徐飞机
  • POJ-2336 Ferry Loading II(简单DP)

    Ferry Loading II Time Limit: 1000MS Memory Limit: 65536K Total Submissi...

    ShenduCC
  • poj-------------(2752)Seek the Name, Seek the Fame(kmp)

    Seek the Name, Seek the Fame Time Limit: 2000MS Memory Limit: 65536K Tot...

    Gxjun

扫码关注云+社区

领取腾讯云代金券