1 条题解

  • 0
    @ 2025-10-8 16:51:43
    /*
    判断是否有合法解,最短路和最长路都行,这里采用最长路
    P a b c:
    s[ b ]-s[ a ]<=c -> s[ b ]-c<=s[a] - > G[ b ].push_back({a,-c});
    s[ b ]-s[ a ]>=c -> s[ a ]+c<=s[ b ] -> G[a].push_back({b,c});
    
    V a b:
    s[ b ]-s[ a ]>=1 -> s[ a ]+1<=s[ b ] -> G[a].push_back({b,1})。
    */
    #include<bits/stdc++.h>
    using namespace std;
    constexpr int N=1010;
    vector< pair<int,int> > G[N];
    int n,st,ed,d[N],dd[N];bool v[N];
    int spfa()
    {
        memset(d,0,sizeof(d));memset(dd,0,sizeof(dd));
        memset(v,0,sizeof(v));
        queue<int>q;
        for(int i=st;i<=ed;i++)q.push(i),v[i]=1;
        d[st]=0;
        while(!q.empty())
        {
            int x=q.front(); q.pop();v[x]=0;
            for(auto i:G[x])
            {
                int y=i.first,w=i.second;
                if(d[y]<d[x]+w)
                {
                    d[y]=d[x]+w;
                    dd[y]=dd[x]+1;if(dd[y]>n)return 0;
                    if(v[y]==0) q.push(y),v[y]=1;
                }
            }
        }
        return 1;
    }
    int main()
    {
        int m;
        while(scanf("%d",&n) && n)
        {
            scanf("%d",&m);
            memset(G ,0,sizeof(G));
            st=n+1;ed=0;
            for(int i=1,a,b,c;i<=m;i++)
            {
                char op[5];scanf("%s%d%d",op,&a,&b);
                if(op[0]=='P')
                {
                    scanf("%d",&c);
                    G[ b ].push_back({a,-c});
                    G[a].push_back({b,c});
                }
                else G[a].push_back({b,1});
                st=min(st,min(a,b));
                ed=max(ed,max(a,b));
            }
            
            if( !spfa() ) printf("Reliable\n"); 
            else  printf("Unreliable\n");
        }
        return 0;
    }
    • 1

    *【差分约束】判断约束系统是否有解

    信息

    ID
    702
    时间
    1000ms
    内存
    128MiB
    难度
    9
    标签
    递交数
    94
    已通过
    9
    上传者