又是一题我不会的模板题……

讲一下差分约束吧

差分约束

参考博客

如果一个系统由n个变量和m个约束条件组成,形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则称其为差分约束系统。——某百科

说简单点吧

就是两值相减 是差分

相减得到的值在一个范围内 是约束

大致是求解一些数学方程问题的

本蒟蒻不会……

大致好像是用最短路来做

本蒟蒻不会最短路……

不会差分约束……

所以就很颓废了。

本题

[题目链接]

我抄题解的

太弱了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
const int lim=;
const int inf=;
int d[lim<<];
struct self{int x,y,w;}s[lim<<];
int first[lim<<],nxt[lim<<];
int m,n,a,b,c,tn,x,y,w;
queue<int>q;
bool inq[lim];
void add(int x,int y,int w)
{
n++;
s[n].x=x;s[n].y=y;s[n].w=w;
nxt[n]=first[x];first[x]=n;
}
void spfa()
{
int a,b;
for(a=;a<=m+;a++)d[a]=-inf;
d[]=;
q.push();
while(!q.empty())
{
int u=q.front();q.pop();inq[u]=;
for(int e=first[u];e!=-;e=nxt[e])
{
if(d[s[e].y]<d[u]+s[e].w)
{
d[s[e].y]=d[u]+s[e].w;
if(!inq[s[e].y])
{
q.push(s[e].y);
inq[s[e].y]=;
}
}
}
}
cout<<d[m+]<<endl;
}
int main()
{
memset(first,-,sizeof(first));memset(nxt,-,sizeof(nxt));
scanf("%d",&tn);
m=;
for(a=;a<=tn;a++)
{
scanf("%d%d%d",&x,&y,&w);
x++;y++;
m=max(m,x);m=max(m,y);
add(x-,y,w);
}
for(a=;a<=m+;a++)
{
add(a,a-,-);
add(a-,a,);
}
spfa();
return ;
}

最新文章

  1. Class.forName()用法及与new区别
  2. Mastering Web Application Development with AngularJS 读书笔记(一)
  3. winform最小化后隐藏到右下角,单击或双击后恢复 .
  4. 判断big endian和little endian的方法
  5. 【Android Demo】加载.gif格式图片
  6. 解决memcached不能远程访问的问题
  7. Android 之 内存管理-查看内存泄露(三)
  8. DB天气app冲刺第一天
  9. -_-#【Node】Express 400 Error: ENOENT, open
  10. wordpress教程之函数site_url()、home_url()、bloginfo(‘url’)的区别
  11. VC++ WIN32 sdk实现按钮自绘详解 之二.
  12. This Android SDK requires Android Developer Toolkit version 22.6.2 or above.
  13. asp.net 验证码技术
  14. 用postal.js在AngularJS中实现订阅发布消息
  15. [CQOI2016]手机号码
  16. SNMP弱口令漏洞的使用
  17. 第二章 TypeScript 开发环境搭建
  18. UITableView 顶部能够放大的图片
  19. poj Meteor Shower - 搜索
  20. 【js】深拷贝和浅拷贝区别,以及实现深拷贝的方式

热门文章

  1. 即时通讯协议之XMPP
  2. 通过自定义比较器排序(C#版)
  3. python列表1
  4. python 在WINDOS虚拟环境部署
  5. 从oracle到mysql
  6. sql select中加入常量列
  7. JS获取地址栏的参数值
  8. la 4490
  9. 【Arduino】开发入门【十】Arduino蓝牙模块与Android实现通信
  10. python全栈开发day62-两表操作增删改查,外键,if else模板语法