UVA 515 差分约束 SPFA判负

第一次看这个题目，完全不知道怎么做，看起来又像是可以建个图进行搜索，但题目条件就给了你几个不等式，这是怎么个做法。。。之后google了下才知道还有个差分约束这样的东西，能够把不等式化成图，要求某个点在满足所有不等式的情况下的最大取值，只需对建好的图进行一次最短路即可

不过要使得a b 点满足这样 a<=b+k这种不等式，还得对题目所给的不等式进行下改装

原不等式无非就是输入个 si ni,使得存在 A(si)+...A(si+ni)<k 或者 >k，我们新定义一个s[],s[i]代表从1 到 i的所有的点的和，这样，原不等式就会变成 s[si+ni]-s[si-1]>=k+1 或者小于=k-1，进行下移项，即可变成差分约束不等式的形式，这样每个点的含义就是对应的s[i]。

此外注意添加一个超级原点 N+1，跟所有点进行下连通，保证图的连通性。

其实题目还有个难点就是，他求是否能满足着m个不等式，如果不满足，意味着有相互冲突的不等式，也就是某个点值既可能正也可能负，也就是说图上存在负环。。。。这个转换确实比较难推敲，尤其是像我这种对图论题目还只是入门的菜鸟。

因此，建好图后，只需用SPFA遍历一下，判断有无负环即可。

此外，还有个疑惑，就是差分约束一定要有等于吗？就像上面的式子，如果不是为了满足=的条件，就不必用k+1和k-1来代替原来的k了。。。这个还有待考证

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#define N 250

using namespace std;

int u[N],v[N],w[N],nt[N],ft[N/],d[N/],num[N/],vis[N/];

int n,m,cnt,flag;

void addedge(int a,int b,int c)

{

    u[cnt]=a;

    v[cnt]=b;

    w[cnt]=c;

    nt[cnt]=ft[a];

    ft[a]=cnt++;

}

void spfa()

{

    int i,j;

    for (i=;i<=n;i++)

        d[i]=<<;

    memset(num,,sizeof num);

    memset(vis,,sizeof vis);

    flag=;

    d[n+]=;

    queue <int> q;

    q.push(n+);

    vis[n+]=;

    while (!q.empty())

    {

        int x=q.front();

        q.pop();

        vis[x]=;

        num[x]++;

        if (num[x]>n)

        {

            flag=;

            return;

        }

        for (i=ft[x];i>=;i=nt[i])

        {

            int nx=v[i];

            if (d[nx]>d[x]+w[i])

            {

                d[nx]=d[x]+w[i];

                if (!vis[nx])

                {

                    q.push(nx);

                    vis[nx]=;

                }

            }

        }

    }

}

int main()

{

    int i,j;

    char ch[];

    while (scanf("%d",&n))

    {

        if (!n) break;

        cnt=;

        scanf("%d",&m);

        int a,b,k,si,ni;

        memset(ft,-,sizeof ft);

        for (i=;i<=m;i++)

        {

            scanf("%d%d%s%d",&si,&ni,ch,&k);

            if (ch[]=='g')

            {

                addedge(si+ni,si-,(-k-));//用差分约束不等式建图，下同

            }

            else

            {

                addedge(si-,si+ni,k-);

            }

        }

        for (i=;i<=n;i++) //将n+1作为超级原点进行连通。

            addedge(n+,i,);

        spfa();

        if (flag)

        {

            puts("lamentable kingdom");

        }

        else puts("successful conspiracy");

    }

    return ;

}

巴特西

UVA 515 差分约束 SPFA判负

最新文章

热门文章