题解—— 洛谷 p1993 小K的农场(差分约束&负环判断)
2024-09-20 01:17:52
看到题就可以想到差分约束
判断负环要用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 ;
}
最新文章
- git命令分类图
- 做一个会使用PS的前端开发
- 挑战程序2.1.4 穷竭搜索>;>;深度优先搜索
- Sql视图创建语句
- easyui+ashx 动态初始化datagrid(动态列头)
- IOS屏幕布局
- 国内外DNS服务器地址列表
- SQL 语句中按照in语句原有的顺序进行排序
- 使用dom4j解析xml文件
- elasticsearch系列(四)部署
- Python学习笔记010_迭代器_生成器
- [UWP]如何使用Fluent Design System (下)
- C语言程序设计第一次作业(2017.10.10完成)
- cygwin pip安装
- autpmapper映射忽略某个属性
- corefx 源码追踪:找到引起 SqlDataReader.ReadAsync 执行延迟的那行代码
- ASP.NET Core2.2 IExceptionFilter
- python之type函数
- [转帖]学习关于TTL
- Docker的学习
热门文章
- ReactiveCocoa(II)
- C# foreach 中获取索引index的方法[转]
- OpenVPN 服务端(pritunl)的一些运维经验
- 使用Hive读取ElasticSearch中的数据
- 20165215 实验一 Java开发环境的熟悉
- js相关(easyUI),触发器,ant,jbpm,hibernate二级缓存ehcache,Javamail,Lucene,jqplot,WebService,regex,struts2,oracle表空间
- oracle goldengate 远程捕获和投递
- HTML的简介
- Linux学习笔记之yum安装和卸载软件
- 【题解】Luogu P2319 [HNOI2006]超级英雄