社区讨论
吸氧AC,不吸氧75,求助
P1993小 K 的农场参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo2tvypm
- 此快照首次捕获于
- 2023/10/23 19:42 2 年前
- 此快照最后确认于
- 2023/10/23 19:42 2 年前
如题,如有大佬可以帮调一下。
CPP#include<cstring>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
const int M=5e3+10;
int n,m,idx=0;
int h[M*2]={-1},to[M*2],ne[M*2],d[M*2],w[M*2],tot[M*2];
bool vst[M*2];
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
void add(int a,int b,int c)
{
w[++idx]=c;
to[idx]=b;
ne[idx]=h[a];
h[a]=idx;
}
bool spfa(int s)
{
queue<int> q;
memset(d,0x3f,sizeof d);
d[s]=0;
vst[s]=true;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
vst[u]=false;
for(int i=h[u];i>0;i=ne[i])
{
int v=to[i];
if(d[v]>d[u]+w[i])
{
d[v]=d[u]+w[i];
tot[v]++;
if(tot[v]==n)
return false;
if(!vst[v])
{
vst[v]=true;
q.push(v);
}
}
}
}
return true;
}
int main()
{
n=read();
m=read();
memset(h,-1,sizeof(h));
memset(d,0x3f,sizeof(d));
for(int i=1;i<=n;i++)
add(0,i,0);
for(int i=1;i<=m;i++)
{
int ffff,a1,b1,c1;
ffff=read();
a1=read();
b1=read();
if(ffff==1)
/* a1-b1>=c1
变形为
b1-a1<=-c1
即
b1<=a1+(-c1)
即
b1到a1的一条权值为-c1的边
*/
{
c1=read();
add(b1,a1,-c1);
}
else if(ffff==2)
/*
a1-b1<=c1
变形为
a1<=b1+c1
即
从a1到b1的一条权值为c1的边
*/
{
c1=read();
add(a1,b1,c1);
}
else if(ffff==3)
/*
应为相等
a1<=b1+0
b1<=a1+0
即
a1-b1=0
从a1到b1的一条权值为0的边
从b1到a1的一条权值为0的边
*/
{
add(a1,b1,0);
add(b1,a1,0);
}
}
if(spfa(0))
cout<<"Yes";
else
cout<<"No";
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...