Zq's Blog spfa,图论,差分约束,算法 [差分约束]bzoj2330: [SCOI2011]糖果

[差分约束]bzoj2330: [SCOI2011]糖果

题目描述

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

输入

输入的第一行是两个整数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个小朋友分到的糖果;

输出

输出一行,表示lxhgww老师至少需要准备的糖果数,如果不能满足小朋友们的所有要求,就输出-1。

样例输入

5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1

样例输出

11

提示

对于30%的数据,保证 N<=100

对于100%的数据,保证 N<=100000

对于所有的数据,保证 K<=100000,1<=X<=5,1<=A, B<=N

来源

Day1

题解

裸的差分约束;

设$S[i]$为第$i$个小朋友分到的糖果数;

对关系逐个分析,有

$X=1,S[A]=S[B]\to 0\le S[A]-S[B]\le0$

$X=2,S[A]<S[B]\to S[A]-S[B]\le1$

$X=3,S[A]\ge S[B]\to S[A]-S[B]\ge0$

$X=4,S[A]>S[B]\to S[A]-S[B]\ge1$

$X=5,S[A]\le S[B]\to S[A]-S[B]\le 0$

按自己的方式刷一趟差分约束即可,不要忘了判环;

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
inline int read(){
    int Res=0,f=1;char ch=getchar();
    while (ch>'9'||ch<'0') f=(ch=='-'?-f:f),ch=getchar();
    while (ch>='0'&&ch<='9') Res=Res*10+ch-'0',ch=getchar();
    return Res*f;
}
int N,M,tot,lnk[100005],son[300005],nxt[300005],w[300006];
ll dis[100005],Min;
bool vis[100005],boo[100005],use;
void add(int x,int y,int z){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;w[tot]=z;}
queue<int>Que;
void spfa(int x){
    if (vis[x]) return (void)(use=1);
    vis[x]=boo[x]=1;
    for (int i=lnk[x];i;i=nxt[i]){
        if (dis[son[i]]>dis[x]+w[i]){
            dis[son[i]]=dis[x]+w[i];
            spfa(son[i]);
            if (use) return (void)(vis[x]=0);
        }
    }
    vis[x]=0;
}
void spfa(){
    memset(dis,63,sizeof dis);
    Que.push(0);vis[0]=1;dis[0]=0;
    while (Que.size()){
        int Now=Que.front();Que.pop();vis[Now]=0;
        for (int i=lnk[Now];i;i=nxt[i]){
            if (dis[son[i]]>dis[Now]+w[i]){
                dis[son[i]]=dis[Now]+w[i];
                if (!vis[son[i]]){
                    vis[son[i]]=1;Que.push(son[i]);
                    if (dis[Que.front()]>dis[Que.back()]) swap(Que.front(),Que.back());
                }
            }
        }
    }
}
int main()
{
    N=read();M=read();
    for (int i=1;i<=M;i++){
        int X=read(),A=read(),B=read();
        switch (X){
            case 1:add(B,A,0);add(A,B,0);break;
            case 2:add(A,B,-1);break;
            case 3:add(B,A,0);break;
            case 4:add(B,A,-1);break;
            case 5:add(A,B,0);break;
        }
    }
    for (int i=1;i<=N;i++){add(0,i,-1);if (!boo[i]) spfa(i);if (use) return puts("-1"),0;}
    memset(vis,0,sizeof vis);
    spfa();
    for (int i=1;i<=N;i++) Min+=dis[i];
    printf("%lld\n",-Min);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注