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

 

思路:

主要考察差分约束,可以通过这篇博文http://www.cnblogs.com/void/archive/2011/08/26/2153928.html了解其基本原理和一些大体的变形

  • 首先就是要根据题目中的不等关系建立有向图。怎么建图?每次将不等关系转化为大于且等于的关系,由后者向前者发出有向边建图。以x=1为例,这时候A和B两个小朋友分配的糖果一样多,那么有A-B=0,B-A=0,这时候分别从A出发,向B建立一条长度为0的边,再从B出发,向A建立一条长度为0的边,表示两者的关系;再如x=2,A的糖果小于B,那么A-B<0,那么有A-B<=-1,那么有B-A>=1,这时候从A出发向B建立一条长度为1的边;其余条件同理。
  • 题目要求:老师至少需要准备的糖果数。即老师给每个学生发的糖要满足题目中的各个约束条件,转化为有向图就是要求有向图的最长路(因为只有最长路都满足了,其余条件才能保证一定满足)。不妨想像一下什么时候题目无解?对,就是图中出现正权环!为了判断正权环,采用SPFA,统计每个节点入队的次数,大于总结点数-1则说明图中有正权环。
  • 同时注意:因为每个人得到的糖果数必须为正,新增加一个节点0,从0向每个人出发引入一条长度为1的边,再通过SPFA统计图中的最长路。
  • 特判:X=2和X=4时,如果A,B两个人的糖果数相同直接输出-1结束。
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#define mp make_pair
#define int long long
using namespace std;
vector<pair<int,int> >ed[100010];
queue<int> Q;
int n,k;
int vis[100010],dis[100010];
int inq[100010];
int cnt[100010];
int spfa(int v){
    Q.push(v);
    inq[v]=1;
    
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        inq[u]=0;        
        cnt[u]++;
        if(cnt[u]>n){//一共有n+1个节点(包括补充的节点0),SPFA每个节点在队列出现的次数不能超过总结点数-1(这里是n)
            return 0;
        }
        for(int i=0;i<ed[u].size();i++){
            int nxt=ed[u][i].first,d=ed[u][i].second;
            if(dis[nxt]<dis[u]+d){
                dis[nxt]=dis[u]+d;
                if(!inq[nxt]){
                    inq[nxt]=1;
                    Q.push(nxt);
                }
            }
        }
    }
    return 1;
}
signed main(){
    scanf("%lld %lld",&n,&k);
    for(int i=0;i<k;i++){
        int x,a,b;
        scanf("%lld %lld %lld",&x,&a,&b);
        if(x==1){ed[a].push_back(mp(b,0));ed[b].push_back(mp(a,0));}
        else if(x==2){ed[a].push_back(mp(b,1));if(a==b){printf("-1\n");return 0;}} //1.特判 
        else if(x==3){ed[b].push_back(mp(a,0));}
        else if(x==4){ed[b].push_back(mp(a,1));if(a==b){printf("-1\n");return 0;}}//1.特判 
        else {ed[a].push_back(mp(b,0));} 
    }
    for(int i=1;i<=n;i++) ed[0].push_back(mp(i,1));
    
    if(!spfa(0)){
        printf("-1\n");
        return 0;
    }
    
    int ans=0;
    for(int i=1;i<=n;i++) ans+=dis[i];
    printf("%lld\n",ans);

    return 0;
}

 

上一篇:Dijkstra模板


下一篇:[NOI.AC省选模拟赛3.31] 附耳而至 [平面图+最小割]