EOJ 3263 丽娃河的狼人传说

差分约束系统，$spfa$。

首先判断无解，若某个约束的$t$大于区间长度，则一定无解。

否则一定有解，可以得到一系列的不等式：

最终区间和大于等于目前的区间和：$S[R]-S[L-1]≥val$，

每一个位置的值小于等于$1$：$S[R]-S[R-1]≤1$，

每一个约束条件：$S[R]-S[L-1]≥t$，

最终是要求$S[n]-S[0]$最小是多少，扔进差分约束系统，跑$S[0]$到$S[n]$的最长路即可。

#include <cstdio>

#include <cmath>

#include <set>

#include <cstring>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

int T;

int n,m,k;

int dis[2000],f[2000];

int h[2200000];

int to[2200000];

int val[2200000];

int nx[2200000];

int sz;

int a[2000];

int cas=1;

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

{

	to[sz] = b;

	val[sz] = c;

	nx[sz] = h[a];

	h[a] = sz++;

}

void spfa()

{

	for(int i=0;i<=n;i++) dis[i] = -n-1, f[i] = 0;

	queue<int>Q;

	Q.push(0); f[0] = 1; dis[0] =0;

	while(!Q.empty())

	{

		int x =Q.front(); Q.pop(); f[x]=0;

		for(int i=h[x];i!=-1;i = nx[i])

		{

			int y = to[i], cost = val[i];

			if(dis[x] + cost > dis[y])

			{

				dis[y] = dis[x] + cost;

				if(f[y]==0)

				{

					f[y] = 1;

					Q.push(y);

				}

			}

		}

	}

}

int main()

{

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d%d%d",&n,&m,&k);

		for(int i=0;i<=n;i++) h[i]=-1, a[i] = 0;

		sz=0;

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

		{

			int x; scanf("%d",&x); a[x]=1;

		}

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

		{

			a[i] = a[i]+a[i-1];

			add(i,i-1,-1);

		}

		bool fail=0;

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

		{

			int L,R,t; scanf("%d%d%d",&L,&R,&t);

			add(L-1,R,t);

			if(R-L+1<t) fail=1;

		}

		if(fail)

		{

			printf("Case %d: %d\n",cas,-1);

			cas++;

		}

		else

		{

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

			{

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

				{

					add(i-1,j,a[j] - a[i-1]);

				}

			}

			spfa();

			printf("Case %d: %d\n",cas,dis[n] - a[n]);

			cas++;

		}

	}

	return 0;

}