大离谱,新手求教
查看原帖
大离谱,新手求教
136889
wweiyi楼主2021/10/5 20:27

为啥这个代码我标星号的那一行加了那个操作就直接把 Test 6 过掉了啊

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#define int long long
using namespace std;
const int maxn=300005;
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
		f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
struct edge{
	int e,next,val;
}ed[maxn<<1];
int en,first[maxn];
void add_edge(int s,int e,int val)
{
	en++;
	ed[en].next=first[s];
	first[s]=en;
	ed[en].e=e;
	ed[en].val=val;
}
int n,k;
int d[maxn],num[maxn];
bool vis[maxn];
queue <int> q;
bool spfa(int s)
{
	d[s]=0;
	vis[s]=true;
	q.push(s);
	num[s]++;
	while(q.size())
	{
		int x=q.front();
		q.pop();
		vis[x]=false;
		for(int i=first[x];i;i=ed[i].next)
		{
			int e=ed[i].e;
			int val=ed[i].val;
			if(d[e]<d[x]+val)
			{
				
				d[e]=d[x]+val;
				if(!vis[e])
				{
					vis[e]=true;
					q.push(e);
					num[e]++;
					if(num[e]==n+1) return false;
				}
			}
		}
	}
	return true;
}
signed main()
{
	memset(d,-0x3f3f3f,sizeof(d));
	n=read(),k=read();
	for(int i=1;i<=k;i++)
	{
		int x=read(),a=read(),b=read();
		if(x==1)
		{
			add_edge(b,a,0);//a<=b
			add_edge(a,b,0);//a>=b;
		}
		else if(x==2)
		{
			if(a==b)
			{
				cout<<-1<<'\n';
				return 0;
			}
			add_edge(a,b,1);//a<b
		}
		else if(x==3)
		{
			add_edge(b,a,0);//a>=b
		}
		else if(x==4)
		{
			if(a==b)
			{
				cout<<-1<<'\n';
				return 0;
			}
			add_edge(b,a,1);//a>b
		}
		else if(x==5)
		{
			add_edge(a,b,0);//a<=b
		}
	}
	for(int i=1;i<=n;i++)
	add_edge(0,i,1),q.push(i);//*********q.push(i)加之前是TLE on test 6,这是为啥啊 
	if(!spfa(0))
	{
		cout<<-1<<'\n';
		return 0;
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	ans+=d[i];
	cout<<ans<<'\n';
	return 0;
}
2021/10/5 20:27
加载中...