本文主要是介绍poj 1364 King，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
查分约束，题目的条件a[i]+a[i+1]+...a[i+n]<k,那么可以假设a[1]+a[2]+....a[n]=sum[n];那么a[i]+a[i+1]+...a[i+n]=sum[i+n]-sum[i-1]<=k-1(因为都是整数),然后就构成了一个查分约束系统，在用Bellman_ford 去求单源最短路径，只要不存在负权环那么必定有解。。。yxl,fighting。。。
#include<stdio.h>
int n,m,a,b,c;
int map[110][3];
int dist[110];
char s[3];
bool bellman_ford()
{
for(int i=0;i<=n;i++)
dist[i]=99999999;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(dist[map[j][0]]>dist[map[j][1]]+map[j][2])
dist[map[j][0]]=dist[map[j][1]]+map[j][2];
}
for(int j=0;j<m;j++)
{
if(dist[map[j][0]]>dist[map[j][1]]+map[j][2])
return false;
}
return true;
}
int main()
{
while(scanf("%d",&n)&&n)
{
scanf("%d",&m);
for(int i=0;i<m;i++)
{
scanf("%d%d%s%d",&a,&b,s,&c);
if(s[0]=='g')
{
map[i][0]=a-1;
map[i][1]=a+b;
map[i][2]=-c-1;
}
else
{
map[i][0]=a+b;
map[i][0]=a-1;
map[i][2]=c-1;
}
}
if(bellman_ford())
printf("lamentable kingdom\n");
else
printf("successful conspiracy\n");
}
return 0;
}这篇关于poj 1364 King的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
