自动搬运

查看原文

来自洛谷，原作者为

	chzhh_111 退是死，前是生||坐标：FJ，现初三，已学 OI 两年||比赛等级分上不了2000，不改签

搬运于2025-08-24 23:02:41，当前版本为作者最后更新于2024-08-26 09:08:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识：差分约束 $+$ 强连通 Tarjan $+$ 拓扑 DP。

差分约束：

注意到，题目中所给出不等关系的约束都可以用 $x \ge y$ 以及 $x > y$ 来表示，同时 $x \ge y$ 和 $x > y$ 又可以用 $x \ge y + z$ 来表示，也就是：

• $x \ge y$ 转化为 $x \ge y + 0$
• $x > y$ 转化为 $x \ge y + 1$

所以都可以用这一关系来建图，$x \ge y + z$ 就是 $y$ 向 $x$ 连一条边，而边权就是 $z$。

强连通 Tarjan：

我们可以发现，当两个点在一个强连通图当中必然有这两个点的亮度相同，因为根据上述所说的建图方法能够得出来这个不小于是有传递性的，所以一条路的终点一定大于等于这一条路的起点，则成立。

因此就可以用 Tarjan 将所有的强连通预处理出来，这样子就可以把这个图变成了 DAG。

同时也可以发现，如果是这样的话，单个强连通里面的每一条边的边全都应该是 $0$。所以 $-1$ 的情况，就是如果发现在单个强连通里面有出现过一条边的边权是 $1$ 的情况。

在强连通的时候，预处理下每个强连通里面的节点数量，以后要用。

拓扑 DP：

题目中的亮度现在可以转化成从这个 DAG 的任意一点出发，所得到的最长路径的权值和是多少，发现可以用拓扑 DP 求解。

设 $dp_{i}$ 表示，从点 $i$ 的前驱转移到点 $i$ 的最长路径是多少，则动态转移方程就是：$dp_{i}= \max (dp_{j}+dis)$ 其中 $j$ 是 $i$ 的前驱，$dis$ 是从 $j$ 走到 $i$ 的权值是多少。

初始化是假如点 $i$ 的入度为零，则 $dp_{i} = 1$。

计算答案：

$ans = \displaystyle \sum_{i=1}^{tot} sum_{i} \times dp_{i}$

$tot$ 是强连通的数量。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+1;
int n,m,a,b,t,ls,z[N],zz[N],dfn[N],low[N],stak[N],top,tot,col[N],Time,sum[N],ru[N],q[N];
int f[N],ans;
struct bian{
	int qi,zhong,quan,zhi;
}s[N],ss[N];
void Tarjan(int x)
{
	dfn[x]=low[x]=++Time;
	stak[++top]=x;
	for(int i=z[x];i;i=s[i].zhi)
	{
		int u=s[i].zhong;
		if(!dfn[u])
		{
			Tarjan(u);
			low[x]=min(low[x],low[u]);
		}
		  else if(!col[u]) low[x]=min(low[x],low[u]);
	}
	if(low[x]==dfn[x])
	{
		col[x]=++tot;
		sum[tot]++;
		while(stak[top]!=x) sum[tot]++,col[stak[top--]]=tot;
		top--;
	}
}
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&t,&a,&b);
		if(t==1) s[++ls]=(bian){a,b,0,z[a]},z[a]=ls,s[++ls]=(bian){b,a,0,z[b]},z[b]=ls;
		else if(t==2) s[++ls]=(bian){a,b,1,z[a]},z[a]=ls;
		else if(t==3) s[++ls]=(bian){b,a,0,z[b]},z[b]=ls;
		else if(t==4) s[++ls]=(bian){b,a,1,z[b]},z[b]=ls;
		else s[++ls]=(bian){a,b,0,z[a]},z[a]=ls;
	}
	for(int i=1;i<=n;i++)
	  if(!dfn[i]) Tarjan(i);
	int len=ls;
	ls=0;
	for(int i=1;i<=len;i++)
	{
		int x=col[s[i].qi],y=col[s[i].zhong];
		if(x!=y) ss[++ls]=(bian){x,y,s[i].quan,zz[x]},zz[x]=ls,ru[y]++;
		  else if(s[i].quan) {printf("-1");return 0;}
	}
	int l=0,r=0;
	for(int i=1;i<=tot;i++) if(!ru[i]) q[++r]=i,f[i]=1;
	while(l<r)
	{
		l++;
		ans+=f[q[l]]*sum[q[l]];
		for(int i=zz[q[l]];i;i=ss[i].zhi)
		{
			int x=ss[i].qi,y=ss[i].zhong;
			if(f[y]<f[x]+ss[i].quan) f[y]=f[x]+ss[i].quan;
			if(!(--ru[y])) q[++r]=y;
		}
	}
	printf("%lld",ans);
	return 0;
}