http://codeforces.com/contest/459/problem/E
不明确的是我的代码为啥AC不了，我的是记录we[i]以i为结尾的点的最大权值得边，然后wa在第35 36组数据
然后參考答案了，然后----网上一份题解
大意： 给出一个带权有向图，求经过的边权绝对上升的最长路径（可能是非简单路径，就可以能经过一个点多次）所包括的边数。
题解： 对边按权值排序后，从小到大搞。
设q[x]为已经搞过的边组成的以x点为终点的最长路径包括的边数。
设当前边e[i]为从u到v的边，因为我们是按权值排序好的，仅仅要没有同样的权值，我们就能够q[v]=max(q[v], q[u]+1)。
可是是有同样的权值的，我们直接这样搞，同样权值的可能会连出一条路，是不符合要求的，像第一个例子会输出3，怒萎。
所以同样权值的要特殊搞。我希望同样权值的不是一个个更新，而是一起更新，所以我把同样权值的先不更新，而是压入vector中，统计完这个权值的全部边，再将其一起从vector中取出更新。发现，有些同样权值的边连到的是同一个点，我希望用更长的路来更新这个点，所以对vector排序，后更新更长的。
AC代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std; #define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)
const ll ll_INF = ((ull)(-1))>>1;
const double EPS = 1e-8;
const int INF = 100000000;
const int MAXN = 4*(1e6)+100;
struct Edge
{
int from,to,w;
}e[MAXN];
int n,m;
int dp[MAXN],we[MAXN]; inline void add(int u,int v,int w,int k)
{
e[k].from=u;
e[k].to=v;
e[k].w=w;
} void init()
{
CL(dp,0);
CL(we,0);
//same.clear();
} bool cmp(const Edge a, const Edge b)
{
return a.w<b.w;
} int main()
{
//IN("E.txt");
int u,v,w;
while(~scanf("%d%d",&n,&m))
{
init();
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w,i);
}
sort(e,e+m,cmp);
int mmax=0;
for(int i=0,pos=0;i<m;i++)
{
dp[i]=we[e[i].from]+1;
if(e[i].w!=e[i+1].w)
{
for(int j=pos;j<=i;j++)
{
we[e[j].to]=max(we[e[j].to],dp[j]);
}
pos=i+1;
}
mmax=max(mmax,dp[i]);
} printf("%d\n",mmax);
}
return 0;
}
WA而不知道原因的代码，就是记录最大权值的结尾
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std; #define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)
const ll ll_INF = ((ull)(-1))>>1;
const double EPS = 1e-8;
const int INF = 100000000;
const int MAXN = 4*(1e6)+100;
struct Edge
{
int from,to,w;
}e[MAXN];
int n,m;
int dp[MAXN],we[MAXN]; inline void add(int u,int v,int w,int k)
{
e[k].from=u;
e[k].to=v;
e[k].w=w;
} void init()
{
CL(dp,0);
CL(we,0);
} bool cmp(const Edge a, const Edge b)
{
if(a.w!=b.w)
return a.w<b.w;
else
{
if(a.from!=b.from)
return a.from<b.from;
else
return a.to<b.to;
}
} int main()
{
//IN("E.txt");
int u,v,w;
while(~scanf("%d%d",&n,&m))
{
init();
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w,i);
}
sort(e,e+m,cmp);
int mmax=0;
for(int i=0;i<m;i++)
{
u=e[i].from;
v=e[i].to;
if(e[i].w > we[u])
{
if(dp[u]+1>dp[v])
{
we[v]=e[i].w;
dp[v]=dp[u]+1;
}
if(dp[u]+1 == dp[v])
we[v]=min(we[v],e[i].w);
}
//if(e[i].w == we[u])
mmax=max(mmax,dp[v]);
mmax=max(mmax,dp[u]);
}
printf("%d\n",mmax);
}
return 0;
}