首页 > 编程学习 > 1043 [SCOI2011]糖果 差分约束

1043 [SCOI2011]糖果 差分约束

发布时间:2022/8/22 3:37:12

 链接:https://ac.nowcoder.com/acm/contest/26077/1043
来源:牛客网

题目描述

幼儿园里有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

输出

复制
11

备注:

对于30%的数据,保证N≤100N\leq100N100
对于100%的数据,保证 N≤100000N\leq100000N100000
对于所有的数据,保证 K≤100000,1≤X≤5,1≤A,B≤NK\leq100000, 1\leq X\leq5, 1\leq A, B\leq NK100000,1X5,1A,BN

分析

差分约束,这题是往大了的约束

原理:https://oi-wiki.org/graph/diff-constraints/

spfa 用于判环

a > b <=> a >= b + 1

a >= b <=> a >= b

a = b <=> a <= b ,a >= b

每个人至少有一个 <=> fo(i,1,n) add(0,a,1) 超级源点

出现多次 <=> 有环

//-------------------------代码----------------------------

//#define int ll
const int N = 1e5+10,M = 3e5+10;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
void add(int a,int b,int c) {e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx ++ ;} 
ll dist[N];
bool st[N];
int cnt[N];

bool spfa() {
    deque<int> q;
    q.push_back(0);
    st[0] = 1;
    ms(dist,-0x3f);
    dist[0] = 0;
    while(q.size()) {
        auto t = q.back();
        q.pop_back();
        st[t] = 0;
        fe(i,t) {
            int j = e[i];
            if(dist[j] < dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n + 1) return false;
                if(!st[j]) {
                    q.pb(j);
                    st[j] = 1;
                }
            }
        }
    }
    return 1;
}

void solve()
{
    cin>>n>>m;ms(h,-1);
    fo(i,1,m) {
        int a,b,x;cin>>x>>a>>b;
        if(x == 1) add(a,b,0),add(b,a,0);
        else if(x == 2) add(a,b,1);
        else if(x == 3) add(b,a,0);
        else if(x == 4) add(b,a,1);
        else add(a,b,0);
    }
    fo(i,1,n) add(0,i,1);
    if(!spfa()) cout<<-1<<endl;
    else {
        ll res = 0;
        fo(i,1,n) res += dist[i];
        cout<<res<<endl;
    }
}
void main_init() {}
signed main(){
    AC();clapping();TLE;
    cout<<fixed<<setprecision(12);
    main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
//    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------

 

Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号