文档章节

poj 3169 Layout (差分约束+Bellman )

猪刚烈
 猪刚烈
发布于 2014/09/24 13:59
字数 345
阅读 12
收藏 0

题意:输入NML MDN默示有N个牛按1-N排成一排,ML,默示有ML行,每行输入A, B, D默示A牛和B牛最远间隔为DMD默示有MD行,每行输入A,B,D默示A牛和B来间隔为D,求满足所有前提的1-N的最大间隔。

比较简单的差分约束,这个周周赛的A题

  1. #include <iostream> 
  2. #include <cstdlib> 
  3. #include <cstdio> 
  4. #include <cstring> 
  5. #include <queue> 
  6. #include <stack> 
  7. #include <algorithm> 
  8. const int N = 210
  9. const int maxn = 1010
  10. const int maxm = 21000
  11. #define FOR(i,a,b) for(int i=a;i<b;i++) 
  12. #define init(a) memset(a,0,sizeof(a)) 
  13. #define MIN INT_MIN 
  14. #define MAX INT_MAX 
  15. #define LL long long 
  16. using namespace std; 
  17. const int INF=0x3f3f3f3f
  18.  
  19. int dis[maxm],cnt,n; 
  20. struct node 
  21.     int u,v,w; 
  22. } edge[maxm]; 
  23. void add(int u,int v,int w) 
  24.     edge[cnt].u=u
  25.     edge[cnt].v=v
  26.     edge[cnt].w=w
  27.     cnt++; 
  28. int Bellman(int s,int t) 
  29.     int flag; 
  30.     FOR(i,0,t+1) 
  31.     { 
  32.         dis[i]=INF; 
  33.     } 
  34.     dis[s]=0; 
  35.     FOR(i,0,n) 
  36.     { 
  37.         flag=0
  38.         FOR(j,0,cnt) 
  39.         { 
  40.             if(dis[edge[j].v] > dis[edge[j].u] + edge[j].w) 
  41.             { 
  42.                 dis[edge[j].v] = dis[edge[j].u] + edge[j].w; 
  43.                 flag = 1
  44.             } 
  45.         } 
  46.         if(!flag) 
  47.             break; 
  48.     } 
  49.     if(flag==1) 
  50.         return -1; 
  51.     else if(dis[t]==INF) 
  52.         return -2; 
  53.     else 
  54.         return dis[t]; 
  55. int main() 
  56.     int u,v,w,a,b; 
  57.     while(scanf("%d%d%d",&n,&a,&b)!=EOF) 
  58.     { 
  59.         cnt=0
  60.         FOR(i,0,a) 
  61.         { 
  62.             scanf("%d%d%d",&u,&v,&w); 
  63.             add(u,v,w); 
  64.         } 
  65.         FOR(i,0,b) 
  66.         { 
  67.             scanf("%d%d%d",&u,&v,&w); 
  68.             add(v,u,-w); 
  69.         } 
  70.       int ans = Bellman(1,n); 
  71.       cout<<ans<<endl
  72.     } 
  73.     return 0; 

本文转载自:http://blog.csdn.net/weitao1234/article/details/38935981

猪刚烈
粉丝 22
博文 708
码字总数 110
作品 1
海淀
程序员
私信 提问
POJ ~ 3169 ~ Layout (SPFA + 差分约束)

题意:输入N,ML,MD表示N个人编号为1-N,有ML+MD行,每行三个数字A,b,C。前ML行表示,A和B的距离不能大于C,接下来MD行表示,A和B的距离不能小于C。这些人必须都在一条线上,且两个人位置不...

ZscDst
2018/01/31
0
0
一个搞ACM需要掌握的算法

ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的. 第一阶段:练经典常用...

long0404
2015/06/24
0
0
POJ 3169 Layout 【差分约束系统 + 最短路模型】

传送门 // 有n头奶牛, 然后给出一些奶牛之间的必须从存在的一些距离限制, 问你是否有可能存在一种排列满足所给的限制条件. 如果有则输出1 - n 头奶牛最长的距离是多少. 如果不存在输出-1, 如...

Anxdada
2018/02/02
0
0
算法进阶路径

第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Fl...

暖冰
2016/04/02
156
1
POJ ~ 1201 ~ Intervals (差分约束 + SPFA最长路)

题意:给定n(n <= 50000)个整点闭区间和这个区间中至少有多少整点需要被选中,每个区间的范围为[ai, bi],并且至少有ci个点需要被选中,其中0 <= ai <= bi <= 50000,问[0, 50000]至少需要...

zscdst
2018/04/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Rabbit MQ 延迟消息发送

为什么使用延迟消息? 不同于同步消息,有些业务场景下希望可以实现延迟一定时间再消费消息。 典型的场景有微信、支付宝等第三方支付回调接口,会在用户支付后3秒、5秒、30秒等等时间后向应用...

兜兜毛毛
7分钟前
2
0
【0918】正则介绍_grep

【0918】正则介绍_grep 9.1 正则介绍_grep上 9.2 grep中 9.3 grep下 一、正则介绍 正则是一串有规律的字符串,它使用单个字符串来描述或匹配一系列符合某个语法规则的字符串。 二、grep工具 ...

飞翔的竹蜻蜓
37分钟前
4
0
为什么要在网站中应用CDN加速?

1. 网页加载速度更快 在网站中使用CDN技术最直接的一个好处就是它可以加快网页的加载速度。首先,CDN加速的内容分发是基于服务器缓存的,由于CDN中缓存了不少数据,它能够给用户提供更快的页...

云漫网络Ruan
今天
8
0
亚玛芬体育(Amer Sports)和信必优正式启动合作开发Movesense创新

亚玛芬体育和信必优正式启动合作开发Movesense创新,作为亚玛芬体育的完美技术搭档,信必优利用Movesense传感器技术为第三方开发移动应用和服务。 Movesense基于传感器技术和开放的API,测量...

symbiochina88
今天
4
0
创龙TI AM437x ARM Cortex-A9 + Xilinx Spartan-6 FPGA核心板规格书

SOM-TL437xF是一款广州创龙基于TI AM437x ARM Cortex-A9 + Xilinx Spartan-6 FPGA芯片设计的核心板,采用沉金无铅工艺的10层板设计,适用于高速数据采集和处理系统、汽车导航、工业自动化等领...

Tronlong创龙
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部