看到题就可以想到差分约束

判断负环要用dfs,bfs-spfa会TLE 4个点

bfs-spfa

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = ;
const int MAXM = ;
int cnt=,u[MAXM],v[MAXM],w[MAXM],first[MAXN],next[MAXM];
bool vis[MAXN];
int inq[MAXN],dis[MAXN],f[MAXN];
int n,m;
void addedge(int ux,int vx,int wx){
++cnt;
u[cnt]=ux;
v[cnt]=vx;
w[cnt]=wx;
next[cnt]=first[ux];
first[ux]=cnt;
}
bool spfa(int s,int t){
queue<int> q;
for(int i=;i<=n+;i++){
dis[i]=0x3f3f3f3f;
}
q.push(s);
dis[s]=;
inq[s]=;
vis[s]=;
f[s]=;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=;
f[u]=;
for(int i=first[u];i;i=next[i]){
if(w[i]+dis[u]<dis[v[i]]){
dis[v[i]]=w[i]+dis[u];
if(!vis[v[i]]){
vis[v[i]]=;
inq[v[i]]++;
q.push(v[i]);
if(inq[v[i]]>n)
return false;
}
}
}
}
return true;
}
int main(){
cin>>n>>m;
int a,b,c,mode;
for(int i=;i<=m;i++){
cin>>mode;
if(mode==){
cin>>a>>b>>c;
addedge(a,b,-c);
}
else if(mode==){
cin>>a>>b>>c;
addedge(b,a,c);
}
else{
cin>>a>>b;
addedge(a,b,);
addedge(b,a,);
}
}
for(int i=;i<=n;i++)
if(!f[i])
if(!spfa(i,)){
printf("No\n");
return ;
}
printf("Yes\n");
return ;
}

dfs-spfa

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = ;
const int MAXM = ;
int cnt=,u[MAXM],v[MAXM],w[MAXM],first[MAXN],next[MAXM];
int vis[MAXN];
int inq[MAXN],dis[MAXN],f[MAXN];
int n,m;
void addedge(int ux,int vx,int wx){
++cnt;
u[cnt]=ux;
v[cnt]=vx;
w[cnt]=wx;
next[cnt]=first[ux];
first[ux]=cnt;
}
bool flag=false;
void spfa(int ux){
vis[ux]=;
for(int i=first[ux];i;i=next[i]){
if(dis[ux]+w[i]<dis[v[i]]){
if(vis[v[i]]){
flag=true;
return;
}
dis[v[i]]=dis[ux]+w[i];
spfa(v[i]);
}
}
vis[ux]=;
return;
}
int main(){
cin>>n>>m;
int a,b,c,mode;
for(int i=;i<=m;i++){
cin>>mode;
if(mode==){
cin>>a>>b>>c;
addedge(a,b,-c);
}
else if(mode==){
cin>>a>>b>>c;
addedge(b,a,c);
}
else{
cin>>a>>b;
addedge(a,b,);
addedge(b,a,);
}
}
for(int i=;i<=n;i++){
dis[i]=;
spfa(i);
if(flag){
printf("No\n");
return ;
}
}
printf("Yes\n");
return ;
}

最新文章

  1. git命令分类图
  2. 做一个会使用PS的前端开发
  3. 挑战程序2.1.4 穷竭搜索&gt;&gt;深度优先搜索
  4. Sql视图创建语句
  5. easyui+ashx 动态初始化datagrid(动态列头)
  6. IOS屏幕布局
  7. 国内外DNS服务器地址列表
  8. SQL 语句中按照in语句原有的顺序进行排序
  9. 使用dom4j解析xml文件
  10. elasticsearch系列(四)部署
  11. Python学习笔记010_迭代器_生成器
  12. [UWP]如何使用Fluent Design System (下)
  13. C语言程序设计第一次作业(2017.10.10完成)
  14. cygwin pip安装
  15. autpmapper映射忽略某个属性
  16. corefx 源码追踪:找到引起 SqlDataReader.ReadAsync 执行延迟的那行代码
  17. ASP.NET Core2.2 IExceptionFilter
  18. python之type函数
  19. [转帖]学习关于TTL
  20. Docker的学习

热门文章

  1. ReactiveCocoa(II)
  2. C# foreach 中获取索引index的方法[转]
  3. OpenVPN 服务端(pritunl)的一些运维经验
  4. 使用Hive读取ElasticSearch中的数据
  5. 20165215 实验一 Java开发环境的熟悉
  6. js相关(easyUI),触发器,ant,jbpm,hibernate二级缓存ehcache,Javamail,Lucene,jqplot,WebService,regex,struts2,oracle表空间
  7. oracle goldengate 远程捕获和投递
  8. HTML的简介
  9. Linux学习笔记之yum安装和卸载软件
  10. 【题解】Luogu P2319 [HNOI2006]超级英雄