最新文章列表

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来判定的话肯定会超时。     在牛人博客 ...
暴风雪 评论(1) 有1204人浏览 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 ...
暴风雪 评论(0) 有1379人浏览 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”。否则输 ...
暴风雪 评论(0) 有1922人浏览 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。也就是差分约束最短 ...
暴风雪 评论(0) 有1335人浏览 2012-01-20 15:29

[差分约束]poj 1716:Integer Intervals

大致题意:     需要选一些整数点,给出m个约束条件,每个条件表述为,(s,t)表示在从s到t的区间内至少有2个点被选择。求最少选择多少个点。   大致思路:     和poj1201基本相同,在此不再赘述。这道题的点是从0开始取的,要小心数组越界。   详细代码: #include<iostream> #include<cmath> #includ ...
暴风雪 评论(0) 有1175人浏览 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 ...
暴风雪 评论(0) 有1260人浏览 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”。   大致 ...
暴风雪 评论(0) 有1658人浏览 2012-01-18 20:31

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

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

最近博客热门TAG

Java(141747) C(73651) C++(68608) SQL(64571) C#(59609) XML(59133) HTML(59043) JavaScript(54918) .net(54785) Web(54513) 工作(54116) Linux(50906) Oracle(49876) 应用服务器(43288) Spring(40812) 编程(39454) Windows(39381) JSP(37542) MySQL(37268) 数据结构(36423)

博客人气排行榜

    博客电子书下载排行

      >>浏览更多下载

      相关资讯

      相关讨论

      Global site tag (gtag.js) - Google Analytics