典型的差分约束系统，可以这样构图：设S(i)表示a[1]+a[2]+…+a[i-1]，那么给出的关系式可以表示成如下形式：S(si+ni+1)-S(si) oi ki。为什么不用S(i)表示前i项和？（我一开始是这么做的，但是样例都过不去），因为这样的话需要S(0)，那约束图中的v0用什么表示呢？
以下是我的代码：
#include<stdio.h>
const long maxn=107;
const long INF=10000007;
struct
{
long u,v,w;
}edge[maxn*3];
long n,m,tot;
const char True[]="lamentable kingdom";
const char False[]="successful conspiracy";
bool bellman_ford()
{
long d[maxn];
for(long i=0;i<=n+1;i++)
d[i]=INF;
d[0]=0;
for(long i=1;i<=n+1;i++)
for(long j=1;j<=tot;j++)
{
long a=edge[j].u,b=edge[j].v,t=edge[j].w;
if(d[a]+t<d[b])
d[b]=d[a]+t;
}
for(long i=1;i<=tot;i++)
{
long a=edge[i].u,b=edge[i].v,t=edge[i].w;
if(d[a]+t<d[b])
return false;
}
return true;
}
int main()
{
while(scanf("%ld",&n)==1)
{
if(n==0) break;
tot=0;
scanf("%ld",&m);
for(long i=1;i<=m;i++)
{
long a,b,t;
char cmd[7];
scanf("%ld %ld %s %ld",&a,&b,cmd,&t);
tot++;
switch(cmd[0])
{
case 'g':
edge[tot].u=a+b+1;
edge[tot].v=a;
edge[tot].w=-t-1;
break;
case 'l':
edge[tot].u=a;
edge[tot].v=a+b+1;
edge[tot].w=t-1;
}
}
for(long i=1;i<=n+1;i++)
{
tot++;
edge[tot].u=0;
edge[tot].v=i;
edge[tot].w=0;
}
if(bellman_ford())
puts(True);
else puts(False);
}
return 0;
}
posted on 2010-02-21 15:57
lee1r 阅读(332)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数学/数论