Description：

给定多组限制，限制分成 $2$ 类，第一类是 $ax+1=ay$ 第二类是 $ax\leqslant ay$ ，求这些数最多有多少种不同的取值。

$1\leqslant n \leqslant 600$

Solution：

对差分约束有了一些新的认识，这个题的模型一看就是一个差分约束，思考一下差分约束 $d[e[i].to]\leqslant d[k]+e[i].v$ 这个不等式，他表达的实际含义是 $e[i].to$ 最多能比 $k$ 大 $e[i].v$ 这个值，而如果存在一个负环，即某个数的最大取值还比自己小，那一定是不合理的，这也就是有负环差分约束系统不合法的原因。

按照原题给的方式建图，用 $\text{tarjan}$ 跑出所有的强连通分量，那么强连通分量之间一定都是边权为 $0$ 的有向边相连，由于缩完点的图是一个 $\text{DAG}$ ，所以各个联通块之间是互不影响的，贪心的想最终一定可以找出一种方案使得联通块之间不存在相同的取值，那么我们只要知道每个联通块内最多有多少不同取值即可。由上文所述差分约束边的含义，而且本题差分约束的边权都为 $1$ ，所以联通块内的最长的最短路就是这个联通块的答案，把所有累加起来就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<vector>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n,m1,m2;

#define MAXN 610

#define MAXM 200000

struct edge

{

	int to,nxt,v;

}e[MAXM];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

int dfn[MAXN],low[MAXN],tot = 0;

stack<int> s;

bool v[MAXN];

int ins[MAXN],scc = 0;

vector<int> p[MAXN];

void tarjan(int k)

{

	dfn[k] = low[k] = ++tot;

	s.push(k);v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!dfn[e[i].to])

		{

			tarjan(e[i].to);

			low[k] = min(low[k],low[e[i].to]);

		}

		else if(v[e[i].to])

		{

			low[k] = min(low[k],dfn[e[i].to]);

		}

	}

	if(low[k] == dfn[k])

	{

		int t;++scc;

		do

		{

			t = s.top();s.pop();

			v[t] = false;ins[t] = scc;

			p[scc].push_back(t);

		}while(t != k);

	}

	return;

}

int d[MAXN],vis[MAXN];

#define INF 0x3f3f3f3f

bool SPFA(int k)

{

	vis[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(ins[e[i].to] != ins[k])continue;

		if(d[e[i].to] > d[k] + e[i].v)

		{

			if(vis[e[i].to])return false;

			d[e[i].to] = d[k] + e[i].v;

			if(!SPFA(e[i].to))return false;

		}

	}

	vis[k] = false;

	return true;

}

int main()

{

	scanf("%d%d%d",&n,&m1,&m2);

	int a,b; 

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

	{

		a = read();b = read();

		add(a,b,1);add(b,a,-1);

	}

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

	{

		a = read();b = read();

		add(b,a,0);

	}

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

	{

		if(dfn[i] == 0)tarjan(i);

	}

	int ans = 0;

	for(int w = 1;w <= scc;++w)

	{

		int res = 0;

		for(vector<int>::iterator s = p[w].begin();s != p[w].end();++s)

		{

			for(vector<int>::iterator k = p[w].begin();k != p[w].end();++k)

				d[*k] = INF;

			d[*s] = 0;

			if(!SPFA(*s))

			{

				puts("NIE");

				return 0;

			}

			for(vector<int>::iterator k = p[w].begin();k != p[w].end();++k)

				res = max(res,d[*k]);

		}

		ans += res + 1;

	}

	cout << ans << endl;

	return 0;

}