首页 > 代码库 > BZOJ 2330: [SCOI2011]糖果 [差分约束系统] 【学习笔记】
BZOJ 2330: [SCOI2011]糖果 [差分约束系统] 【学习笔记】
2330: [SCOI2011]糖果
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 5395 Solved: 1750
[Submit][Status][Discuss]
Description
幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的，lxhgww想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。
Input
输入的第一行是两个整数N，K。
接下来K行，表示这些点需要满足的关系，每行3个数字，X，A，B。
如果X=1， 表示第A个小朋友分到的糖果必须和第B个小朋友分到的糖果一样多；
如果X=2， 表示第A个小朋友分到的糖果必须少于第B个小朋友分到的糖果；
如果X=3， 表示第A个小朋友分到的糖果必须不少于第B个小朋友分到的糖果；
如果X=4， 表示第A个小朋友分到的糖果必须多于第B个小朋友分到的糖果；
如果X=5， 表示第A个小朋友分到的糖果必须不多于第B个小朋友分到的糖果；
Output
输出一行，表示lxhgww老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出-1。
【数据范围】
对于30%的数据，保证 N<=100
对于100%的数据，保证 N<=100000
对于所有的数据，保证 K<=100000，1<=X<=5，1<=A, B<=N
Source
Day1
以下自己的理解
一组类似最短路中的三角不等式的线性规划问题，用最短路算法求解
a-b<=c ----> d[v]<=d[u]+c
目标函数 最短路啊你说目标函数是什么
然而我就这样做了之后，一直不过样例！
突然发现，他们都跑了最长路
原来：
差分约束系统中，求每个变量的最大值（这个最值是相对的，差分约束系统当其中一个变量的值确定其他的也会有确定的范围，比如d[s]确定）
就是用最短路 按照<=建图
求最小值的话就是最长路了，按>=建图
更形式化的：
①：对于差分不等式，a - b <= c ，建一条 b 到 a 的权值为 c 的边，求的是最短路，得到的是最大值
②：对于不等式 a - b >= c ，建一条 b 到 a 的权值为 c 的边，求的是最长路，得到的是最小值
③：存在负环的话是无解
④：求不出最短路（dist[ ]没有得到更新）的话是任意解
为什么最短路反而是最小值呢？
回忆算法导论504页把最短路转换成线性规划形式时，d[t]是最大化的，因为这个线性规划求的是满足那些不等式的最大的d[t]，因为这个问题有实际意义 如果最小的话 d[t]取-INF就好了，显然这样是错误的
在网上看到另一个想法：“求最短路是由无穷向下约束而得到的，所以得到的一定是最大值”
还有一个实现上的问题：
有必要加一个超级源来避免不连通吗？
没有，记得算法导论上有个思考题吗。和负环一样，把所有点加入队列d[i]=0就可以了
对于本题来说，因为至少一个糖果，所以d[i]=1
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;typedef long long ll;const int N=1e5+5,M=1e5+5,INF=1e9;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,m,x,a,b,s;struct edge{ int v,ne; double w;}e[M<<1];int h[N],cnt=0;inline void ins(int u,int v,int w){ cnt++; e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;}int q[N],head,tail,inq[N],num[N],d[N];inline void lop(int &x){if(x==N) x=1;}bool spfa(int s){ for(int i=1;i<=n;i++) d[i]=-INF; head=tail=0; memset(inq,0,sizeof(inq)); memset(num,0,sizeof(num)); for(int i=1;i<=n;i++) q[tail++]=i,inq[i]=1,d[i]=1; while(head!=tail){ int u=q[head++];inq[u]=0;lop(head); for(int i=h[u];i;i=e[i].ne){ int v=e[i].v,w=e[i].w; if(d[v]<d[u]+w){ d[v]=d[u]+w; if(!inq[v]){ inq[v]=1,q[tail++]=v,lop(tail); if(++num[v]>n) return true; } } } } return false;}int main(){ n=read();m=read();s=0; for(int i=1;i<=m;i++){ x=read();a=read();b=read(); if(x==1) ins(a,b,0),ins(b,a,0); else if(x==2){if(a==b){puts("-1");return 0;} ins(a,b,1);} else if(x==3) ins(b,a,0); else if(x==4){if(a==b){puts("-1");return 0;} ins(b,a,1);} else ins(a,b,0); } if(spfa(s)) puts("-1"); else{ ll ans=0; for(int i=1;i<=n;i++) ans+=d[i]; printf("%lld",ans); } }
BZOJ 2330: [SCOI2011]糖果 [差分约束系统] 【学习笔记】