2 条题解

  • 0
    @ 2025-10-8 16:51:57

    题目只求是否有合法方案,那么 最短路模型 和 最长路模型 都可以。 这里选择最短路模型。 约束条件的推导: 设s[i]表示从1~i这个区间内有多少个点 那么每个约束条件可以表示为 s[ai+bi]-s[ai-1]>ci(gt) -> ci++ -> s[ai+bi]-s[ai-1]>=ci(gt) -> s[ai+bi]-ci >=s[ai-1] -> G[ai+bi].push_back({ai-1,-ci});

    s[ai+bi]-s[ai-1]<ci(lt) -> ci-- -> s[ai+bi]-s[ai-1]<=ci(lt) -> s[ai-1]+ci >=s[ai+bi] -> G[ai-1].push_back({ai+bi,ci});

    #include <bits/stdc++.h>
    using namespace std;
    vector<pair<int, int>> G[110];
    int st, ed, d[110], dd[110]; bool v[110];
    int spfa()
    {
        memset(d, 63, 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] > (ed - st + 1)) return 0;
                    if(v[y] == 0) q.push(y), v[y] = 1;
                }
            }
        }
        return 1;
    }
    int main()
    {
        int n, m;
        while(scanf("%d", &n) && n)
        {
            scanf("%d", &m);
            for(int i = 0; i <= 109; i++) G[i].clear();
            st = 110, ed = 0;
            for(int i = 1, x, y, c; i <= m; i++)
            {
                char ss[10]; scanf("%d%d%s%d", &x, &y, ss, &c); x++; y++;
                if(ss[0] == 'g') G[x + y].push_back({x - 1, -(c + 1)});
                else G[x - 1].push_back({x + y, c - 1});
                ed = max(ed, x + y);
                st = min(st, x - 1);
            }
            
            if(!spfa()) printf("successful conspiracy\n");//不等式组无解,无法得到想要的答案
            else printf("lamentable kingdom\n");//反之则有解 
        }
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:51:42
      /*
      题目只求是否有合法方案,那么 最短路模型 和 最长路模型 都可以。
      这里选择最短路模型。
      约束条件的推导:
      设s[i]表示从1~i这个区间内有多少个点
      那么每个约束条件可以表示为
      s[ai+bi]-s[ai-1]>ci(gt) -> ci++ -> s[ai+bi]-s[ai-1]>=ci(gt) ->
      s[ai+bi]-ci >=s[ai-1] -> G[ai+bi].push_back({ai-1,-ci});
       
      s[ai+bi]-s[ai-1]<ci(lt) -> ci-- -> s[ai+bi]-s[ai-1]<=ci(lt) ->
      s[ai-1]+ci >=s[ai+bi] -> G[ai-1].push_back({ai+bi,ci});
       
      */
      #include<bits/stdc++.h>
      using namespace std;
      vector< pair<int,int> > G[110];
      int st,ed,d[110],dd[110];bool v[110];
      int spfa()
      {
          memset(d,63,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]>(ed-st+1))return 0;
                      if(v[y]==0)q.push(y),v[y]=1;
                  }
              }
          }
          return 1;
      }
      int main()
      {
          int n,m;
          while(scanf("%d",&n) && n)
          {
              scanf("%d",&m);
              for(int i=0;i<=109;i++)G[i].clear();
              st=110,ed=0;
              for(int i=1,x,y,c;i<=m;i++)
              {
                  char ss[10];scanf("%d%d%s%d",&x,&y,ss,&c);x++;y++;
                  if(ss[0]=='g')G[x+y].push_back({x-1,-(c+1)});
                  else          G[x-1].push_back({x+y,c-1});
                  ed=max(ed,x+y);
                  st=min(st,x-1);
              }
              
              if(!spfa())printf("successful conspiracy\n");//不等式组无解,无法得到想要的答案
              else printf("lamentable kingdom\n");//反之则有解 
          }
          return 0;
      }
      • 1

      *【差分约束】判断不等式方程组是否有解

      信息

      ID
      701
      时间
      1000ms
      内存
      128MiB
      难度
      7
      标签
      递交数
      72
      已通过
      15
      上传者