社区讨论

吸氧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 条回复,欢迎继续交流。

正在加载回复...