[poj 1364]King[差分约束详解(续篇)][超级源点][SPFA][Bellman-Ford]

迈不过友情╰ 2021-12-14 00:45 207阅读 0赞

# 题意 #

有n个数的序列, 下标为\[1.. N \], 限制条件为: 下标从 si 到 si+ni 的项求和 < 或 > ki. 一共有m个限制条件. 问是否存在满足条件的序列.

# 思路 #

转化为差分约束, 就是

即 Si 为第 i 项的前缀和, 特别的 So 为0. 转化不等式(连续子段和变为前缀和之差 > < 变为 >= <= ),求最短路, 判断有没有负权回路.

# 注意 #

由于并不知道图是否连通

(不像是之前的那道Candies图一定是联通的,选择班长所代表的点即可)

所以正常情况下是要另设一个"超级源点", 连接图上的每个点, 从这个点出发就一定可以遍历到每一个点.

"超级源点"到每个点的边权是任意的,而它自己的点权自然是0.

这样的话,就求出了一组满足每对点的差尽可能大, 并且其中的d\[0\] = 0的解.

> 1. 将所有点(包括"超级源点")同时平移, 均为满足所有约束的可行解(包括新加入的边权们)
> 
> 2. 将原图中的所有点同时平移, 得到所有满足原有约束的可行解. 但是仍有d\[0\] = 0的此时, 与超级源点的这些约束有可能不满足. 但是显然这是无所谓的.
> 
> 3. 由此可知, 超级源点的作用就在于确保图的连通性,使得每一个点都有一个"距离". 而"超级源点"带来的额外约束一是d\[0\] = 0, 二是新加的边权. 二者影响的都是d\[1\]到d\[n\]的浮动情况(d\[0\]是参考零点, 额外的边权约束则是起到了限制d\[1\]到d\[n\]与d\[0\]的距离的作用,一堆不等式同样是选择了限制最严的那些并且距离尽可能大....没有实际意义...)

总之参考零点就是这样~

但是用SPFA只是判断负环的话,只需要初始时将所有点入队(而非只将源点入队), 然后判断每个点的入队次数. 如果超过点的总数, 说明存在负环.否则不存在.

数值上是从INF开始减, 有负环的话就会一直减... 没有的话就会正常退出, 当然这个时候d\[ \] 值会很大..

SFPA + stack

//132K 16MS
    #include <cstdio>
    #include <cstring>
    #include <stack>
    using namespace std;
    const int MAXN = 105;
    const int MAXE = 105;
    const int INF = 0x3f3f3f3f;
    struct pool
    {
        int v,pre,w;
    } p[MAXE];
    int num,head[MAXN],d[MAXN],n,m,enq[MAXN];
    bool inq[MAXN];
    stack<int> s;
    void clear()
    {
        while(!s.empty())   s.pop();
        memset(head,0,sizeof(head));
        memset(d,0x3f,sizeof(d));
        memset(inq,false,sizeof(inq));
        memset(enq,0,sizeof(enq));
        num = 0;
    }
    
    bool SPFA()
    {
        for(int i=0;i<=n;i++)
        {
            s.push(i);
            inq[i] = true;
            enq[i]++;
        }
        d[0] = 0;
        while(!s.empty())
        {
            int u = s.top();
            s.pop();
            inq[u] = false;
            for(int tmp=head[u],v;v=p[tmp].v,tmp;tmp=p[tmp].pre)
            {
                int w = p[tmp].w;
                if(d[v]>d[u]+w)
                {
                    d[v] = d[u] + w;
                    if(!inq[v])
                    {
                        inq[v] = true;
                        enq[v]++;
                        if(enq[v]>n+1)    return false;
                        s.push(v);
                    }
                }
            }
        }
        return true;
    }
    
    void add(int u, int v ,int w)
    {
        p[++num].v = v;
        p[num].w = w;
        p[num].pre = head[u];
        head[u] = num;
    }
    
    int main()
    {
        while(scanf("%d",&n)==1 && n)
        {
            clear();
            scanf("%d",&m);
            while(m--)
            {
                int si,ni,ki;
                char o,p;
                scanf("%d %d %c%c %d",&si,&ni,&o,&p,&ki);
                if(o=='g')  add(si+ni,si-1,-ki-1);
                else        add(si-1,si+ni,ki-1);
            }
            printf(SPFA()?"lamentable kingdom\n":"successful conspiracy\n");
        }
    }

用Bellman-Ford也可以.这个时候就要用到超级源点啦

//120K 0MS
    #include <cstdio>
    #include <cstring>
    using namespace std;
    const int MAXN = 105;
    const int MAXE = 210;
    const int INF = 0x3f3f3f3f;
    int s[MAXE],e[MAXE],w[MAXE];
    int num,d[MAXN],n,m;
    
    void clear()
    {
        memset(d,0x3f,sizeof(d));
        num = 0;
    }
    
    bool Bellman_Ford()
    {
        d[n+1] = 0;
        for(int i=0;i<=n+1;i++)
        {
            for(int j=1;j<=num;j++)
            {
                if(d[e[j]]>d[s[j]]+w[j])    d[e[j]] = d[s[j]] + w[j];
            }
        }
        for(int j=1;j<=num;j++)
        {
            if(d[e[j]]>d[s[j]]+w[j])    return false;
        }
        return true;
    }
    
    void add(int u, int v ,int c)
    {
        s[++num] = u;
        e[num] = v;
        w[num] = c;
    }
    
    int main()
    {
        while(scanf("%d",&n)==1 && n)
        {
            clear();
            scanf("%d",&m);
            while(m--)
            {
                int si,ni,ki;
                char o,p;
                scanf("%d %d %c%c %d",&si,&ni,&o,&p,&ki);
                if(o=='g')  add(si+ni,si-1,-ki-1);
                else        add(si-1,si+ni,ki-1);
            }
            for(int i=0;i<=n;i++)
            {
                add(n+1,i,0);
            }
            printf(Bellman_Ford()?"lamentable kingdom\n":"successful conspiracy\n");
        }
    }

转载于:https://www.cnblogs.com/james1207/p/3279972.html