「bzoj2788」「Poi2012」Festival节日 - 差分约束系统

题目大意

    有$n$个数，给出$m$个形如$x_a+1=x_b$，$x_c\le x_d$的限制条件，求$x$不同取值个数的最大值。

---

题目分析

根据题目的限制，我们可以使用差分约束构造出图。
图中若存在负环无解。
若存在正/零环，统计其内部的最短路径最大值，将每个强连通分量的最短路径最大值相加即可。

证明：

• 对于不同块，它们不相互影响，因为我们总是能构造出一组解使得其满足限制并块之间的取值不同，因此我们可以将每个块的答案相加。
• 对于相同块，其个数即为块内权值的极差，也就是任意两点最短路径的最大值。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=605;

int n,m1,m2,step=0,top=0,Dfn[maxn],Lowlink[maxn],Stack[maxn],Instack[maxn],map[maxn][maxn],ans=0;
vector<int>edges[maxn],circle;

void AddEdge(int x,int y) {
	edges[x].push_back(y);
}

void Cal() {
	int sum=0;
	for(int x:circle)
		for(int y:circle)
			sum=max(sum,map[x][y]);
	ans+=sum+1;
}

void Tarjan(int Now) {
	Dfn[Now]=Lowlink[Now]=++step;
	Stack[++top]=Now;
	Instack[Now]=1;
	for(int Next:edges[Now]) {
		if(!Dfn[Next]) {
			Tarjan(Next);
			Lowlink[Now]=min(Lowlink[Now],Lowlink[Next]);
		} else if(Instack[Next])Lowlink[Now]=min(Lowlink[Now],Dfn[Next]);
	}
	if(Dfn[Now]==Lowlink[Now]) {
		circle.clear();
		int y;
		do {
			y=Stack[top--];
			Instack[y]=0;
			circle.push_back(y);
		} while(y!=Now);
		Cal();
	}
}

int main() {
	n=Get_Int();
	m1=Get_Int();
	m2=Get_Int();
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			map[i][j]=i==j?0:INT_MAX/2;
	for(int i=1; i<=m1; i++) {
		int x=Get_Int(),y=Get_Int();
		AddEdge(x,y);
		AddEdge(y,x);
		map[x][y]=min(map[x][y],1);
		map[y][x]=min(map[y][x],-1);
	}
	for(int i=1; i<=m2; i++) {
		int x=Get_Int(),y=Get_Int();
		AddEdge(y,x);
		map[y][x]=min(map[y][x],0);
	}
	for(int k=1; k<=n; k++)
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
	for(int i=1; i<n; i++)
		if(map[i][i]<0) {
			puts("NIE");
			return 0;
		}
	for(int i=1; i<=n; i++)
		if(!Dfn[i])Tarjan(i);
	printf("%d\n",ans);
	return 0;
}