题目描述
幼儿园里有 $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; }