CF459E Pashmak and Graph (Dag dp)

解题思路

　　\(dag\)上\(dp\)，首先要按照边权排序，然后图都不用建直接\(dp\)就行了。注意边权相等的要一起处理，具体来讲就是要开一个辅助数组\(g[i]\)，来避免同层转移。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

using namespace std;

const int MAXN = 300005;

inline int rd(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}

	while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

	return f?x:-x;

}

int n,m,f[MAXN],g[MAXN],stk[MAXN],top,ans;

bool vis[MAXN];

struct Edge{

	int u,v,w;

	friend bool operator<(const Edge A,const Edge B){

		return A.w<B.w;

	}

}edge[MAXN];

int main(){

	n=rd(),m=rd();

	for(int i=1;i<=m;i++)

		edge[i].u=rd(),edge[i].v=rd(),edge[i].w=rd();

	sort(edge+1,edge+1+m);

	for(int i=1;i<=m;i++){

		int x=edge[i].u,y=edge[i].v;

		if(edge[i].w==edge[i-1].w) {

			g[y]=max(g[y],f[x]+1);

			if(!vis[y]) {vis[y]=1;stk[++top]=y;}

		}

		else {

			while(top) {

				vis[stk[top]]=0;

				f[stk[top]]=g[stk[top]];

				top--;

			}

			g[y]=max(g[y],f[x]+1);

			vis[y]=1;stk[++top]=y;

		}

	}

	while(top) {

		vis[stk[top]]=0;

		f[stk[top]]=g[stk[top]];

		top--;

	}

	for(int i=1;i<=n;i++) ans=max(ans,f[i]);

	printf("%d\n",ans);

	return 0;

}

巴特西

CF459E Pashmak and Graph (Dag dp)

解题思路

代码

最新文章

热门文章