洛谷 P3275 BZOJ 2330 [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。

輸入輸出樣例

輸入樣例#1：

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

輸出樣例#1：

11      

說明

【資料範圍】

對于30%的資料，保證 N<=100

對于100%的資料，保證 N<=100000

對于所有的資料，保證 K<=100000，1<=X<=5，1<=A, B<=N

解題思路

　　一道差分限制的裸題，不懂差分限制的看

這裡

，我就是看那篇博文看懂的差分限制，它被百度放到了第一個，實屬不易，少有的不謀财害命的事例啊。

　　這題要求的是最小值，那麼我們需要求出一堆$x_i-x_j>=c$的式子，然後求0點到其他點最長路之和，如果存在負環或自己不等于自己的，則輸出-1

　　順便從0連一條權值為1的邊到其他所有點，根據一些玄學的東西，要按n到1的順序連,否則某些成鍊的點跑不過去，然後跑spfa即可，我找負環、求最長路用的是dfs型的spfa，代碼短一些。

源代碼

#include<stdio.h>
int n,m;

struct edge{
    int next,to,w;
}e[1000010];
int head[500010]={0},cnt=1;
void add(int u,int v,int w)
{
    e[cnt]={head[u],v,w};
    head[u]=cnt++;
}

int dis[500010];
bool ins[500010]={0};
bool spfa(int u)
{
    ins[u]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to,w=e[i].w;
        if(dis[v]<dis[u]+w)
        {
            dis[v]=dis[u]+w;
            if(ins[v]||!spfa(v)) return false;
        }
    }
    ins[u]=0;
    return true;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,mode,u,v;i<=m;i++)
    {
        scanf("%d%d%d",&mode,&u,&v);
        if(mode==1)
            add(v,u,0),add(u,v,0);
        else if(mode==2)
        {
            if(u==v)
            {
                puts("-1");
                return 0;
            }
            add(u,v,1);
        }
        else if(mode==3)
        {
            add(v,u,0);
        }
        else if(mode==4)
        {
            if(u==v)
            {
                puts("-1");
                return 0;
            }
            add(v,u,1);
        }
        else
        {
            add(u,v,0);
        }
    }
    for(int i=n;i>=1;i--)
        add(0,i,1);
    for(int i=1;i<=n;i++)
        dis[i]=0;
    dis[0]=0;
    if(spfa(0))
    {
        long long ans=0;
        for(int i=1;i<=n;i++)
            ans+=dis[i];
        printf("%lld",ans);
    }
    else puts("-1");
    return 0;
}