POJ 2983 Is the Information Reliable? 依旧差分约束

题目大意：

星际大战开始了。你购买了情报，需要判断它的准确性。已知地方的根据地在由南向北排成一条直线。P A B X，表示A在B北面距离X光年的地方，另一种是V A B，表示只知道A在B的北面至少1光年的地方。

思路：

可转化为差分约束。

对于P A B X来说因为A-B=X (因为他们相距X光年，我们取北边为正方向）可以记做： A-B >=X && A-B<=X，即A-B>=X && B-A>=-X

对于V A B ，可以记做 A-B>=1

然后老样子差分约束。记得建立一个连接所有顶点的超级顶点来保证图的连通性~

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int MAXN=1000+10;

const int MAXM=200000+1000;

const int INF=-9999999;

struct edge

{

	int to;

	int val;

	int next;

}e[MAXM];

int head[MAXN],dis[MAXN],len,n,m;

void add(int from,int to,int val)

{

	e[len].to=to;

	e[len].val=val;

	e[len].next=head[from];

	head[from]=len++;

}

bool spfa()

{

	int start=n+1;

	for(int i=1;i<=n;i++)

		dis[i]=INF;

	bool vis[MAXN]={0};

	int cnt[MAXN]={0};

	deque<int> q;

	q.push_back(start);

	vis[start]=1;

	cnt[start]=1;

	dis[start]=0;

	while(!q.empty())

	{

		int cur=q.front();

		q.pop_front();

		vis[cur]=false;

		for(int i=head[cur];i!=-1;i=e[i].next)

		{

			int id=e[i].to;

			if(dis[id] < dis[cur] + e[i].val)

			{

				dis[id]=dis[cur] + e[i].val;

				if(!vis[id])

				{

					if(++cnt[id] > n)

						return true;

					vis[id]=true;

					if(!q.empty() && dis[id] > dis[q.front()])

						q.push_back(id);

					else

						q.push_front(id);

				}

			}

		}

	}

	return false;

}

int main()

{

	while(~scanf("%d%d",&n,&m))

	{

		memset(head,-1,sizeof(head));

		len=0;

		for(int i=0;i<m;i++)

		{

			char cmd[5];

			int from,to,val;

			scanf("%s",cmd);

			if(cmd[0]=='P')

			{

				scanf("%d%d%d",&from,&to,&val);

				add(from,to,-val);

				add(to,from,val);

			}

			else

			{

				scanf("%d%d",&from,&to);

				add(to,from,1);

			}

		}

		for(int i=1;i<=n;i++)

			add(n+1,i,0);

		if(spfa())

			puts("Unreliable");

		else

			puts("Reliable");

	}

	return 0;

}

巴特西

POJ 2983 Is the Information Reliable? 依旧差分约束

最新文章

热门文章