Luogu1993 小K的农场 (差分约束)
2024-09-07 22:44:49
\(if \ a - b <= c, AddEdge(b, a, c)\)
Be careful, MLE is not good.
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ON_DEBUGG
#ifdef ON_DEBUGG
#define D_e_Line printf("\n----------\n")
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#else
#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#endif
using namespace std;
struct ios{
template<typename ATP>inline ios& operator >> (ATP &x){
x = 0; int f = 1; char ch;
for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();
x *= f;
return *this;
}
}io;
const int N = 20007;
struct Edge{
int nxt, pre, w;
}e[N << 1];
int head[N], cntEdge;
inline void add(int u, int v, int w){
e[++cntEdge] = (Edge){ head[u], v, w}, head[u] = cntEdge;
}
int vis[N], dis[N];
inline bool SPFA(int u){
vis[u] = true;
for(register int i = head[u]; i; i = e[i].nxt){
if(dis[e[i].pre] > dis[u] + e[i].w){
dis[e[i].pre] = dis[u] + e[i].w;
if(vis[e[i].pre] || SPFA(e[i].pre)){
return true;
}
}
}
vis[u] = false;
return false;
}
int main(){
//FileOpen();
int n, m;
io >> n >> m;
R(i,1,m){
int opt;
io >> opt;
if(opt == 1){
int x, y, w;
io >> x >> y >> w;
add(x, y, -w);
}
else if(opt == 2){
int x, y, w;
io >> x >> y >> w;
add(y, x, w);
}
else if(opt == 3){
int x, y;
io >> x >> y;
add(x, y, 0);
add(y, x, 0);
}
}
R(i,1,n){
add(0, i, 0); // this sentence caused MLE !
dis[i] = 0x3f3f3f3f;
}
if(SPFA(0) == false){
printf("Yes\n");
}
else{
printf("No\n");
}
return 0;
}
最新文章
- Angular中ngCookies模块介绍
- js获取输入框中当前光标位置并在此位置插入字符串的方法(angularjs+ts)
- 转:HTML网页中插入视频各种方法
- Adding New Functions to MySQL(User-Defined Function Interface UDF、Native Function)
- k8s入门系列之介绍篇
- 【转载】知乎答案----孙志岗----Google 发布了程序员养成指南,国内互联网巨头是否也有类似的指南和课程推荐
- Sqli-labs less 16
- jQuery mouseover与mouseenter,mouseout与mouseleave的区别
- ";解密";微信开放高级接口 企业如何应对
- 创业青年:刘霞(YBC推荐)_CCTV.com_中国中央电视台
- 基于visual Studio2013解决面试题之0407数组差
- XP下类似%windir% %userprofile% 的变量的说明(转)
- 在windows上搭建ipv6代理
- c3p0使用记录
- 简单谈谈数据库DML、DDL和DCL的区别
- 开源WHMCS支付宝当面付和即时到账插件
- Vim——回顾整理
- (水题) Div 3 -- SGU -- 105
- RabbitMQ使用笔记
- Error_OAF_Flex VO() of flex bean (ExpenseDescFlexs) is null (异常)
热门文章
- MongoDB学习总览
- Tensor的向量化
- Spring Security:用户和Spring应用之间的安全屏障
- web自动化之元素定位篇
- hadoop集群搭建——单节点(伪分布式)
- jenkins安装配置及发布
- Linux的文件路径和访问文件相关命令
- nginx启动失败/报错(bind() to 0.0.0.0:80 failed (10013: An attempt was made to access a socket...permissions) nginx启动失败
- UML图记忆技巧
- 在项目中导入lombok依赖自动生成有参,无参 空参 方法的注解