题目分析

题意理解

基于提供的代码，我们可以分析出这是一道关于差分约束系统的题目。题目要求判断是否存在满足一系列约束条件的解。

输入格式

• 第一行输入测试用例数量 $t$
• 每个测试用例：
  • 第一行两个整数 $n$ 和 $m$，表示有 $n$ 个变量和 $m$ 个约束条件
  • 接下来 $m$ 行，每行描述一个约束条件，格式为：$x$ $y$ $z$，其中 $y$ 是一个字符串表示约束类型

约束条件类型

代码中处理了多种约束类型，每种类型对应不同的不等式关系：

1. $NE$ (North East):

   • 添加两条边：$x \rightarrow z$ (权重 $1$)
   • 对应不等式：$x + 1 \leq z$

2. $NW$ (North West):

   • 添加两条边：$z \rightarrow x$ (权重 $1$) 和 $x \rightarrow z$ (权重 $1$)
   • 对应不等式：$z + 1 \leq x$ 和 $x + 1 \leq z$

3. $N$ (North):

   • 添加三条边：$x \rightarrow z$ (权重 $0$), $z \rightarrow x$ (权重 $0$), $x \rightarrow z$ (权重 $1$)
   • 对应不等式：$x \leq z$, $z \leq x$, 和 $x + 1 \leq z$

4. $SE$ (South East):

   • 添加两条边：$x \rightarrow z$ (权重 $1$) 和 $z \rightarrow x$ (权重 $1$)
   • 对应不等式：$x + 1 \leq z$ 和 $z + 1 \leq x$

5. $SW$ (South West):

   • 添加两条边：$z \rightarrow x$ (权重 $1$) 和 $z \rightarrow x$ (权重 $1$)
   • 对应不等式：$z + 1 \leq x$ (重复)

6. $S$ (South):

   • 添加三条边：$x \rightarrow z$ (权重 $0$), $z \rightarrow x$ (权重 $0$), $z \rightarrow x$ (权重 $1$)
   • 对应不等式：$x \leq z$, $z \leq x$, 和 $z + 1 \leq x$

7. $E$ (East):

   • 添加三条边：$x \rightarrow z$ (权重 $1$), $x \rightarrow z$ (权重 $0$), $z \rightarrow x$ (权重 $0$)
   • 对应不等式：$x + 1 \leq z$, $x \leq z$, 和 $z \leq x$

8. $W$ (West):

   • 添加三条边：$z \rightarrow x$ (权重 $1$), $x \rightarrow z$ (权重 $0$), $z \rightarrow x$ (权重 $0$)
   • 对应不等式：$z + 1 \leq x$, $x \leq z$, 和 $z \leq x$

解题方法

差分约束系统

题目使用差分约束系统来建模，通过构建有向图并检测负权环来判断是否存在可行解。

1. 图构建：

   • 使用两个图（$k=0$ 和 $k=1$）来分别处理不同的约束条件
   • 为每个变量 $i$ 添加从超级源点 $0$ 出发的边，初始权重为 $0$

2. $SPFA$算法：

   • 使用$SPFA$算法检测图中是否存在负权环
   • 如果两个图都不存在负权环，则输出"$POSSIBLE$"，否则输出"$IMPOSSIBLE$"

3. 松弛操作：

   • 对于每个约束条件，转换为相应的边添加到图中
   • 在$SPFA$中执行松弛操作，更新最短路径估计

复杂度分析

• 时间复杂度：$O(t \cdot (n + m) \cdot k)$，其中 $k$ 是$SPFA$的平均运行时间
• 空间复杂度：$O(n + m)$，用于存储图结构

标准代码

#include<queue>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 10000001
#define esp 1
int n,m;
int head[2][30015],v[2][30015],next[2][30015];
double w[2][30015];
double dis[1005];
int input[1505],output[1505];
int cnt[2];
void add(int k,int a,int b,double c)
{
    v[k][cnt[k]]=b;
    w[k][cnt[k]]=c;
    next[k][cnt[k]]=head[k][a];
    head[k][a]=cnt[k]++;
}
bool spfa(int k)
{
    for(int i=1;i<=n;i++) dis[i]=-INF;
    memset(input,0,sizeof(input));
    memset(output,0,sizeof(output));
    queue<int> q;
    q.push(0);
    dis[0]=0;
    input[0]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        input[u]=0;
        output[u]++;
        if(output[u]>n) return 0;
        for(int i=head[k][u];i!=-1;i=next[k][i])
            if(dis[v[k][i]]<dis[u]+w[k][i])
            {
                dis[v[k][i]]=dis[u]+w[k][i];
                if(!input[v[k][i]])
                {
                    q.push(v[k][i]);
                    input[v[k][i]]=1;
                }
            }
    }
    return 1;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(head,-1,sizeof(head));
        memset(cnt,0,sizeof(cnt));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            add(0,0,i,0);
            add(1,0,i,0);
        }
        for(int i=0;i<m;i++)
        {
            int x,z;
            char y[10];
            scanf("%d%s%d",&x,y,&z);
            if(y[0]=='N'&&y[1]=='E')
            {
                add(0,x,z,esp);
                add(1,x,z,esp);
                continue;
            }
            if(y[0]=='N'&&y[1]=='W')
            {
                add(0,z,x,esp);
                add(1,x,z,esp);
                continue;
            }
            if(y[0]=='N'&&y[1]=='\0')
            {
                add(0,x,z,0);
                add(0,z,x,0);
                add(1,x,z,esp);
                continue;
            }
            if(y[0]=='S'&&y[1]=='E')
            {
                add(0,x,z,esp);
                add(1,z,x,esp);
                continue;
            }
            if(y[0]=='S'&&y[1]=='W')
            {
                add(0,z,x,esp);
                add(1,z,x,esp);
                continue;
            }
            if(y[0]=='S'&&y[1]=='\0')
            {
                add(0,x,z,0);
                add(0,z,x,0);
                add(1,z,x,esp);
                continue;
            }
            if(y[0]=='E')
            {
                add(0,x,z,esp);
                add(1,x,z,0);
                add(1,z,x,0);
                continue;
            }
            if(y[0]=='W')
            {
                add(0,z,x,esp);
                add(1,x,z,0);
                add(1,z,x,0);
                continue;
            }
        }
        if(spfa(0)&&spfa(1)) cout<<"POSSIBLE"<<endl;
        else cout<<"IMPOSSIBLE"<<endl;
    }
    return 0;
}