luogu 1453 城市环路

题目背景

一座城市，往往会被人们划分为几个区域，例如住宅区、商业区、工业区等等。B市就被分为了以下的两个区域——城市中心和城市郊区。在着这两个区域的中间是一条围绕B市的环路，环路之内便是B市中心。

题目描述

整个城市可以看做一个N个点，N条边的单圈图(保证图连通)，唯一的环便是绕城的环路。保证环上任意两点有且只有2条路径互通。图中的其它部分皆隶属城市郊区。

现在，有一位名叫Jim的同学想在B市开店，但是任意一条边的2个点不能同时开店，每个点都有一定的人流量Pi，在该点开店的利润就等于该店的人流量Pi×K(K≤10000)，K的值将给出。

Jim想尽量多的赚取利润，请问他应该在哪些地方开店？

输入格式

第一行一个整数N 代表城市中点的个数。城市中的N个点由0~N-1编号。

第二行N个正整数，表示每个点的人流量Pi(Pi≤10000)。

下面N行，每行2个整数A,B，表示A，B建有一条双向路。

最后一行一个实数K。

输出格式

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

输入输出样例

输入 #1

输出 #1

12.0

说明/提示

【数据范围】

对于20%的数据，N≤100.

对于另外20%的数据，环上的点不超过2000个

对于50%的数据 N≤50000.

对于100%的数据 N≤100000.

分析

骑士的简化版本

因为这图联通，

骑士我连的单向边，这一次连双向边，用i^1找反向边，size从1开始

连双向边，找环的时候标记会简单一点

代码

  1 /*********************
  2 User:Mandy.H.Y
  3 Language:c++
  4 Problem:luogu2607
  5 Algorithm: 
  6 *********************/
  7 //这题双向边 
  8 //找环的时候为了避免走了自己的反向边，
  9 //可以带参，带上一条边的编号
 10 //用i^1找反向边，不过要size初值为1便于找反向边
 11 #include<bits/stdc++.h>
 12 
 13 using namespace std;
 14 
 15 const int maxn = 1e5 + 5;
 16 
 17 int n,size = 1,first[maxn];
 18 //size == 1
 19 int r1,r2;
 20 long long val[maxn];
 21 long long dp[maxn][3];
 22 bool vis[maxn];
 23 double k;
 24 
 25 struct Edge{
 26     int v,nt;
 27 }edge[maxn << 1]; 
 28 
 29 template<class T>inline void read(T &x){
 30     x = 0;bool flag = 0;char ch = getchar();
 31     while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
 32     while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
 33     if(flag) x = -x;
 34 }
 35 
 36 template<class T>void putch(const T x){
 37     if(x > 9) putch(x / 10);
 38     putchar(x % 10 | 48);
 39 }
 40 
 41 template<class T>void put(const T x){
 42     if(x < 0) putchar('-'),putch(-x);
 43     else putch(x);
 44 }
 45 
 46 void file(){
 47     freopen("1453.in","r",stdin);
 48 //    freopen("1453.out","w",stdout);
 49 }
 50 
 51 void eadd(int u,int v){
 52     edge[++size].v = v;
 53     edge[size].nt = first[u];
 54     first[u] = size;
 55 } 
 56 
 57 void readdata(){
 58     read(n);
 59     for(int i = 0;i < n; ++ i) read(val[i]);
 60     //从0开始 
 61     for(int i = 1;i <= n; ++ i){
 62         int u,v;
 63         read(u);read(v);
 64         eadd(u,v);eadd(v,u);
 65     }
 66     scanf("%lf",&k);
 67 }
 68 
 69 void find_circle(int u,int e){
 70     vis[u] = 1;
 71     for (int i = first[u];i;i = edge[i].nt){
 72         int v = edge[i].v;
 73         if((i^1)==e) continue;
 74         if(vis[v]) {
 75             r1 = u;
 76             r2 = v;
 77             continue;
 78         }
 79         find_circle(v,i);
 80     }
 81 }
 82 
 83 void dfs(int u,int rt,int fa){
 84     dp[u][0] = 0;
 85     dp[u][1] = val[u];
 86     for(int i = first[u];i;i = edge[i].nt){
 87         int v = edge[i].v;
 88         if(v == fa) continue;
 89         if(v == rt) continue;
 90         dfs(v,rt,u);
 91         dp[u][0] += max(dp[v][0],dp[v][1]);
 92         dp[u][1] += dp[v][0];
 93     }
 94 }
 95 
 96 void work(){
 97     find_circle(1,-1);
 98     long long cur = -100;
 99     dfs(r1,r1,r2);
100     cur = max(cur,dp[r1][0]);
101     dfs(r2,r2,r1);
102     cur = max(cur,dp[r2][0]);
103     printf("%.1lf",cur * k);
104 }
105 
106 int main(){
107 //    file();
108     readdata();
109     work();
110     return  0;
111 }

View Code