CodeForces 615B Longtail Hedgehog
사고방식: 단순 DP, dp[i]=max(dp[i], dp[j]+1) 그리고 한 번 뛰면 돼요.
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100005;
#define LL long long
int dp[maxn];
vector<int>e[maxn];
int cnt[maxn];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for (int i = 1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
if (u<v)
swap(u,v);
e[u].push_back(v);
cnt[u]++;
cnt[v]++;
}
LL ans = 0;
for (int i = 1;i<=n;i++)
{
for (int j = 0;j<e[i].size();j++)
dp[i]=max(dp[i],dp[e[i][j]]);
dp[i]++;
ans = max(ans,1LL*dp[i]*cnt[i]);
}
printf("%lld
",ans);
}
Description
This Christmas Santa gave Masha a magic picture and a pencil. The picture consists of n points connected by m segments (they might cross in any way, that doesn't matter). No two segments connect the same pair of points, and no segment connects the point to itself. Masha wants to color some segments in order paint a hedgehog. In Mashas mind every hedgehog consists of a tail and some spines. She wants to paint the tail that satisfies the following conditions:
Masha defines the length of the tail as the number of points in it. Also, she wants to paint some spines. To do so, Masha will paint all the segments, such that one of their ends is the endpoint of the tail. Masha defines the beauty of a hedgehog as the length of the tail multiplied by the number of spines. Masha wants to color the most beautiful hedgehog. Help her calculate what result she may hope to get.
Note that according to Masha's definition of a hedgehog, one segment may simultaneously serve as a spine and a part of the tail (she is a little girl after all). Take a look at the picture for further clarifications.
Input
First line of the input contains two integers n and m(2 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000) — the number of points and the number segments on the picture respectively.
Then follow m lines, each containing two integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — the numbers of points connected by corresponding segment. It's guaranteed that no two segments connect the same pair of points.
Output
Print the maximum possible value of the hedgehog's beauty.
Sample Input
Input
8 6
4 5
3 5
2 5
1 2
2 8
6 7
Output
9
Input
4 6
1 2
1 3
1 4
2 3
2 4
3 4
Output
12
Hint
The picture below corresponds to the first sample. Segments that form the hedgehog are painted red. The tail consists of a sequence of points with numbers 1, 2 and 5. The following segments are spines: (2, 5), (3, 5) and (4, 5). Therefore, the beauty of the hedgehog is equal to 3·3 = 9.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.