P4878 [USACO05DEC] 布局
2024-09-05 15:49:32
这居然是个紫题???原谅我觉得这题是模板。。。
这个这个,这题的算法呢其实是一个叫差分约束的东西,也是今天下午我们机房的重点,如果不知道这个差分约束是个啥的人呢,自行百度一下谢谢。。
好吧还是简单介绍一下,简而言之,就是对一堆子不等式进行最短路模型化,然后依照问题用最短(长)路跑一(两)遍,基本上就可以求出答案
那么剩下的东西呢都在代码里了
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std; int n,l,d,tot;
bool ok;
int dis[],c[],head[],next[],w[],to[];
bool vis[];
queue < int > q; void add(int v,int u,int p){//链式前向星不用多介绍了吧(这玩意要是不会的真的建议理解一下,平时做题复制粘贴虽然可以,但考场不行啊)
next[++tot]=head[v];
to[tot]=u;
w[tot]=p;
head[v]=tot;
} void spfa(int s){//由于可能有环及负权边,故用spfa求解
memset(dis,0x3f,sizeof(dis));
dis[s]=;
memset(c,,sizeof(c));
memset(vis,,sizeof(vis));
while(!q.empty()){q.pop();}
q.push(s);
vis[s]=;
ok=;
while(!q.empty()){
int x;
x=q.front();
q.pop();
vis[x]=;
for(int k=head[x];k;k=next[k]){
int y=to[k];
if(dis[x]+w[k]<dis[y]){
dis[y]=dis[x]+w[k];
if(!vis[y]){
vis[y]=;
c[y]++;
q.push(y);
}
if(c[y]>n){//处理负环的情况
ok=;
return;
}
}
}
}
return;
} int main(){
scanf("%d%d%d",&n,&l,&d);
for(int i=;i<=n;i++){//这段赋值可以对建图进行预处理,进而处理图非连通的情况
add(,i,);
}
for(int i=;i<=l;i++){//这个读入和下一个读入就是差分约束的核心,简而言之,就是小于等于时建一条a指向b权值为c的边(换行嘤嘤嘤)
int a,b,c;//大于等于时建一条b指向a权值为-c的边
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
for(int i=;i<=d;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(b,a,-c);
}
spfa();
if(!ok){//负环
printf("-1\n");
return ;
}
spfa();
if(!ok){//负环
printf("-1\n");
}
else if(dis[n]==0x3f3f3f3f){//不连通
printf("-2\n");
}
else{
printf("%d\n",dis[n]);//输出
}
return ;
}
嗯呐还有好多篇要写,就这样了
最新文章
- SQL Server-5种常见的约束
- MySQL 使用JOIN优化子查询
- Win10---------专区
- BZOJ2555——SubString
- PopupWindow
- 多线程BackgroundWorker
- Java对象克隆(Clone)及Cloneable接口、Serializable接口的深入探讨
- Report_客制化报表输出Excel后去0问题(案例)
- ffmpeg/ffplay vc6 源码剖析
- 显示 png 图片
- 【HDOJ】2510 符号三角形
- 捉Bug:易车注册页布局小臭虫 附demo
- T-SQL 语句
- SSM与jsp传递实体类
- docker学习笔记(一)—— ubuntu16.04下安装docker
- Python3.5 学习二十一
- Visual Studio 2017 系统发布部署服务器教程
- 第二阶段Sprint冲刺会议5
- matlab for 运算的提速
- hibernate cascade的真正含义
热门文章
- 10.17小作业 基于TCP开发一款远程CMD程序
- qt5-Qt Creator使用
- 2017noip总结
- SQLSERVER 连接常见问题
- BZOJ 1095: [ZJOI2007]Hide 捉迷藏 动态点分治+堆
- 51 Nod 大鱼吃小鱼
- java取小数点后两位
- 前端MVC、MVVM的简单实现
- Javascript事件:this.value()和this.select()
- LeetCode 236. 二叉树的最近公共祖先(Lowest Common Ancestor of a Binary Tree)