首页 > 代码库 > BSOJ3760||洛谷P1453 城市环路 题解
BSOJ3760||洛谷P1453 城市环路 题解
城市环路
Description
一座城市，往往会被人们划分为几个区域，例如住宅区、商业区、工业区等等。B市就被分为了以下的两个区域——城市中心和城市郊区。在着这两个区域的中间是一条围绕B市的环路，环路之内便是B市中心。
整个城市可以看做一个N个点，N条边的单圈图(保证图连通)，唯一的环便是绕城的环路。保证环上任意两点有且只有2条路径互通。图中的其它部分皆隶属城市郊区。
现在，有一位名叫Jim的同学想在B市开店，但是任意一条边的2个点不能同时开店，每个点都有一定的人流量Pi，在该点开店的利润就等于该店的人流量Pi×K(K≤10000)，K的值将给出。
Jim想尽量多的赚取利润，请问他应该在哪些地方开店？
整个城市可以看做一个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。
第二行N个正整数，表示每个点的人流量Pi(Pi≤10000)。
下面N行，每行2个整数A,B，表示A，B建有一条双向路。
最后一行一个实数K。
Output
输出仅一个实数M，（保留1位小数），代表开店的最大利润。
Sample Input
41 2 1 50 10 21 21 32
Sample Output
12.0
Hint
【数据范围】
对于20%的数据 N≤100.
对于50%的数据 N≤2000.
对于100%的数据 N≤100000.
对于20%的数据 N≤100.
对于50%的数据 N≤2000.
对于100%的数据 N≤100000.
↑以上是正经的题目描述XD
↓接下来是一点也不正经的题解啦
题目已经很明确了，这是个环，环上还有树。
就像这样：
乍一看会很麻烦对吧......那么我们先来考虑一下比较简单的情况。假如这一开始就只是个环呢？
那很简单啊，只要随便找个点开始，选择它跑一圈，不选它再跑一圈，取个最大值就行了嘛。
那么，加上树有什么影响呢？
没有。对，没有。只要提前把这个点引出去的树处理好就行了。
也就是说，只需要先对这棵子树进行一次动态规划，然后把这里能取到的最大值当做这个点的权值，这题就成了环形DP裸题啦23333。
主要流程：
①：Tarjan法先找出图中唯一的环。
②：枚举环上的每个点进行树形DP。
③：跑一遍环上DP。
听说这个东西好像叫环套树来着...去看了看其他几道环套树都好可怕啊QAQ
AC Code：
View Code
#include<cstring>#include<cstdio>#include<cmath>#include<stack>#include<iostream>#include<algorithm>using namespace std;inline const int Read(){ int Num=0,Sgn=1; char ch=getchar(); while(!isdigit(ch)){if(ch==‘-‘)Sgn=-1;ch=getchar();} while(isdigit(ch)){Num=(Num<<1)+(Num<<3)+ch-‘0‘;ch=getchar();} return Num*Sgn;}struct Edge{ int Next,To;}e[200005];int h[200005]={0},Cnt=0;void Addedge(int x,int y){e[++Cnt]=(Edge){h[x],y}; h[x]=Cnt;}int a[200005]={0};double K;int N;int Scnt=0;int DFN[200005]={0},Lowlink[200005]={0};int Cir[200005]={0},Belong[200005]={0},Prt[200005]={0};int f[200005][2]={0},g[200005][2]={0};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[0]]=t; Belong[t]=1; }while(t!=x); }}void DFS(int x){ f[x][0]=0; f[x][1]=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][0]+=max(f[y][1],f[y][0]); f[x][1]+=f[y][0]; } }}int main(){ N=Read(); for(int i=1;i<=N;i++) a[i]=Read(); for(int i=1;i<=N;i++) { int Tx=Read(),Ty=Read(); Addedge(Tx+1,Ty+1); Addedge(Ty+1,Tx+1); } scanf("%lf",&K); Tarjan(1); int M=Cir[0]; memset(Prt,0,sizeof(Prt)); for(int i=1;i<=M;i++) DFS(Cir[i]); for(int i=1;i<=M;i++) { g[i][0]=f[Cir[i]][0]; g[i][1]=f[Cir[i]][1]; } f[2][0]=g[1][0]+g[2][0]; f[2][1]=g[1][0]+g[2][1]; for(int i=3;i<=M;i++) { f[i][1]=f[i-1][0]+g[i][1]; f[i][0]=max(f[i-1][0],f[i-1][1])+g[i][0]; } int Ans=0; Ans=max(f[M][1],max(Ans,f[M][0])); f[2][0]=g[1][1]+g[2][0]; f[2][1]=-0x3f3f3f3f; for(int i=3;i<=M;i++) { f[i][0]=max(f[i-1][0],f[i-1][1])+g[i][0]; f[i][1]=f[i-1][0]+g[i][1]; } Ans=max(Ans,f[M][0]); printf("%.1lf\n",(double)Ans*K); return 0;}
一开始忘了环形要跑两遍...真是⑨一般的错误啊（笑）
BSOJ3760||洛谷P1453 城市环路 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。