codeforces 459E E. Pashmak and Graph(dp)
3121 단어 dpcodeforces
제목 링크:
codeforces 459E
제목 대의:
n개의 점, m변의 유방향도를 제시하고 각 변은 변권이 있으며 가장 긴 변권이 상승하는 경로의 길이를 구한다.
제목 분석:
4
4
4
그래서 dp[i]=g[e[i].u]+1
4
AC 코드:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define MAX 300007
using namespace std;
int n,m;
int dp[MAX],g[MAX];
struct Edge
{
int u,v,w;
bool operator < ( const Edge& a ) const
{
return w < a.w;
}
}e[MAX];
int main ( )
{
while ( ~scanf ( "%d%d" , &n , &m ) )
{
for ( int i = 0 ; i < m ; i++ )
scanf ( "%d%d%d" , &e[i].u , &e[i].v , &e[i].w );
sort ( e , e+m );
int t = 0;
e[m].w = -1;
int ans = 0;
for ( int i = 0 ; i < m ; i++ )
{
int v = e[i].v;
int u = e[i].u;
int w = e[i].w;
dp[i] = g[e[i].u]+1;
if ( e[i].w != e[i+1].w )
{
for ( int j = t ; j <= i ; j++ )
g[e[j].v] = max ( g[e[j].v] , dp[j] );
t = i+1;
}
ans = max ( ans , dp[i] );
}
printf ( "%d
" , ans );
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
