P1260 工程规划 (差分约束)

题目链接

Solution

差分约束.

差分约束似乎精髓就两句话:

当我们把不等式整理成 \(d[a]+w<=d[b]\) 时，我们求最长路。
整理成 \(d[a]+w>=d[b]\) 时，我们求最短路。

所以对于本题的式子 \(Ti-Tj \leq b\) 可以写成: \(T_i-b \leq T_j\).

然后就从 \(i\) 向 \(j\) 连一条 \(-b\) 的边然后跑最长路即可.

按式子可以随便搞.

Code

#include<bits/stdc++.h>

using namespace std;

const int maxn=5008;

struct sj{

    int to,next,w;

}a[maxn];

int kk,inf,n,m,cnt[maxn],flag;

int head[maxn],size;

int v[maxn],dis[maxn];

void add(int x,int y,int z)

{

    a[++size].to=y;

    a[size].next=head[x];

    head[x]=size;

    a[size].w=z;

}

void SPFA(int s)

{

    queue<int>q;

    q.push(s); dis[s]=0;

    while(!q.empty())

    {

        int x=q.front(); q.pop();

        cnt[x]++;

        if(cnt[x]>n){{cout<<"NO SOLUTION"<<endl;exit(0);}}

        for(int i=head[x];i;i=a[i].next)

        {

            int tt=a[i].to;

            if(dis[tt]>dis[x]+a[i].w)

            {

                dis[tt]=dis[x]+a[i].w;

                if(!v[tt])

                q.push(tt),v[tt]=1;

            }

        }

        v[x]=0;

    }

}

int main()

{

    scanf("%d%d",&n,&m);

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

    {

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        add(y,x,z);

    }

    memset(dis,127,sizeof(dis));

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

    {

        if(cnt[i])continue;

        SPFA(i);

    }

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

    kk=min(kk,dis[i]);

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

    printf("%d\n",dis[i]-kk);

}

巴特西

P1260 工程规划 (差分约束)

题目链接

Solution

Code

最新文章

热门文章