洛谷 P3275 BZOJ 2330 [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。
输入输出样例
5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1
11
说明
【数据范围】
对于30%的数据,保证 N<=100
对于100%的数据,保证 N<=100000
对于所有的数据,保证 K<=100000,1<=X<=5,1<=A, B<=N
解题思路
一道差分约束的裸题,不懂差分约束的看这里,我就是看那篇博文看懂的差分约束,它被百度放到了第一个,实属不易,少有的不谋财害命的事例啊。
这题要求的是最小值,那么我们需要求出一堆$x_i-x_j>=c$的式子,然后求0点到其他点最长路之和,如果存在负环或自己不等于自己的,则输出-1
顺便从0连一条权值为1的边到其他所有点,根据一些玄学的东西(2019年01月26日更新 莫非是因为链式前向星倒着存边?先留坑),要按n到1的顺序连,否则某些成链的点跑不过去,然后跑spfa即可,我找负环、求最长路用的是dfs型的spfa,代码短一些。
源代码
#include<stdio.h>
int n,m; struct edge{
int next,to,w;
}e[];
int head[]={},cnt=;
void add(int u,int v,int w)
{
e[cnt]={head[u],v,w};
head[u]=cnt++;
} int dis[];
bool ins[]={};
bool spfa(int u)
{
ins[u]=;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to,w=e[i].w;
if(dis[v]<dis[u]+w)
{
dis[v]=dis[u]+w;
if(ins[v]||!spfa(v)) return false;
}
}
ins[u]=;
return true;
} int main()
{
scanf("%d%d",&n,&m);
for(int i=,mode,u,v;i<=m;i++)
{
scanf("%d%d%d",&mode,&u,&v);
if(mode==)
add(v,u,),add(u,v,);
else if(mode==)
{
if(u==v)
{
puts("-1");
return ;
}
add(u,v,);
}
else if(mode==)
{
add(v,u,);
}
else if(mode==)
{
if(u==v)
{
puts("-1");
return ;
}
add(v,u,);
}
else
{
add(u,v,);
}
}
for(int i=n;i>=;i--)
add(,i,);
for(int i=;i<=n;i++)
dis[i]=;
dis[]=;
if(spfa())
{
long long ans=;
for(int i=;i<=n;i++)
ans+=dis[i];
printf("%lld",ans);
}
else puts("-1");
return ;
}
最新文章
- Linux初识二
- ASP.NET MVC 设置Area中 Controller 的方法 默认启动页
- java中static 和 final 的一些使用规则
- Resumable.js – 基于 HTML5 File API 的文件上传
- Gulan查询UI排布
- 用 eric6 与 PyQt5 实现python的极速GUI编程(系列02)---- 省市县(区)下拉列表多级联动
- MySQL数据库远程连接
- ubuntu下安装svn
- imx51-linux的cpuinfo之分析
- DAY4(PYTHON)列表的嵌套,range,for
- Guava Cache用法介绍<;转>;
- System.Web.WebPages.Html.HtmlHelper”不包含XXXX
- 偷懒把本来要判断输入值的textbox 输出提示值,结果点两次程序异常
- MAC系统下用Idea创建spring boot工程 基于maven
- myeclipse和maven的clean和build
- Java枚举根据key获取value
- Object之wait
- 磁盘 ->; 硬盘 ->; c盘 &;&; 内存
- Django请求响应对象
- 20155238 2016-2017-2 《Java程序设计》第二周学习总结