Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题目链接 题意：给出n个点，m条边，定义一条路径的价值为【路径长度*(路径终点的度)】，求最大价值。 思路：一月份的时候写过一个回溯。。。TLE22了。。。其实也能猜到是dp..但是无奈不会写。然而其实真的不难== 我们枚举路径的终点，dp[i]表示以点i为终点能得到的最长路径长度。
转移方程：dp[i] = max(dp[i],dp[edge[i][j]]+1);
含义是与i点相连的j点是否要将i点加在以j点为路径末尾的路径的终点，使i点成为新的路径终点。
具体看代码
1/* ***********************************************
2Author :111qqz
3Created Time :2016年01月08日 星期五 21时55分26秒
4File Name :code/cf/#338/B.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=2E5+7;
34int n,m;
35vector<int>edge[N];
36LL ans;
37LL cur;
38LL dp[N];
39
40
41int main()
42{
43 #ifndef ONLINE_JUDGE
44 freopen("code/in.txt","r",stdin);
45 #endif
46 cin>>n>>m;
47 for ( int i = 0 ; i < m ; i ++)
48 {
49 int x,y;
50 scanf("%d %d",&x,&y);
51 edge[x].push_back(y);
52 edge[y].push_back(x);
53 }
54
55 for ( int i = 1 ; i <= n ; i++)
56 {
57 dp[i] = 1;
58 for (int j = 0 ; j < int(edge[i].size()) ; j++)
59 {
60 int v = edge[i][j];
61 dp[i] = max(dp[i],dp[v]+1);
62 }
63 ans = max(ans,LL(edge[i].size())*dp[i]);
64 }
65 cout<<ans<<endl;
66
67 #ifndef ONLINE_JUDGE
68 fclose(stdin);
69 #endif
70 return 0;
71}