首页 > 代码库 > BZOJ 2330: [SCOI2011]糖果 [差分约束系统] 【学习笔记】

BZOJ 2330: [SCOI2011]糖果 [差分约束系统] 【学习笔记】

2330: [SCOI2011]糖果

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 5395  Solved: 1750
[Submit][Status][Discuss]

Description

幼儿园里有N个小朋友,lxhgww老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心,总是会提出一些要求,比如小明不希望小红分到的糖果比他的多,于是在分配糖果的时候,lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的,lxhgww想知道他至少需要准备多少个糖果,才能使得每个小朋友都能够分到糖果,并且满足小朋友们所有的要求。

Input

输入的第一行是两个整数NK

接下来K行,表示这些点需要满足的关系,每行3个数字,XAB

如果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]糖果 [差分约束系统] 【学习笔记】