差分约束系统。
有n只牛，每只牛i对应x轴上一点di，对于i < j，有di <= dj。存在ml个关系di >= dj – k，其中i < j；又存在md个关系di <= dj - k，其中i < j。要求d[n] - d[1]最大值。若关系无法满足，输出-1；若最大值为无穷，输出-2。 由于题目所求的是限制约束下的最大值，也即需要取大于等于号建立差分约束系统，那么3种边分别有： dj >= di
di + k >= dj
dj – k >= di
初始化除d1外的di值为无穷大，便可以用SPFA求解了。每次当 di + k < dj 时，进行松弛 dj = di + k。 但是……用栈跑SPFA时却无限WA。换成队列一下就AC了。找到了原始数据后又看了别人的程序，最后发现问题出在了判负环上。 基于队列的SPFA是用入栈次数>n来判断是否存在负环的，而姜碧野的《SPFA算法的优化与应用》中深搜的SPFA通过节点是否在栈中判负环是针对递归实现的。而我写的是基于栈的非递归SPFA，用的还是根据入栈次数>n判负环，但却发现很易出现误判。猜测由于深搜SPFA可以说是“盲目”推进的，也即有可能过多地沿回边更新，而导致入栈次数超过n，但实际却不存在负环。例如下图的例子：
最后的解是d[1..5] = {0, 4, 6, 10, 3}，其中结点5的入栈次数高达8次，但仍是无负环的。
在这题中，如果改变邻接表中边的顺序，让深搜SPFA尽量往图的深处推进，就能使用入栈次数来正确地判断负环了。可惜没有找到通用的严格证明……
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include<cstdio> #include<cstring> int n,ml,md,hd[1001],el,d[1001],b[1001],c[1001]; int stk[1000],sl; struct E { int v,d,p; }e[100000]; inline void adde(int u,int v,int d) { e[el].v=v; e[el].d=d; e[el].p=hd[u]; hd[u]=el++; } void init() { int i,j,k,l; el=0; sl=0; memset(hd,-1,sizeof hd); memset(b,0,sizeof b); memset(c,0,sizeof c); for(i=1;i<=n;i++) d[i]=0x7fffffff; while(ml--) { scanf("%d%d%d",&i,&j,&k); adde(i,j,k); } while(md--) { scanf("%d%d%d",&i,&j,&k); adde(j,i,-k); } for(i=2;i<=n;i++) adde(i,i-1,0); } int solve() { int i,j,k,l; b[1]=1; d[1]=0; stk[sl++]=1; while(sl) { i=stk[--sl]; b[i]=0; for(l=hd[i];l!=-1;l=e[l].p) { j=e[l].v; k=e[l].d; if(d[i]+k<d[j]) { d[j]=d[i]+k; if(!b[j]) { if(++c[j]>n) return -1; b[j]=1; stk[sl++]=j; } } } } if(d[n]==0x7fffffff) return -2; return d[n]-d[1]; } int main() { int i,j; while(~scanf("%d%d%d",&n,&ml,&md)) { init(); printf("%d\n",solve()); } return 0; } |
结论就是：下次还是老老实实用队列判负环吧……