首页 > 代码库 > P3275 [SCOI2011]糖果
P3275 [SCOI2011]糖果
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 71 1 22 3 24 4 13 4 55 4 52 3 54 5 1
输出样例#1：
11
说明
【数据范围】
对于30%的数据，保证 N<=100
对于100%的数据，保证 N<=100000
对于所有的数据，保证 K<=100000，1<=X<=5，1<=A, B<=N
1 #include<cstdio> 2 #include<algorithm> 3 #include<queue> 4 #include<cstring> 5 #define MAXN 100100 6 using namespace std; 7 8 struct Edge{ 9 int to,w,nxt;10 }e[MAXN<<2];11 int head[MAXN],dis[MAXN],inq[MAXN];12 bool vis[MAXN];13 int cnt,n,k;14 queue<int>q;15 16 void add(int u,int v,int w)17 {18 ++cnt;19 e[cnt].w = w;20 e[cnt].to = v;21 e[cnt].nxt = head[u];22 head[u] = cnt;23 }24 25 bool spfa()26 {27 q.push(0);28 vis[0] = true;29 dis[0] = 0;30 inq[0] = 1;31 while (!q.empty())32 {33 int u = q.front();34 q.pop();35 for (int i=head[u]; i; i=e[i].nxt)36 {37 int v = e[i].to;38 int w = e[i].w;39 if (dis[v]<dis[u]+w)40 {41 dis[v] = dis[u]+w;42 if (++inq[v]>=n) return false ;43 if (!vis[v])44 {45 q.push(v);46 vis[v] = true;47 }48 }49 }50 vis[u] = false;51 }52 return true ;53 }54 55 int main()56 {57 scanf("%d%d",&n,&k);58 for (int x,a,b,i=1; i<=k; ++i)59 {60 scanf("%d%d%d",&x,&a,&b);61 if (x==1) add(a,b,0), add(b,a,0);62 else if (x==2)63 {64 if (a==b){printf("-1\n");return 0;}65 add(a,b,1);66 }67 else if (x==3) add(b,a,0);68 else if (x==4) 69 {70 if (a==b){printf("-1\n");return 0;}71 add(b,a,1);72 }73 else add(a,b,0);74 }75 for (int i=n; i>0; i--) add(0,i,1); 76 long long ans = 0;77 if (!spfa()) printf("-1\n");78 else 79 {80 for (int i=1; i<=n; ++i)81 ans += dis[i];82 printf("%lld",ans);83 }84 return 0;85 }
P3275 [SCOI2011]糖果
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。