POJ 1364 King (UVA 515) 差分约束

http://poj.org/problem?id=1364

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=456

题目大意：

有一串序列，A={a1,a2,……an};

然后给你一些信息，判断是否有解

4 2

1 2 gt 0 表示a1+a2+a3>0

2 2 lt 2 表示 a2+a3+a4<2

思路：

还是差分约束，不过值得注意的是我们要把小于号和大于号改为<=和>=

也就是说a1+a2+a3>=1 a2+a3+a4<=2

设S[I]为前i项和，如果为大于号有

S[ to + from] - s[from -1]>=val+1

小于号有：

s[to+from] - s[from - 1]<= val -1

变形得：

s[from - 1] -s[to+from]>=1-val

然后把n+1作为附加点，保证图的连通性。

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int MAXN=100+10;

const int MAXM=100+10;

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()

{

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

		dis[i]=INF;

	int start=n+1;

	queue<int> q;

	bool vis[MAXN]={0};

	int cnt[MAXN]={0};

	q.push(start);

	vis[start]=1;

	cnt[start]=1;

	dis[start]=0;

	while(!q.empty())

	{

		int cur= q.front();

		q.pop();

		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])

				{

					cnt[id]++;

					if(cnt[cur]>n)

						return true;

					vis[id]=true;

					q.push(id);

				}

			}

		}

	}

	return false;

}

int main()

{

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

	{

		len=0;

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

		scanf("%d",&m);

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

		{

			int from,to,val;

			char cmd[5];

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

			if(strcmp(cmd,"gt")==0)

				add(from-1,to+from,val+1);

			else

				add(to+from,from-1,-val+1);

		}

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

			add(n+1,i,0);

		if(spfa())

			puts("successful conspiracy");

		else

			puts("lamentable kingdom");

	}

	return 0;

}

巴特西

POJ 1364 King (UVA 515) 差分约束

最新文章

热门文章