【CCF-201809-4】再買菜（100） 差分限制spfa Apare_xzc

【CCF-201809-4】再買菜 差分限制

這題卡了2天了，也算是把差分限制複習了一遍，加深了解

題面

Sample Input

8
2 2 1 3 4 9 10 13
           

Sample Output

2 2 2 1 6 5 16 10
           

參考部落格：

https://blog.csdn.net/u014390156/article/details/82775736

推薦差分限制學習

夜深人靜寫算法(四)- 最短路和差分限制 - WhereIsHeroF…_CSDN部落格

差分限制算法總結

分析

spfa 求差的最小值：把不等式都轉化為>=的形式，建圖之後求最長路。
因為整除的性質，我們可以根據題意得到如下的一組不等式
(1). b[1]*2 <= a1+a2    <= b[1]*2+1
(2). b[2]*3 <= a1+a2+a3 <= b[2]*3+2
(3). b[3]*3 <= a2+a3+a4 <= b[3]*3+2
(4). b[4]*3 <= a3+a4+a5 <= b[4]*3+2
(5). b[5]*3 <= a4+a5+a6 <= b[5]*3+2
_._._
(i). b[i]*3   <= a[i-1]+a[i]+a[i+1] <= b[i]*3+2
._._. 
(n-1).b[n-1]*3 <= a[n-2]+a[n-1]+a[n] <= b[n-1]*3+2
(n)  .b[n]*2   <= a[n-1]+a[n]        <= b[n] * 2+2
____________________________________________________
根據差分限制的性質，我們要得到字典序最小的菜價序列，
那麼，我們要把不等式組轉化為Xi-Xj>=d的形式，然後建立
 j->i 長度為d的單向邊
____________________________________________________ 
由題意直接得出的式子都是ai+aj,我們需要引入一個輔助數
列：s[n] = a0+a1+a2+...+an (a0=0)
就是a[n]的字首和，則：
s0 = a0
s1 = a0+a1
s2 = a0+a1+a2 
s3 = a0+a1+a2+a3
s4 = a0+a1+a2+a3+a4
s5 = a0+a1+a2+a3+a4+a5
...
sn = a0+a1+a2+a3+a4+...+an 
那麼：
(1) a1+a2 = s2-s0
(2) a1+a2+a3 = s3-s0
(3) a2+a3+a4 = s4-s1
(4) a3+a4+a5 = s5-s2
......
(n-1) a[n-2]+a[n-1]+a[n] = s[n]-s[n-3]
(n)   a[n-1]+a[n] = s[n]-s[n-2]
______________________________________
--------------------------------------
是以，我們可以得到如下的式子：
(1)   b[1]*2 <= s2-s0 <= b[1]*2+1 
(2)   b[2]*3 <= s3-s0 <= b[2]*3+2
(3)   b[3]*3 <= s4-s1 <= b[3]*3+2
(4)   b[4]*3 <= s5-s2 <= b[4]*3+2
...
(i)   b[i]*3 <= s[i+1]-s[i-2] <= b[i]*3+2
...
(n-1) b[n-1]*3 <= s[n]-s[n-3] <= b[n-1]*3+2
(n)   b[n]*2   <= s[n]-s[n-2] <= b[n] * 2+1
---------------------------------------
_______________________________________
我們将上面n個式子轉化為Xi>=xj+d的形式：
s2 >= s0 + (2*b1)       ===> X0->X2 : 2*b1
s0 >= s2 + (-2*b1-1)    ===> X2->X0 : -2*b1-1
--------------------
s3 >= s0 + (3*b2)      
s0 >= s3 + (-3*b2-2)
s4 >= s1 + (3*b3)
s1 >= s4 + (-3*b3-2)
......
s[i+1] >= s[i-2] + (3*b[i])    ===> X[i-2]->X[i+1]: 3*bi
s[i-2] >= s[i+1] + (-3*b[i]-2) ===> X[i+1]->X[i-2]: -3*bi-2
......
s[n]   >= s[n-3] + (3*b[n-1])
s[n-3] >= s[n]   + (-3*b[n-1]-2)
--------------------
s[n]   >= s[n-2] + (b[n]*2)   ===> X[n-2]->X[n]   : bn*2
s[n-2] >= s[n]   + (-2*b[n]-1)===> X[n]  ->X[n-2] : -2*bn-1
___________________________________________________________
然後，我們發現還有一組限制條件，就是每天的菜價都是正整數
即為：a1>=1, a2>=1, a3>=1,... an>=1
可得：s1-s0>=1    ===> s1>=s0+1 ===> X[0]->X[1]:1
      s2-s1>=1
	  ...
	  s[i]-s[i-1]>=1 ===> si>=s[i-1]+1 ===>X[i]->X[i-1]:1
	  ...
	  sn-s[n-1]>=1 
PS: 由于求最長路，而且圖可能不連通，把dis[i]都初始化成0，然後都入隊
           

這個人的代碼很神奇，沒有節點全入隊,也100分，而我隻push(st)就隻有50分，之後再研究一下 <-

代碼

#include <bits/stdc++.h>
using namespace std;
const int maxn =315;
const int maxm = 6000+5;
const int INF = 0x3f3f3f3f;
int b[maxn];
struct Node{
	int to,Next,d;
}node[maxm];
int head[maxn],tot;

void initEdge()
{
	tot = 0;
	memset(head,-1,sizeof(head));
}
void addedge(int from,int to,int d)
{
//	printf("%d -> %d : %d\n",from,to,d);
	node[tot].d = d;
	node[tot].to = to;
	node[tot].Next = head[from];
	head[from] = tot++;
}
bool inQue[maxn]; //節點是否在隊列中 
int dis[maxn];    //源點到節點的最短距離 
int num[maxn];    //節點入隊的次數 
bool spfa(int n) //求最長路 
{
	int NN = sqrt(n);
	queue<int> Q;
//	for(int i=0;i<=n;++i)
//		inQue[i]=false,num[i]=0,dis[i]=0;
//	Q.push(st);
//	inQue[st] = true;
//	num[st]++;
//	dis[st] = 0;
	for(int i=0;i<=n;++i)
	{
		Q.push(i);
		inQue[i] = true;
		num[i] = 1;
		dis[i] = 0;
	}
	while(!Q.empty())
	{
		int u = Q.front();
		Q.pop();
		inQue[u] = false;
		for(int i=head[u];i!=-1;i=node[i].Next)
		{
			int v = node[i].to;
			int d = node[i].d;
			if(dis[u]+d>dis[v])
			{
				dis[v] = dis[u]+d;
				if(!inQue[v])
				{
					Q.push(v);
					inQue[v] = true;
					if(++num[i]>NN) return false;
				}
			}
		}
	}
	return true;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",b+i);
	initEdge();
	addedge(2,0,-2*b[1]-1);  
	addedge(0,2,2*b[1]);
	for(int i=2;i<=n-1;++i)
		addedge(i-2,i+1,3*b[i]),       
		addedge(i+1,i-2,-3*b[i]-2);   	
	addedge(n-2,n,2*b[n]);    
	addedge(n,n-2,-2*b[n]-1);
	for(int i=1;i<=n;++i)
		addedge(i-1,i,1);
	for(int i=1;i<=n;++i)
		addedge(0,i,i);
	bool ok = spfa(n);
//	cout<<(ok?"沒有負環":"有負環")<<endl;
	printf("%d",dis[1]); 
	for(int i=2;i<=n;++i)
		printf(" %d",dis[i]-dis[i-1]);
	printf("\n");

	return 0;
}