【差分约束】 杭电多校4-1003（HDU7176）Magic

上链接：Problem - 7176

蒟蒻补题难得发现能补的上的题。。

        给定n个魔法塔和一个作用半径k，所有魔法塔的初始魔法值为0，同时给定每个魔法塔的目标魔法值，需完成若干次操作使得每个魔法塔的魔法值大于等于目标魔法值。一次操作选择一个魔法塔注入1点魔法成分，以该魔法塔为中心的作用半径内的所有塔的魔法值加1(若半径k=1，选定魔法塔2，则塔1、2、3的魔法值加一)，同时给定q组约束条件，每组约束条件中给定一个区间[L,R]和区间和B，要求该区间内的魔法塔的魔法成分不得大于B。求最少操作次数，若无法实现则输出-1

（Tips:需注意魔法值与魔法成分的区别。）

        简言之：约束若干个区间内的操作次数，每次操作收益总数为以操作目标为中心的2*k-1个操作点，求给定收益目标下的最小操作次数。

        分析一个样例

        5 2 

        2 2 0 10 3

        1

        2 3 0

        结果为12：约束条件要求不能在区间[2,3]上进行操作，则可在点1进行两次操作，由于k=2，则点1、2的收益达到目标，随后在点4或者点5上进行10次操作，使得点4达到收益目标10，总共产生操作次数为12，且无法找到更小的可能操作次数。

        由于q组约束是对于某个区间内操作次数的限制，且目标收益给定了每个点的半径k范围内的最小操作总数和，且有操作数大于等于0等信息，能够罗列出若干不等式，故可考虑进行差分约束模型的建立。

        那么以什么作为建图的节点呢？

        考虑到我们所求的值为区间[1,n]的总操作数，且给出的约束条件都与区间操作数有关。故可设s为对于所有操作点的操作数的前缀和数组的元素。有前缀和数组才能更便捷地表示出区间操作数。

        则有三个约束条件：1.操作数大于等于0  2.区间i操作总数小于等于Bi 3.某点i的半径内的操作总数大于等于pi。

        故可写出差分约束不等式：

 其中Ui表示以i为中心的半径内的操作总数

        化简至标准形式：

        根据差分约束模型，形如v-u<=p的式子可视作从u到v的有向边，边权为p，最后所求值为s[n]-s[0]的可能最小值M，即为区间[1,n]的总操作数，而考虑到节点0本没有实际含义，且s[n]-s[0]满足式子s[n]-s[0]>=M,化为标准形式则为s[0]-s[n]<=-M，显而易见需要求以n为起点到节点0的最小路径，该值的相反数则为所求答案。

        而什么时候不会出现答案呢？即所给定的约束条件无法正确的约束出所需要的最短路径，换言之有负环存在，使得能够无止尽的进行松弛，约束条件失去其有效性。故可用SPFA在求以节点n为源点的单源最短路径的同时记录每个节点被访问的次数，若次数超过n+1（考虑到虚节点0）,则可判定产生负环，约束条件无效，无正确答案产生。

        采用前向星存图，忘了初始化head数组和cnt值导致一遍遍莫名其妙的WA。

        读入每个节点的目标能量值

        （1）min(i+k-1,n)至max(0,i-k)，权值为-Pi

        （2）i至i-1，权值为0 

        （3）L-1至R，权值为B。

        最老套的SPFA判负环模板就可以了，运行时间约为700ms,标程采用了手写双端队列，运行时间约为300ms

        若产生负环，则直接输出-1，若没有负环产生，则输出dis[0]的相反数即可，即为s[n]-s[0]，差分一下就是区间[1,n]的最小操作数。

#include
using namespace std;
typedef long long ll;
const int N=100005;
struct Edge
{
	int to,next,w;
} edge[6*N]; //开大不超就行，考虑到边多
int cnt,head[N],neg[N],inq[N];
int n,k,tmp,q,L,R,B;
void init() {
	cnt=0;
	for(int i=0;i<=n+3;i++) {
		head[i]=-1;
	}
}
ll dis[N];
void addedge(int u,int v,int w) {
	edge[cnt].w=w;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
	cnt++;
	return;
}
bool spfa(int s) {
	for(int i=0;i<=n;i++) {
		dis[i]=1e18;
		inq[i]=neg[i]=0;
	}
	inq[s]=1;
	neg[s]=1;
	dis[s]=0;
	queue q;
	q.push(s);
	while(!q.empty()) {
		int u=q.front();q.pop();inq[u]=0;
		for(int i=head[u];~i;i=edge[i].next) {
			int v=edge[i].to,w=edge[i].w;
			if(dis[u]+wn+1) return 0;
				}
			}
		}
	}
	return 1;
}
void solve() {
	scanf("%d%d",&n,&k);
	init();
	for(int i=1;i<=n;i++) {
		scanf("%d",&tmp);
		int u,v;  //u-v>=p  v-u<=-p
		u=min(n,i+k-1);
		v=max(0,i-k);
		addedge(u,v,-1*tmp);
		u=i;
		v=i-1;
		addedge(u,v,0);
	}
	scanf("%d",&q);
	while(q--) {
		scanf("%d%d%d",&L,&R,&B);
		addedge(L-1,R,B);
	}	
	if(spfa(n)) {
		printf("%lldn",-1*dis[0]);
	} else {
		printf("-1n");
	}
	return ;
}
int main() {
	//freopen("t.in","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--) {
		solve();
	}
}