luogu1073最优贸易 做题笔记

题面传送门

一眼看过去

能往回走，各种图论算法肯定是不能直接用的，但是既然能回到自己，那就是说连通块里的每个点先后顺序随便，所以tarjan缩点搞一搞+DAG图dp

然后中间脑抽，啊，DAG图不就是一棵树吗，所以搞个dfs，记录一下爸爸，线性dp！

果然是太久没写dag图dp了……DAG图是一棵有向树，性质和树不完全相同，不能这么搞的

所以正解应该是tarjan缩点+top排序+树形dp

/*
作者：wyf
日期：2019/11/12
OJ：luogu
题目：1063
*/
#include<bits/stdc++.h>
#define maxn 4005010
#define ll long long
#define INF 2147483648
using namespace std;
int n,m;
struct edge
{
	int next,end;
}e[maxn],new_e[maxn];
int head[maxn];
int tot;
void add(int x,int y)
{
	e[++tot].next=head[x];
	e[tot].end=y;
	head[x]=tot;
}
int step=0;
int color=0;
int belong[maxn];
bool vis[maxn];
int stck[maxn];
int top;
int dfn[maxn],low[maxn];
void tarjan(int now)
{
	dfn[now]=++step;
	vis[now]=true;
	low[now]=step;
	stck[++top]=now;
	for (int i=head[now];i;i=e[i].next)
	{
		int to=e[i].end;
		if (!dfn[to])
			tarjan(to),low[now]=min(low[to],low[now]);
		else if (!belong[to])
			low[now]=min(low[now],dfn[to]);
	}
	if (low[now]==dfn[now])
	{
		belong[now]=++color;
		while(stck[top]!=now)
		{
			belong[stck[top]]=color;
			top--;
		}
		top--;
	}
}
int new_head[maxn];
int new_tot;
void new_add(int x,int y)
{
	new_e[++tot].next=new_head[x];
	new_e[tot].end=y;
	new_head[x]=tot;
}
int rd[maxn];
int l,r;
int q[maxn];
void tp_sort()
{
	r=0;
    l=r;
    for(int i=1;i<=color;i++)
        if(!rd[i])
            q[++r]=i;
    while(l<r)
    {
        int x=q[++l];
        for(int i=new_head[x];i;i=new_e[i].next)
        {
            int y=new_e[i].end;
            rd[y]--;
            if(!rd[y])
                q[++r]=y;
        }
    }
//    for (int i=1;i<=color;i++)
// 	cout<<q[i]<<' ';
}
int ed;
int xiao[maxn];
int fa[maxn];
int minn[maxn],maxx[maxn];
int f[maxn];
void dp()
{
	for (int i=1;i<=color;i++)
	{
	//	cout<<q[i]<<' '<<xiao[q[i]]<<"    ";
		for (int j=new_head[q[i]];j;j=new_e[j].next)
		{
			int to=new_e[j].end;
		//	cout<<to<<" ";
			xiao[to]=min(min(xiao[to],xiao[q[i]]),minn[to]);
			f[to]=max(max(f[to],f[q[i]]),maxx[to]-xiao[to]);
		}
	//	cout<<endl;
	}
//	for (int i=1;i<=color;i++)
//		cout<<xiao[q[i]]<<' '<<maxx[q[i]]<<' '<<f[q[i]]<<endl;
}
int a[maxn];
queue<int> qq;
/*void dfss(int now)
{
	if (now==belong[1])
	{
		cout<<"ha";
		while(!qq.empty())
		{
			cout<<qq.front()<<' ';
			qq.pop();
		}
		return;
	}
	for (int i=new_head[now];i;i=new_e[i].next)
	{
		qq.push(i);
		dfss(new_e[i].end);
		qq.pop();
	}
}*/
int main()
{
	//freopen("ha.in","r",stdin);
	//freopen("ha.out","w",stdout); 
	
	cin>>n>>m;
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int cnt=m;
	for (int i=1;i<=m;i++)
	{
		int ha,hb,k;
		scanf("%d%d%d",&ha,&hb,&k);
		if (k==2)
			add(ha,hb),add(hb,ha),cnt++;
		else
			add(ha,hb);
	}
	for (int i=1;i<=n;i++)
		if (!belong[i])
			tarjan(i);
/*	for (int i=1;i<=n;i++)
		cout<<belong[i]<<' ';
	cout<<endl;*/
	memset(minn,0x3f3f3f,sizeof(minn));
	memset(xiao,0x3f3f3f,sizeof(xiao));
	for (int i=1;i<=n;i++)
	{
		maxx[belong[i]]=max(maxx[belong[i]],a[i]);
		minn[belong[i]]=min(minn[belong[i]],a[i]); 
	//	cout<<belong[i]<<' '<<maxx[belong[i]]<<' '<<minn[belong[i]]<<endl;
	}
	xiao[belong[1]]=minn[belong[1]];
	//cout<<endl;
	for (int i=1;i<=n;i++)
	{
		for (int j=head[i];j;j=e[j].next)
		{
			if (belong[i]!=belong[e[j].end])
				new_add(belong[i],belong[e[j].end]),rd[belong[e[j].end]]++;
		}
	}
	ed=belong[n];
	tp_sort();
//	for (int i=1;i<=color;i++)
//		for (int j=new_head[i];j;j=new_e[j].next)
//			cout<<i<<' '<<new_e[j].end<<endl;	
//	cout<<endl;
//	for (int i=1;i<=n;i++)
//		cout<<belong[i]<<' ';
//	cout<<endl; 

//	cout<<'?'<<ed<<endl;
//	cout<<endl;
	dp();	
	cout<<f[ed];
 	return 0;
}

谨以此纪念我令人窒息的鬼畜操作

（碎碎念，很久没有自己想出一道蓝题的正解然后调出来了呢，果然是，对ac上瘾啊）

以上，退役前的碎碎念，感谢

不要留遗憾啊