CodeForces 615B Longtail Hedgehog

题目:

http://codeforces.com/problemset/problem/615/B

题意:题目描述很复杂,但实际上很简单。大意就是连续的几个点组成尾巴,要求尾巴的长度乘以尾巴终点的分支数的最大值,其中尾巴要满足的条件是有边相连,且尾巴上节点的编号一定是递增的,终点是最大值。

我刚开始的想法是,先用邻接表保存这个无向图(矩阵保存不了),在读取边的时候,用一个数组保存每个节点的分支数,然后用深搜,遍历尾巴的最大长度,同时每扩展一个点,用当前长度乘以该点的分支数,并不断更新这个最大值,最后输出。然后各种超时,自己尝试加了些剪枝还是过不了。

与舍友讨论过后,又有了新的优化思路:

  1. 首先是不用保存无向图,因为尾巴上的节点要求递增,所以只需要保存起点比终点小的有向图即可。
  2. 开一个数组,记录以当前节点为终点的尾巴的最大长度。
  3. 放弃搜索的方式,直接用结构体保存每一条边,然后对边进行排序,再从前往后扫描,对每条边终点的尾巴长度进行更新

PS:记得用long long

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #define maxn 111111
 4 #define maxm 222222
 5 using namespace std;
 6 struct node{
 7     int u;
 8     int v;
 9 };
10 node e[maxm];
11 long long spine[maxm],tail[maxm];
12 bool cmp(node a,node b){
13     if(a.u == b.u)
14         return a.v < b.v;
15     else
16         return a.u < b.u;
17 }
18 int main(){
19     int n,m;
20     scanf("%d%d",&n,&m);
21     int u,v;
22     for(int i = 1;i<=m;i++){
23         scanf("%d%d",&u,&v);
24         e[i].u = min(u,v);
25         e[i].v = max(u,v);
26         spine[u]++;
27         spine[v]++;
28     }
29     sort(e+1,e+1+m,cmp);
30     for(int i = 1;i<=m;i++){
31         //这里要取max,因为有可能一个节点同时是两个尾巴的终点 
32         tail[e[i].v] = max(tail[e[i].u]+1,tail[e[i].v]);
33     }
34     long long ans = 0;
35     for(int i = 1;i<=n;i++)
36         ans = max(ans,(tail[i]+1)*spine[i]);//要加1,因为初始tail数组都是0,没有算上起始点 
37     printf("%I64d
",ans);
38 } 
原文地址:https://www.cnblogs.com/zqy123/p/5337781.html