P3275 [SCOI2011]糖果差分约束

古城微笑少年丶 2021-12-13 12:59 188阅读 0赞

## 题目描述 ##

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

## 输入输出格式 ##

输入格式：

输入的第一行是两个整数 NN，KK。接下来 KK 行，表示这些点需要满足的关系，每行 33 个数字，XX，AA，BB。

*  如果 X=1X=1， 表示第 AA 个小朋友分到的糖果必须和第 BB 个小朋友分到的糖果一样多；
 *  如果 X=2X=2， 表示第 AA 个小朋友分到的糖果必须少于第 BB 个小朋友分到的糖果；
 *  如果 X=3X=3， 表示第 AA 个小朋友分到的糖果必须不少于第 BB 个小朋友分到的糖果；
 *  如果 X=4X=4， 表示第 AA 个小朋友分到的糖果必须多于第 BB 个小朋友分到的糖果；
 *  如果 X=5X=5， 表示第 AA 个小朋友分到的糖果必须不多于第 BB 个小朋友分到的糖果；

输出格式：

输出一行，表示 \\text\{lxhgww\}lxhgww 老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出 \-1−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：  复制

## 说明 ##

对于 30\\%30% 的数据，保证 N\\leq100N≤100

对于 100\\%100% 的数据，保证 N\\leq100000N≤100000

对于所有的数据，保证 K\\leq100000, 1\\leq X\\leq5, 1\\leq A, B\\leq NK≤100000,1≤X≤5,1≤A,B≤N

比较简单的差分约束

有一个wa点是  每个人都要有糖果！！

所以连源点边的时候边长为1

加源点边的时候正序过不了  反序跑的飞起？？？？？？？？？？？？？？？？？？？

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    //input by bxd
    #define rep(i,a,b) for(int i=(a);i<=(b);i++)
    #define repp(i,a,b) for(int i=(a);i>=(b);--i)
    #define RI(n) scanf("%d",&(n))
    #define RII(n,m) scanf("%d%d",&n,&m)
    #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
    #define RS(s) scanf("%s",s);
    #define ll long long
    #define pb push_back
    #define REP(i,N)  for(int i=0;i<(N);i++)
    #define CLR(A,v)  memset(A,v,sizeof A)
    //
    #define inf 0x3f3f3f3
    const int N=1000000+5;
    const int M=10*N;
    int n;
    int pos,head[M];
    struct Edge
    {
        int nex,to,v;
    }edge[M];
    void add(int a,int b,int c)
    {
        edge[++pos].nex=head[a];
        head[a]=pos;
        edge[pos].to=b;
        edge[pos].v=c;
    }
    int dis[N];
    int vis[N];
    int cnt[N];
    
    bool spfa()
    {
        rep(i,0,n)dis[i]=-inf,vis[i]=0,cnt[i]=0;
        dis[0]=0;
        cnt[0]=1;
        vis[0]=1;
        queue<int>q;
        q.push(0);
        while(!q.empty())
        {
            int u=q.front();q.pop();
            vis[u]=0;
            for(int i=head[u];i;i=edge[i].nex)
            {
                int v=edge[i].to;
                if(dis[v]<dis[u]+edge[i].v)
                {
                    dis[v]=dis[u]+edge[i].v;
                    if(!vis[v])
                    {
                        vis[v]=1;
                        if(++cnt[v]>n)return false;
                        q.push(v);
                    }
                }
            }
        }
        return true;
    }
    bool spfa(int u)
    {
        vis[u]=1;
        for(int i=head[u];i;i=edge[i].nex)
        {
            int v=edge[i].to;
            if(dis[v]<dis[u]+edge[i].v)
            {
                dis[v]=dis[u]+edge[i].v;
                if(vis[v])return 0;
                if(!spfa(v))return 0;
            }
        }
        vis[u]=0;
        return 1;
    }
    int main()
    {
        int m;
        RII(n,m);
        rep(i,1,m)
        {
            int x,a,b;RIII(x,a,b);
            if(x==1)
            {
                add(a,b,0);add(b,a,0);
            }
            else if(x==2)
            {
                add(a,b,1);
                if(a==b){printf("-1");return 0;}
            }
            else if(x==3)
                add(b,a,0);
            else if(x==4)
            {
                add(b,a,1);
                if(a==b){printf("-1");return 0;}
            }
            else if(x==5)
                add(a,b,0);
        }
        repp(i,n,1)
        add(0,i,1),dis[i]=-inf;
    
        if(spfa())
        {
            ll ans=0;
            rep(i,1,n)
            ans+=dis[i];
            cout<<ans;
        }
        else printf("-1");
    
        return 0;
    }

转载于:https://www.cnblogs.com/bxd123/p/10808272.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211213/85f6a9532ce146da939738feb68545d9.png