poj1364,2983-差分约束系统

 poj1364

题目大意:现在假设有一个这样的序列，S={a1，a2，a3，a4...ai...at}
其中ai=a*si,其实这句可以忽略不看
现在给出一个不等式，使得ai+a(i+1)+a(i+2)+...+a(i+n)<ki或者是ai+a(i+1)+a(i+2)+...+a(i+n)>ki
首先给出两个数分别代表S序列有多少个，有多少个不等式
不等式可以这样描述
给出四个参数第一个数i可以代表序列的第几项，然后给出n，这样前面两个数就可以描述为ai+a(i+1)+...a(i+n)，即从i到n的连续和，再给出一个符号和一个ki
当符号为gt代表‘>’,符号为lt代表‘<'
那么样例可以表示
1 2 gt 0
a1+a2+a3>0
2 2 lt 2
a2+a3+a4<2
最后问你所有不等式是否都满足条件，若满足输出lamentable kingdom，不满足输出successful conspiracy，这里要注意了，不要搞反了

 

要注意的一点是差分约束系统的条件是 小于等于。因此样例可以得到如下不等式

s3-s0<0    ----  s3-s0<=-1   (si 表示a1+a2+..ai)

 

#include<iostream>
#include<queue>
using namespace std;
#define MAXSIZE 150
#define INF 9999999
struct node{
	int u;
	int v;
	int c;
};
struct node edges[MAXSIZE];
int head[MAXSIZE];
int next[MAXSIZE];
int vis[MAXSIZE];
int dis[MAXSIZE];
int num;
int n,m;
int c[MAXSIZE];
queue<int>que;
void addnode(int u,int v,int c)
{

	edges[num].u=u;
	edges[num].v=v;
	edges[num].c=c;
	next[num]=head[u];
	head[u]=num++;
}
int spfa(int s)
{
	int i;
	while(!que.empty())
	{
		que.pop();
	}
	memset(vis,0,sizeof(vis));
	memset(c,0,sizeof(c));
	for(i=0;i<=n;i++)
		dis[i]=INF;
	dis[s]=0;
	vis[s]=1;
	c[s]++;
	que.push(s);
	while(!que.empty())
	{
		int from=que.front();
		que.pop();
		vis[from]=0;
		for(i=head[from];i!=-1;i=next[i])
		{
			int to=edges[i].v;
			if(dis[to]>dis[from]+edges[i].c)
			{
				dis[to]=dis[from]+edges[i].c;
				c[to]++;
				if(c[to]>=n+1)
				{
					return 0;
				}
				if(!vis[to])
				{
					vis[to]=1;
					que.push(to); 
				}
			}
		}
	}
	return 1;
}
int main()
{
	//freopen("in.txt","r",stdin);
	while(1)
	{
		scanf("%d",&n);
		if(!n)
			break;
		scanf("%d",&m);
		memset(head,-1,sizeof(head));
		memset(next,-1,sizeof(next));
		num=0;
		while(m--)
		{
			int a,b,k;
			char s[10];
			scanf("%d%d%s%d",&a,&b,s,&k);
			int s1=a-1;
			int s2=a+b;
			if(s[0]=='g')//>
			{
				addnode(s2,s1,-k-1);//这里是-(k-1)
			}
			else 
			{
				addnode(s1,s2,k-1);
			}
		}
		
		int flag=1;
		for(int i=0;i<=n;i++)
			if(!spfa(i))
			{
				flag=0;
				break;
			}
			if(!flag)
				printf("successful conspiracy\n");
			else
				printf("lamentable kingdom\n");
	}
	return 0;
}

 

 

poj2983

#include<iostream>
#include<queue>
using namespace std;
#define EMAX 201010
#define NMAX 1010
#define INF 900000
#define MIN(x,y) (((x)<(y))?(x):(y))
#define MAX(x,y) (((x)>(y))?(x):(y))
int s,e;
int n,m;
int num;
queue<int>que;
struct node
{
	int u;
	int v;
	int c;
};
node edge[EMAX];
int head[EMAX];
int next[EMAX];
int vis[NMAX];
int cans[NMAX];
int dis[NMAX];

void addnode(int u,int v,int c)
{
	edge[num].u=u;
	edge[num].v=v;
	edge[num].c=c;
	next[num]=head[u];
	head[u]=num++;
}

int spfa(int start)
{
	int i;
	while(!que.empty())
	{
		que.pop();
	}
	memset(vis,0,sizeof(vis));
	memset(cans,0,sizeof(cans));
	for(i=s;i<e+1;i++)
	{
		dis[i]=INF;
	}
	dis[start]=0;
	vis[start]=1;
	que.push(start);
	cans[start]++;
	while(!que.empty())
	{
		int from=que.front();
		que.pop();
		vis[from]=0;
		for(i=head[from];i!=-1;i=next[i])
		{
			int to=edge[i].v;
			if(dis[to]>dis[from]+edge[i].c)
			{
				dis[to]=dis[from]+edge[i].c;
				if(!vis[to])
				{
					vis[to]=1;
					que.push(to);
					cans[to]++;
					if(cans[to]>n)
						return 0;
				}
			}
		}
	}
	return 1;
}


int main()
{
//	freopen("in.txt","r",stdin);

	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(head,-1,sizeof(head));
		memset(next,-1,sizeof(next));
		
		num=0;
		s=INF;
		e=-INF;
		while(m--)
		{
			char ct;
			int a,b,c;
			//scanf("%c",&ct);
			cin>>ct;
			if(ct=='P')
			{
				scanf("%d%d%d",&a,&b,&c);
				addnode(a,b,c);
				addnode(b,a,-c);
				
				s=MIN(s,a);
				e=MAX(e,b);
			}
			if(ct=='V')
			{
				scanf("%d%d",&a,&b);
				addnode(b,a,-1);
				s=MIN(s,a);
				e=MAX(e,b);
			}
		}
		for (int i =1; i <= n; i++)
			addnode(0, i, 0);
		

		int flag=1;
		if(!spfa(0))
			flag=0;
		if(flag)
			printf("Reliable\n");
		else
			printf("Unreliable\n");

		
			
	}
	return 0;
}
/*
差分约束系统，对于bellman和spfa来说，解差分的不同在于，
对于不连通图bellman能直接处理，而spfa不能，
需要加入超级源（一个到所有点都有一条长度为0的边的点），
并把超级源作为起点，才能保证在扩展过程中到达每个点。
(也可从每个点调用一次spfa来判断是否存在负权环，但这里此题会超时)
否则差分约束系统的部分内容就不会被检测到。
当然也不是所有题遇到这种不连通的情况都可以使用超级源。
因为这种超级源相当于把不同的连通分支在数轴上的起点都平移到了原点。
如题目有特殊要求，则可以对不同的连通分支分别做单独处理。
*/