博客首页 → 差分约束

最新文章列表

King 差分约束系统

/*注意将所有的不等式全都转化成<=的形式，如<1变为<=0. 注意建模。即构造不等关系。然后将两端点反向存图。接着就上bellman，果断1A。*/ #include <stdio.h> #include <cstring> #define maxn 101 struct edge { int u,v,val; } e[maxn]; int ...
差分约束 
chuilengqi 评论(0) 有7人浏览 2012-08-15 13:35

[差分约束]hdoj 3666：THE MATRIX PROBLEM

  大致题意：     给出一个n*m的矩阵map，和两个数字L，U。求出是否存在这样的数列a[1~n]，b[1~m]。使得对于每一个map[i][j]有map[i][j]*a[i]/b[j]大于等于L，小于等于U。   大致思路：     用log运算把乘法转化为加法，求出不等式。然后做差分约束。另外注意一点，如果直接用每个点入队次数大于n来判定的话肯定会超时。     在牛人博客 ...
差分约束hdoj 3666acm数据结构图论 
暴风雪 评论(1) 有1179人浏览 2012-03-10 19:54

[差分约束]poj 2983：Is the Information Reliable?

大致题意：    给出n个点的m条约束信息。每条信息表述为(P a b c)表示a在b北方距离c的位置，或者(V a b) 表示a在b北方1单位距离或者更远的位置。问是否可能存在符合以上m个要求的点。 大致思路：    把dis[i]设为其到始点的距离。第二个条件很简单dis[a]-dis[b]>=1 也就是dis[b]<=dis[a]-1。对于第一个，带等于号的条件dis[a]-di ...
差分约束poj 2983Is the Information Reliable? 
暴风雪 评论(0) 有1351人浏览 2012-01-21 03:17

[差分约束]poj 3169：Layout

大致题意：    有n头牛，按照序号1……n排队，多头牛可以站在同一个位置(暂且这么认为)，也就是任意两头牛之间的距离都大于等于0。先给出ml组约束关系(u,v,w)代表第u牛和第v牛之间的距离要小于等于w。再给出md组关系(u,v,w)，代表第u牛和第v牛之间的距离要大于等于w。求这n头牛排成的队伍能否符合以上的约束，不能的话(也就是出现负环)，输出“-1”，如果距离是inf，输出“-2”。否则输 ...
差分约束poj 3169Layout 
暴风雪 评论(0) 有1884人浏览 2012-01-20 22:17

[差分约束]poj 3159：Candies

大致题意：     给n个小孩发糖吃，给出m组约束条件，每组条件包含三个数字a b c，表示b得到的糖果数目不能比a多超过c个。求第n个人得到的糖果数比第一个人最多能多几个。   大致思路：     spfa差分约束，dis[i]为第i人得到的糖果数目。对于每个约束管理就能列出不等式：dis[a]>=dis[b]-c，就能转化为dis[b]<=dis[a]+c。也就是差分约束最短 ...
差分约束poj3159Candies 
暴风雪 评论(0) 有1309人浏览 2012-01-20 15:29

[差分约束]poj 1716：Integer Intervals

大致题意：     需要选一些整数点，给出m个约束条件，每个条件表述为，(s,t)表示在从s到t的区间内至少有2个点被选择。求最少选择多少个点。   大致思路：     和poj1201基本相同，在此不再赘述。这道题的点是从0开始取的，要小心数组越界。   详细代码： #include<iostream> #include<cmath> #includ ...
差分约束poj 1716Integer Intervals 
暴风雪 评论(0) 有1152人浏览 2012-01-19 23:03

[差分约束]poj 1201：Award Contest

大致题意：    需要从0~50000内选一些整数点，给出m个约束条件，每个条件表述为，(s,t,c)表示在从s到t的区间内至少有c个点被选择。求最少选择多少个点。大致思路：    转化为差分约束模型，设dis[i]为从0到i这个区间中被选择的点数。对每个约束，则有dis[t]-dis[s-1]&gt;=c。另外还有一个隐含的约束条件就是0<=dis[i]-dis[i-1]<=1 ...
差分约束poj 1201Award Contest 
暴风雪 评论(0) 有1230人浏览 2012-01-19 22:56

[差分约束]poj 1364：King

大致题意：    告诉你有一列长度为n的数列和m个关系式。每个关系式的表述为：    si ni “gt” c 或者是  si ni “lt” c。分别代表该数列第si项一直加到第si+ni项的和大于c，和第si项一直加到第si+ni项的和小于c。求是否存在满足以上m个要求的数列。是则输出“lamentable kingdom”，否则输出“successful conspiracy”。   大致 ...
差分约束poj 1364King 
暴风雪 评论(0) 有1610人浏览 2012-01-18 20:31

[转载]差分约束系统详解

（本文假设读者已经有以下知识：最短路径的基本性质、Bellman-Ford算法。）    比如有这样一组不等式：   X1 - X2 <= 0X1 - X5 <= -1X2 - X5 <= 1X3 - X1 < ...
差分约束资料acm 
暴风雪 评论(0) 有851人浏览 2012-01-18 02:39

最近博客热门TAG

Java(141744) C(73651) C++(68608) SQL(64571) C#(59609) XML(59133) HTML(59043) JavaScript(54919) .net(54785) Web(54514) 工作(54118) Linux(50905) Oracle(49875) 应用服务器(43289) Spring(40812) 编程(39454) Windows(39381) JSP(37542) MySQL(37267) 数据结构(36424)

博客人气排行榜

    博客电子书下载排行

      >>浏览更多下载

      相关资讯

      相关讨论

      Global site tag (gtag.js) - Google Analytics