- 有(n)个数，存在两种限制，形如(a_x=a_y-1)或(a_xle a_y)。
- 求最多可能有多少种不同的数。
- (nle600)，限制总数(le10^5)
差分约束
根据限制的类型容易想到差分约束。
对于第一种限制，可以拆成(a_x-a_yle-1)且(a_y-a_xle1)。
对于第二种限制，可以写成(a_x-a_yle0)。
于是就建立了差分约束模型，但仅仅这样并不能解决这道题。
强连通分量
考虑对于当前图中的每一个强连通分量，其中的数的种数就是其中点两两最短路的最大值(+1)。
而对于不同的强连通分量，因为我们的限制只有一个边界，完全可以让它们相差很多，就能保证值域不交。
因此答案就是每个强连通分量答案之和。
代码：(O(n^3+m))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 600
#define M 100000
#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
using namespace std;
int n,m1,m2,ee,lnk[N+5],f[N+5][N+5],g[N+5];struct edge {int to,nxt;}e[2*M+5];
int d,dfn[N+5],low[N+5],T,S[N+5],IS[N+5],ct,bl[N+5];I void Tarjan(CI x)//Tarjan缩点
{
dfn[x]=low[x]=++d,IS[S[++T]=x]=1;for(RI i=lnk[x];i;i=e[i].nxt)
dfn[e[i].to]?IS[e[i].to]&&(low[x]=min(low[x],dfn[e[i].to])):(Tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]));
if(low[x]==dfn[x]) {++ct;W(bl[S[T]]=ct,IS[S[T]]=0,S[T--]^x);}
}
int main()
{
RI i,j,x,y;for(scanf("%d%d%d",&n,&m1,&m2),i=1;i<=n;++i) for(j=1;j<=n;++j) f[i][j]=i^j?1e9:0;
for(i=1;i<=m1;++i) scanf("%d%d",&x,&y),add(x,y),add(y,x),f[x][y]=min(f[x][y],-1),f[y][x]=min(f[y][x],1);//a[x]-a[y]≤-1,a[y]-a[x]≤1
for(i=1;i<=m2;++i) scanf("%d%d",&x,&y),add(x,y),f[x][y]=min(f[x][y],0);//a[x]-a[y]≤0
for(RI k=1;k<=n;++k) for(i=1;i<=n;++i) for(j=1;j<=n;++j) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);//Floyd最短路
for(i=1;i<=n;++i) if(f[i][i]) return puts("NIE"),0;for(i=1;i<=n;++i) !dfn[i]&&(Tarjan(i),0);//判无解，否则求强连通分量
for(i=1;i<=n;++i) for(j=1;j<=n;++j) bl[i]==bl[j]&&(g[bl[i]]=max(g[bl[i]],f[i][j]));//求出同一强连通分量内两点最短路最大值
RI t=0;for(i=1;i<=ct;++i) t+=g[i]+1;return printf("%d
",t),0;//答案是所有强连通分量答案之和
}