poj 1364-モデリング

問題の意味によってこの問題は<和>の関係ですが、差分制約を使うには>=または<=でなければなりません.
問題は条件が整数であることを示しているので,これがヒントであるので,>cであれば>=c−1であり,同理<である.
これを知って、直接負のループがあるかどうかを判断すればいいので、ソースポイントを1つ追加して、図の連通性を保つことを忘れないでください...
 
 
コード:
 

#include <stdio.h>

#define maxN 205//     ，   s[i]
#define inf 0x7fffffff

struct Edge 
{
	int v, w, next;
}edge[maxN * 30];// 

int edgeNum;//   
int dis[maxN];//      dis[i]     i     
bool vis[maxN];//  i      
int preEdge[maxN];//          
int cnt[maxN];//      
int queue[maxN * 30];//    
int n,m;//   n
char ch[10];

void addEdge(int u, int v, int w)//    
{
	edge[edgeNum].v = v;
	edge[edgeNum].w = w;
	edge[edgeNum].next = preEdge[u];// u        
	preEdge[u] = edgeNum ++;
}

int spfa()//spfa    
{
	int head = 0, tail = 1;

	for (int i = 0; i <= n; ++ i)
	{
		dis[i] = inf;
		vis[i] = false;
		cnt[i] = 0;
	}
	queue[ head] = n + 2;
	dis[n + 2] = 0;
	++ cnt[n + 2];
	while (head < tail)
	{
		int u = queue[head];
		int p = preEdge[u];
		vis[u] = true;
		while (p != -1)
		{
			int v = edge[p].v, w = edge[p].w;
			if (dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
				if (!vis[v])
				{
					vis[v] = true;
					queue[tail] = v;
					tail ++;
					if(++cnt[v] > n )
					{
						return 1;
					}

				}


			}
			p = edge[p].next;
		}
		head ++;
		vis[u] = false;
	}
	return 0;
}

void buildGraph()//           ，  。。。。
{
	edgeNum = 0;
	for (int i = 0; i <= n + 2; ++ i)
	{
		preEdge[i] = -1;
	}
	scanf("%d", &m);
	
	for (int i = 0; i < m; ++ i)
	{
		int u, v, w;
		scanf("%d %d %s %d", &u, &v, ch, &w);
		if (ch[0] == 'g')
		{
			addEdge(u + v, u - 1, - w - 1);
		}
		else
			addEdge(u - 1, u + v, - 1 + w);
	}
	for (int i = 1; i <= n; ++ i)
	{
		addEdge(n + 2, i, 0);
	}
	
}

int main()//   
{
	while (scanf("%d", &n) != EOF && n)
	{
		buildGraph();
		if (spfa())
		{
			printf("successful conspiracy
");
		}
		else
			printf("lamentable kingdom
");
	}
	return 0;
}