差分约束

哇,没搞清楚这个,结果被黄牌题吊打。。。。

差分约束系统是用来解一些特殊的不等式。

就是把每个约束条件建边,然后跑最短路或者最长路。

例如:

   $x_{i}$ $-$ $x_{j}$>=k; 那么就从j向i连一条长度为k的边;跑最长路。

   $x_{i}$ $-$ $x_{j}$<=k; 那么就从j向i连一条长度为k的边;跑最短路。

对于不同的题,跑最短路和最长路是不一样的,要看约束条件。

例题:p1250——种树

这题就是用前缀和列出不等式,然后全部变成$x_{i}$ $-$ $x_{j}$>=k这一类型,然后跑最长路就是最后的答案了。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=30005;
int head[N];
bool used[N];
int dis[N],n,m,tot,x,y,z;
struct node
{
    int next,value,to;
}edge[N*100];
void add(int x,int y,int z)
{
    tot++;
    edge[tot].to=y;
    edge[tot].value=z;
    edge[tot].next=head[x];
    head[x]=tot;
}
void spfa(int x)
{
    memset(dis,-63,sizeof(dis));
    queue<int>Q;
    Q.push(x);
    dis[x]=0;
    while(!Q.empty())
    {
        int y=Q.front();Q.pop();used[y]=0;
        for(int i=head[y];i;i=edge[i].next)
        {
            if(dis[edge[i].to]<dis[y]+edge[i].value)
            {
                dis[edge[i].to]=dis[y]+edge[i].value;
                if(!used[edge[i].to])
                {
                    used[edge[i].to]=1;
                    Q.push(edge[i].to);
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x-1,y,z);
    }
    for(int i=1;i<=n;i++)
    {
        add(i-1,i,0);
        add(i,i-1,-1);
    }
    memset(used,0,sizeof(used));
    spfa(0);
    printf("%d",dis[n]);
    return 0;
}

只要题意可以变成许多个限制条件,然后就可以用差分约束了。 注意一般要用spfa,因为会有负环。

有负环说明这个方程组无解。

顺便说一下,怎么判无解吧.

一个点被入队n次就说明出现负环了。

不要让我这个蒟蒻证明(不会)(逃


发表于 2018-09-26 19:22:37 in 知识点