【差分约束系统】【最短路】【spfa】CDOJ1646 穷且益坚， 不坠青云之志。

求一个有n个元素的数列，满足任意连续p个数的和不小于s， 任意连续q个数的和不大于t。

令sum[i]表示前i项的和(0<=i<=n,sum[0]=0) 那么题目的条件可转化为： sum[i]-sum[i-p]>=s (p<=i<=n) sum[i]-sum[i-q]<=t (q<=i<=n) 将第一个不等式取反，得到 sum[i-p]-sum[i]<=-s(p<=i<=n)

于是问题转化为求一系列不等式的解，这是一个典型的差分约束问题。 考虑最短路径的性质，令dis[i]表示从s到i的最短路，则对于图中存在的一条边(u,v),有 dis[v]<=dis[u]+w(u,v),即dis[v]-dis[u]<=w(u,v); 类比不等式，于是可建图，i向i-p引长度为-s的边，i-q向i引长度为t的边。 然后运行bellmanford，如果存在负环，则无解， 否则所得到的最短路的值就是sum[i]的一个解。 时间复杂度：O(VE) 具体原理及证明见《算法导论》P387

注意这里只需要求出可行解，故而建立一个虚拟结点的方法是可行的。

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

int n,p,q,K1,K2;

queue<int>Q;

bool inq[510];

int dis[510],sumv[510];

int v[510*3],__next[510*3],e,w[510*3],first[510],cnts[510];

void AddEdge(int U,int V,int W){

	v[++e]=V;

	w[e]=W;

	__next[e]=first[U];

	first[U]=e;

}

bool spfa(const int &s)

{

	memset(dis,0x7f,sizeof(dis));

    dis[s]=0; Q.push(s); inq[s]=1; ++cnts[s];

    while(!Q.empty())

      {

        int U=Q.front();

        for(int i=first[U];i;i=__next[i])

          if(dis[v[i]]>dis[U]+w[i])

            {

              dis[v[i]]=dis[U]+w[i];

              if(!inq[v[i]])

                {

                  Q.push(v[i]);

                  inq[v[i]]=1;

                  ++cnts[v[i]];

                  if(cnts[v[i]]>n+1)

                    return 0;

                }

            }

        Q.pop(); inq[U]=0;

      }

    return 1;

}

int main(){

	scanf("%d%d%d%d%d",&n,&p,&q,&K1,&K2);

	for(int i=0;i+p<=n;++i){

		AddEdge(p+i,i,-K1);

	}

	for(int i=0;i+q<=n;++i){

		AddEdge(i,q+i,K2);

	}

	for(int i=0;i<=n;++i){

		AddEdge(n+1,i,0);

	}

	if(!spfa(n+1)){

		puts("No");

		return 0;

	}

	puts("Yes");

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

		sumv[i]=dis[i]-dis[0];

	}

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

		printf("%d ",sumv[i]-sumv[i-1]);

	}

	printf("%d\n",sumv[n]-sumv[n-1]);

	return 0;

}