正文
nyoj 1208——水题系列——————【dp】
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
水题系列时间限制：1000 ms | 内存限制：65535 KB难度：2
- 给你一个有向图，每条边都有一定的权值，现在让你从图中的任意一点出发，每次走的边的权值必须必上一次的权值大的情况下，问你最多能走几条边？
- 首先一个n和m，分别表示点的数目和边的数目
接下来m行，每行三个值x,y,val，表示x到y有路，其权值为val。（1<n,m，val<10^5,0<x,y<=n） - 输出最多有的边的数目
3 3
1 2 1
2 3 1
3 1 1
6 7
1 2 1
3 2 5
2 4 2
2 5 2
2 6 9
5 4 3
4 3 41
6解题思路：这个题目刚看起来好像是图论，但是出题人是考察的dp思想。定义两个数组dp[i],g[i]分别表示边编号为i时的最多有向边及点为i时的最多有向边数目。转移方程为：
如果边权不相同：dp[i]=g[E[i].st]+1,g[E[i].en]=max(g[E[i].en],dp[i])。
如果边权相同：{i,i+1,i+2,i+3...}边集合中都为边权相同的边编号。
dp[i]=g[E[i].st]+1,dp[i+1]=g[E[i+1].st]+1，etc...
g[E[i].en]=dp[i],g[E[i+1].en]=dp[i+1]，etc...
对于边权相同的情况，第一组样例可以看出问题，这里这种操作学长说是延迟，具体说应该是对点延迟，对边提前。#include<bits/stdc++.h>
using namespace std;
const int maxe=1e5+10;
struct edge{
int st,en;
int val;
}E[maxe];
int dp[maxe],g[maxe];
int INF=1e9;
bool cmp(edge a,edge b){
return a.val<b.val;
}
void solve(int n,int m){
memset(dp,0,sizeof(dp));
memset(g,0,sizeof(g));
for(int i=0;i<m;i++){
if(E[i].val<E[i+1].val){
dp[i]=g[E[i].st]+1;
g[E[i].en]=max(g[E[i].en],dp[i]);
}else{
int j,t=i;
for( j=i;j<m;j++){
if(E[j].val!=E[j+1].val)
break;
}
i=j;
for(int k=t;k<=j;k++){
dp[k]=g[E[k].st]+1;
}
for(int k=t;k<=j;k++){
g[E[k].en]=max(g[E[k].en],dp[k]);
}
}
}
int max_e=0;
// for(int i=1;i<=n;i++){ //遍历点跟边应该是相同的效果，但是后台的测试数据不过。。。
// if(g[i]>max_e){
// max_e=g[i];
// }
// }
for(int i=0;i<m;i++){
if(max_e<dp[i]){
max_e=dp[i];
}
}
printf("%d\n",max_e);
}
int main(){
freopen("In.txt","r",stdin);
freopen("OUT1.txt","w",stdout);
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=0;i<m;i++){
scanf("%d%d%d",&E[i].st,&E[i].en,&E[i].val);
}
sort(E,E+m,cmp);
E[m].val=INF;
solve(n,m);
}
return 0;
}
