现在的位置: 首页 > 综合 > 正文

King 差分约束系统

2013年04月20日 ⁄ 综合 ⁄ 共 747字 ⁄ 字号 评论关闭
/*注意将所有的不等式全都转化成<=的形式,如<1变为<=0.
注意建模。即构造不等关系。然后将两端点反向存图。接着就上bellman,果断1A。*/
#include <stdio.h>
#include <cstring>
#define maxn 101
struct edge
{
    int u,v,val;
} e[maxn];
int dis[maxn];
int n,m;
bool bellman(int s)
{
    memset(dis,0x7f,sizeof(dis));
    dis[0]=0;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            if(dis[e[j].u]+e[j].val<dis[e[j].v])
                dis[e[j].v]=dis[e[j].u]+e[j].val;
    for(int j=0; j<m; j++)
        if(dis[e[j].u]+e[j].val<dis[e[j].v]) return false;
    return true;
}
int main()
{
    while(scanf("%d",&n)==1)
    {
        if(n==0) break;
        scanf("%d",&m);
        char op[3];
        int si,ni,ki;
        for(int i=0; i<m; i++)
        {
            scanf("%d %d %s %d",&si,&ni,op,&ki);
            if(op[0]=='l')
            {
                e[i].u=si-1;
                e[i].v=si+ni;
                e[i].val=ki-1;
            }
            else
            {
                e[i].u=si+ni;
                e[i].v=si-1;
                e[i].val=-ki-1;
            }
        }
        if(bellman(0)) printf("lamentable kingdom\n");
        else printf("successful conspiracy\n");
    }
    return 0;
}
 


抱歉!评论已关闭.