[Vijos1532]区间 (差分约束)
2024-09-25 06:51:29
又是一题我不会的模板题……
讲一下差分约束吧
差分约束
如果一个系统由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 ;
}
最新文章
- Class.forName()用法及与new区别
- Mastering Web Application Development with AngularJS 读书笔记(一)
- winform最小化后隐藏到右下角,单击或双击后恢复 .
- 判断big endian和little endian的方法
- 【Android Demo】加载.gif格式图片
- 解决memcached不能远程访问的问题
- Android 之 内存管理-查看内存泄露(三)
- DB天气app冲刺第一天
- -_-#【Node】Express 400 Error: ENOENT, open
- wordpress教程之函数site_url()、home_url()、bloginfo(‘url’)的区别
- VC++ WIN32 sdk实现按钮自绘详解 之二.
- This Android SDK requires Android Developer Toolkit version 22.6.2 or above.
- asp.net 验证码技术
- 用postal.js在AngularJS中实现订阅发布消息
- [CQOI2016]手机号码
- SNMP弱口令漏洞的使用
- 第二章 TypeScript 开发环境搭建
- UITableView 顶部能够放大的图片
- poj Meteor Shower - 搜索
- 【js】深拷贝和浅拷贝区别,以及实现深拷贝的方式