Codeforces 459E Pashmak and Graph：dp + 贪心

题目链接：http://codeforces.com/problemset/problem/459/E

题意：

　　给你一个有向图，每条边有边权。

　　让你找出一条路径，使得这条路径上的边权严格递增。

　　问你这样的路径最长有多长。

 

题解：

　　先将所有边按边权从小到大排序，以保证边权递增。

　　表示状态：

　　　　dp[i] = max len

　　　　表示以点i为终点时的最长路径长度。

 

　　找出答案：

　　　　ans = max dp[i]

 

　　如何转移：

　　　　枚举每条边e[i]，则有：

　　　　　　dp[e[i].t] = max(dp[e[i].t], dp[e[i].s]+1)

　　　　但是要注意，当枚举一些边的边权相同时，直接更新dp[e[i].t]是不行的。

　　　　比如一条链上的边权均相同的情况。

　　　　所以当边权相同时，先暂时将新的dp[e[i].t]存到f数组中，等这些边权相同的边枚举完之后，再用f数组更新dp。

 

　　边界条件：

　　　　set dp & f = 0

 

AC Code:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define MAX_N 300005

using namespace std;

struct Edge
{
    int s;
    int t;
    int len;
    Edge(int _s,int _t,int _len)
    {
        s=_s;
        t=_t;
        len=_len;
    }
    Edge(){}
    friend bool operator < (const Edge &a,const Edge &b)
    {
        return a.len<b.len;
    }
};

int n,m;
int ans=0;
int f[MAX_N];
int dp[MAX_N];
Edge edge[MAX_N];

void read()
{
    scanf("%d%d",&n,&m);
    int a,b,v;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&a,&b,&v);
        edge[i]=Edge(a,b,v);
    }
}

void work()
{
    sort(edge,edge+m);
    memset(dp,0,sizeof(dp));
    memset(f,0,sizeof(f));
    int pos=0;
    for(int i=0;i<m;i++)
    {
        Edge temp=edge[i];
        f[temp.t]=max(f[temp.t],dp[temp.s]+1);
        ans=max(ans,f[temp.t]);
        if(i==m-1 || temp.len!=edge[i+1].len)
        {
            while(pos<=i)
            {
                dp[edge[pos].t]=f[edge[pos].t];
                pos++;
            }
        }
    }
    printf("%d\n",ans);
}

int main()
{
    read();
    work();
}