刷题总结——分糖果(bzoj2330)
2024-09-13 03:59:16
题目:
Description
幼儿园里有N个小朋友,lxhgww老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心,总是会提出一些要求,比如小明不希望小红分到的糖果比他的多,于是在分配糖果的时候,lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的,lxhgww想知道他至少需要准备多少个糖果,才能使得每个小朋友都能够分到糖果,并且满足小朋友们所有的要求。
Input
输入的第一行是两个整数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个小朋友分到的糖果;
Output
输出一行,表示lxhgww老师至少需要准备的糖果数,如果不能满足小朋友们的所有要求,就输出-1。
Sample Input
5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1
Sample Output
11
HINT
【数据范围】
对于30%的数据,保证 N<=100
对于100%的数据,保证 N<=100000
对于所有的数据,保证 K<=100000,1<=X<=5,1<=A, B<=N
题解:
差分约束模板题目·····只是注意怎样处理等于的情况就可以了
代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+;
queue<int>que;
int first[N],next[N*],go[N*],val[N*],tot=;
int cnt[N],n,k;
long long dis[N];
bool insta[N];
inline void comb(int a,int b,int c)
{
next[++tot]=first[a],first[a]=tot,go[tot]=b,val[tot]=c;
}
inline bool spfa()
{
insta[]=true,cnt[]=;
que.push();
while(!que.empty())
{
int u=que.front();
que.pop();
insta[u]=false;
for(int e=first[u];e;e=next[e])
{
int v=go[e];
if(dis[v]<dis[u]+val[e])
{
dis[v]=dis[u]+val[e];
if(!insta[v])
{
cnt[v]++;
if(cnt[v]==n+) return false;
insta[v]=true,que.push(v);
}
}
}
}
return true;
}
int main()
{
//freopen("a.in","r",stdin);
scanf("%d%d",&n,&k);
int a,b,x;
for(int i=;i<=k;i++)
{
scanf("%d%d%d",&x,&a,&b);
if(x==)
{
comb(a,b,);
comb(b,a,);
continue;
}
if(x==)
{
if(a==b)
{
cout<<"-1"<<endl;
return ;
}
comb(a,b,);
continue;
}
if(x==)
{
comb(b,a,);
continue;
}
if(x==)
{
if(a==b)
{
cout<<"-1"<<endl;
return ;
}
comb(b,a,);
continue;
}
if(x==)
{
comb(a,b,);
continue;
}
}
for(int i=n;i>=;i--)
comb(,i,);
if(spfa())
{
long long ans=;
for(int i=;i<=n;i++)
ans+=dis[i];
cout<<ans<<endl;
}
else
cout<<"-1"<<endl;
return ;
}
最新文章
- Quartz.NET Windows 服务示例
- CSS Icon 项目地址 小图标-用css写成的
- wex5 实战 框架拓展之1 公共data组件(Data)
- mysql破解root用户密码总结
- VS2010解决方案不显示无法添加项目问题
- Apache Httpd通过mod_jk连接多个Tomcat
- bzoj3208:花神的秒题计划I
- redis 源码分析
- windows服务器修改登录密码
- ●BZOJ 1853 [Scoi2010]幸运数字
- 深入分析synchronized的实现原理
- Eclipse块选择快捷键
- (转)【Java线程】Java内存模型总结
- 单字段去重 distinct 返回其他多个字段
- PAT1131(dfs)
- 微信小程序 发现之旅(二)—— 自定义组件
- Python学习摘录(下)
- Nginx优化(十七)
- css3 实现圆角边框的border-radius属性和实现阴影效果的box-shadow属性
- Linux入门-5 用户及权限基础
热门文章
- 中国区 Azure 和全球版 Azure:功能对比
- 如何通过Xcode 5中集成的XCTest框架进行简单的单元测试
- HDU 1964 Pipes (插头DP,变形)
- 解决因为手机设置字体大小导致h5页面在webview中变形的BUG
- PAT (Basic Level) Practise (中文)-1035. 插入与归并(25)
- AOP日志组件 多次获取post参数
- 字符串数组 输入3个字符串,要求按由小到大的字母顺序输出; 输入n个学生的姓名和学号到字符串数组中,在输入一个姓名,如果班级有该生则返回其信息,否则返回本班无此人
- iOS开发--使用OpenSSL生成私钥和公钥的方法
- ios之UIPickView
- C#获得DataTable的key值