【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;
}
