【bzoj2330】[SCOI2011]糖果 差分约束系统
发布日期:2022-03-11 15:03:42 浏览次数:8 分类:技术文章

本文共 1861 字,大约阅读时间需要 6 分钟。

题目描述

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

样例输入

5 7

1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1

样例输出

11


题解

差分约束系统

把所有的约束转化为两个点之间连边,用spfa处理。

具体地,x<y:x->y(1),x≤y:x->y(0),x==y:x<->y(0)

由于每个数都为正,再加S->i(1)。

然后跑最长路即可。

#include 
#include
#include
using namespace std;typedef long long ll;queue
q;int head[100010] , to[300010] , next[300010] , cnt , inq[100010] , num[100010];ll dis[100010] , len[300010];void add(int x , int y , ll z){ to[++cnt] = y; len[cnt] = z; next[cnt] = head[x]; head[x] = cnt;}int main(){ int n , k , t , x , y , i; ll ans = 0; scanf("%d%d" , &n , &k); while(k -- ) { scanf("%d%d%d" , &t , &x , &y); switch(t) { case 1: add(x , y , 0); add(y , x , 0); break; case 2: add(x , y , 1); break; case 3: add(y , x , 0); break; case 4: add(y , x , 1); break; default: add(x , y , 0); } } for(i = 1 ; i <= n ; i ++ ) dis[i] = 1 , inq[i] = 1 , q.push(i); while(!q.empty()) { x = q.front() , q.pop() , inq[x] = 0; for(i = head[x] ; i ; i = next[i]) { if(dis[to[i]] < dis[x] + len[i]) { dis[to[i]] = dis[x] + len[i]; if(!inq[to[i]]) { if(num[to[i]] >= n) { printf("-1\n"); return 0; } num[to[i]] ++ , inq[to[i]] = 1 , q.push(to[i]); } } } } for(i = 1 ; i <= n ; i ++ ) ans += dis[i]; printf("%lld\n" , ans); return 0;}

 

转载于:https://www.cnblogs.com/GXZlegend/p/6617326.html

转载地址:https://blog.csdn.net/weixin_30267785/article/details/99218867 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:JAVA SE11环境变量配置(Windows)
下一篇:pandas中Dataframe的查询方法([], loc, iloc, at, iat, ix)

发表评论

最新留言

初次前来,多多关照!
[***.217.46.12]2024年03月23日 21时47分24秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

php中的变量名称用什么表示,PHP变量,方法,类等名称中的有效字符是什么? 2019-04-21
pic32mx是什么cpu_PIC32MX单片机外设库使用(Ⅰ)- 系统时钟及I/O口基本设置 2019-04-21
用c 在mysql上存图片_C 批量保存图片进 mysql 利用MYSQL_BIND插入longblob 2019-04-21
mysql 1045 28000_mysql报关于用户密码1045(28000),几种处理方法 (zhuan) 2019-04-21
solr比mysql的优势_Solr与Elasticsearch的优缺点比较总结和归纳 2019-04-21
华为博士招聘上机考试题目_牛客网-华为-2020届校园招聘上机考试-3 2019-04-21
python中for可以做变量名吗_Python中使用动态变量名的方法 2019-04-21
mysql 日期转换天数_MySQL 日期操作 增减天数、时间转换、时间戳 2019-04-21
java对象去重复_JAVA中List对象去除重复值的方法 2019-04-21
java bss_[转] .bss段和.data段的区别 2019-04-21
java上传图片损坏_大神求助 上传图片后 图片损坏 2019-04-21
java socket唯一标识符_Java Socket编程之常识网络基础知识 2019-04-21
java给xyz大小排序_java递归实现string xyz排序 2019-04-21
arctime必须要java_Arctime使用教程 Arctime常见问题解答 2019-04-21
mysql pxc mysql5.7_mysql之PXC5.7.18集群系列——1. Percona XtraDB Cluster 搭建 2019-04-21
mysql 自适应字段宽度_box-sizing解决自适应布局容器宽度问题 2019-04-21
java 配置文件配置路径_Java读取配置文件路径设置 2019-04-21
vux 选择器_vue中的scoped分析以及在element-UI和vux中的应用 2019-04-21
java cache 有效期_springboot cache 自定义过期时间及自定义缓存key前缀 2019-04-21
java实验一目的_Java实验报告(实验一) 2019-04-21