BZOJ2330/SCOI2011/糖果

Posted on By 二价氢

#题目描述

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

#做法

差分约束

#复杂度分析

#AC Code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef vpii::iterator vpiii;
const int maxn=100005;
vpii e[maxn];
int inq[maxn],t[maxn];
long long dis[maxn];
int n,k,x,a,b;
long long spfa()
{
    int u;
    long long ans=0;
    queue<int>Q;
    for (int i=1;i<=n;i++)
        Q.push(i),t[i]=dis[i]=inq[i]=true;
    while (!Q.empty())
    {
        u=Q.front();Q.pop();inq[u]=false;
        for (vpiii v=e[u].begin();v!=e[u].end();v++)
            if (dis[v->x]<dis[u]+v->y)
            {
                dis[v->x]=dis[u]+v->y;
                if (++t[v->x]>n)
                    return -1;
                if (!inq[v->x])
                    inq[v->x]=true,Q.push(v->x);
            }
    }
    for (int i=1;i<=n;i++)
        ans+=dis[i];
    return ans;
}
int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=k;i++)
    {
        scanf("%d%d%d",&x,&a,&b);
        if (a==b && (x==2||x==4))
        {
            printf("-1\n");
            return 0;
        }
        else if (x==1)
            e[a].push_back(pii(b,0)),e[b].push_back(pii(a,0));
        else if (x==2)
            e[a].push_back(pii(b,1));
        else if (x==3)
            e[b].push_back(pii(a,0));
        else if (x==4)
            e[b].push_back(pii(a,1));
        else if (x==5)
            e[a].push_back(pii(b,0));
    }
    printf("%lld\n",spfa());
    return 0;
}