BSOJ3760||洛谷P1453 城市环路题解

城市环路

Description

　　一座城市，往往会被人们划分为几个区域，例如住宅区、商业区、工业区等等。B市就被分为了以下的两个区域——城市中心和城市郊区。在着这两个区域的中间是一条围绕B市的环路，环路之内便是B市中心。
　　整个城市可以看做一个N个点，N条边的单圈图(保证图连通)，唯一的环便是绕城的环路。保证环上任意两点有且只有2条路径互通。图中的其它部分皆隶属城市郊区。
　　现在，有一位名叫Jim的同学想在B市开店，但是任意一条边的2个点不能同时开店，每个点都有一定的人流量Pi，在该点开店的利润就等于该店的人流量Pi×K(K≤10000)，K的值将给出。
　　Jim想尽量多的赚取利润，请问他应该在哪些地方开店？

Input

　　第一行一个整数N 代表城市中点的个数。城市中的N个点由0~N-1编号。
　　第二行N个正整数，表示每个点的人流量Pi(Pi≤10000)。
　　下面N行，每行2个整数A,B，表示A，B建有一条双向路。
　　最后一行一个实数K。

Output

　　输出仅一个实数M，（保留1位小数），代表开店的最大利润。

Sample Input

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

Sample Output

12.0

Hint

【数据范围】
　　对于20%的数据 N≤100.
　　对于50%的数据 N≤2000.
　　对于100%的数据 N≤100000.

↑以上是正经的题目描述XD

↓接下来是一点也不正经的题解啦

题目已经很明确了，这是个环，环上还有树。

就像这样：

乍一看会很麻烦对吧......那么我们先来考虑一下比较简单的情况。假如这一开始就只是个环呢？

那很简单啊，只要随便找个点开始，选择它跑一圈，不选它再跑一圈，取个最大值就行了嘛。

那么，加上树有什么影响呢？

没有。对，没有。只要提前把这个点引出去的树处理好就行了。

也就是说，只需要先对这棵子树进行一次动态规划，然后把这里能取到的最大值当做这个点的权值，这题就成了环形DP裸题啦23333。

主要流程：

①：Tarjan法先找出图中唯一的环。

②：枚举环上的每个点进行树形DP。

③：跑一遍环上DP。

听说这个东西好像叫环套树来着...去看了看其他几道环套树都好可怕啊QAQ

AC Code：

#include<cstring>

#include<cstdio>

#include<cmath>

#include<stack>

#include<iostream>

#include<algorithm>

using namespace std;

inline const int Read()

{

    int Num=,Sgn=;

    char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')Sgn=-;ch=getchar();}

    while(isdigit(ch)){Num=(Num<<)+(Num<<)+ch-'';ch=getchar();}

    return Num*Sgn;

}

struct Edge

{

    int Next,To;

}e[];

int h[]={},Cnt=;

void Addedge(int x,int y){e[++Cnt]=(Edge){h[x],y}; h[x]=Cnt;}

int a[]={};

double K;

int N;

int Scnt=;

int DFN[]={},Lowlink[]={};

int Cir[]={},Belong[]={},Prt[]={};

int f[][]={},g[][]={};

stack<int>Sta;

void Tarjan(int x)

{

    Scnt++;

    DFN[x]=Scnt; Lowlink[x]=Scnt;

    Sta.push(x);

    for(int i=h[x];i;i=e[i].Next)

    {

        int y=e[i].To;

        if(!DFN[y])

        {

            Prt[y]=x;

            Tarjan(y);

            Lowlink[x]=min(Lowlink[x],Lowlink[y]);

        }

        else if(Prt[x]!=y)

          Lowlink[x]=min(Lowlink[x],DFN[y]);

    }

    if(Lowlink[x]==DFN[x])

    {

        if(Sta.top()==x)

        {

            Sta.pop();

            return;

        }

        int t;

        do

        {

            t=Sta.top(); Sta.pop();

            Cir[++Cir[]]=t;

            Belong[t]=;

        }while(t!=x);

    }

}

void DFS(int x)

{

    f[x][]=; f[x][]=a[x];

    for(int i=h[x];i;i=e[i].Next)

    {

        int y=e[i].To;

        if(Prt[x]!=y&&!Belong[y])

        {

            Prt[y]=x;

            DFS(y);

            f[x][]+=max(f[y][],f[y][]);

            f[x][]+=f[y][];

        }

    }

}

int main()

{

    N=Read();

    for(int i=;i<=N;i++)

      a[i]=Read();

    for(int i=;i<=N;i++)

    {

        int Tx=Read(),Ty=Read();

        Addedge(Tx+,Ty+); Addedge(Ty+,Tx+);

    }

    scanf("%lf",&K);

    Tarjan();

    int M=Cir[];

    memset(Prt,,sizeof(Prt));

    for(int i=;i<=M;i++)

      DFS(Cir[i]);

    for(int i=;i<=M;i++)

    {

        g[i][]=f[Cir[i]][];

        g[i][]=f[Cir[i]][];

    }

    f[][]=g[][]+g[][];

    f[][]=g[][]+g[][];

    for(int i=;i<=M;i++)

    {

        f[i][]=f[i-][]+g[i][];

        f[i][]=max(f[i-][],f[i-][])+g[i][];

    }

    int Ans=;

    Ans=max(f[M][],max(Ans,f[M][]));

    f[][]=g[][]+g[][];

    f[][]=-0x3f3f3f3f;

    for(int i=;i<=M;i++)

    {

        f[i][]=max(f[i-][],f[i-][])+g[i][];

        f[i][]=f[i-][]+g[i][];

    }

    Ans=max(Ans,f[M][]);

    printf("%.1lf\n",(double)Ans*K);

    return ;

}

一开始忘了环形要跑两遍...真是⑨一般的错误啊（笑）

巴特西

BSOJ3760||洛谷P1453 城市环路题解

城市环路

Description

Input

Output

Sample Input

Sample Output

Hint

最新文章

热门文章

巴特西

BSOJ3760||洛谷P1453 城市环路 题解

城市环路

Description

Input

Output

Sample Input

Sample Output

Hint

最新文章

热门文章

BSOJ3760||洛谷P1453 城市环路题解