题解 P4878 【[USACO05DEC]layout布局】

· · 题解

这是我们学校的小网管上传的题,我居然来写题解了QWQ

很显然,这是一道差分约束的裸题,瞎搞一下跑个最短路就可以了,但是丧心病狂的小网管出了三个DB数据,你还得去从0开始跑spfa判断图是不是联通的,然后就A了QAQ

差分约束

这玩意主要就是给你几个不等式,让你求一个东西的范围,

x_2-x_1\leq a_1 x_3-x_2\leq a_2 x_4-x_3\leq a_3 x_5-x_4\leq a_4

比方说我们有以上几个不等式,求 x_5-x_1的最大值,直接代入计算就可以,但是要计算机能拿来计算,我们得有一个规矩点的方法

我们可以通过移项,发现 x_i\leq x_j +a_k 然后可以自然而然地想到求最短路时的松弛操作,但是这里符号是反的,这并无大碍,因为我们是求 x_5-x_1 的最大值,就等于 x_1 ~ x_5 的最小值(这里请好好理解),如果 dis[n] 是无穷大,就表明 x_5-x_1 可以无穷大,如果出现负环,就表明无解

code:

方便复制的代码QWQ

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define main mian
using namespace std;
const int N=1005;
const int M=40005;
int n,ml,md,a,b,d;
struct EDGE
{
    int nxt,to,wei,;
}edge[M];
int head[N],tot;
inline void add(int x,int y,int v)
{
    edge[++tot].nxt=head[x];
    edge[tot].to=y;
    edge[tot].wei=v;
    head[x]=tot;
}
queue<int> q;
int vis[N],dis[N],circle[N];
void spfa(int s)
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(circle,0,sizeof(circle));
    q.push(s);
    vis[s]=1,dis[s]=0;
    while(!q.empty())
    {
        int now=q.front(); q.pop(); vis[now]=0;
        for(int i=head[now];i;i=edge[i].nxt)
        {
            int tt=edge[i].to;
            if(dis[now]+edge[i].wei<dis[tt])
            {
                dis[tt]=dis[now]+edge[i].wei;
                circle[tt]=circle[now]+1;
                if(circle[tt]>=n)
                {
                    puts("-1");exit(0);
                }
                if(!vis[tt])
                {
                    vis[tt]=1;
                    q.push(tt);
                }
            }
        }
    }

}
int main()
{
    int n;
    scanf("%d%d%d",&n,&ml,&md);
    for(int i=1;i<=n;i++) add(0,i,0);
    for(int i=1;i<=ml;i++)
    {
        scanf("%d%d%d",a,b,d);
        add(a,b,d);
    }
    for(int i=1;i<=md;i++)
    {
        scanf("%d%d%d",a,b,d);
        add(b,a,-d);
    }
    spfa(0);
    spfa(1);
    if(dis[n]==INF) puts("-2");
    else printf("%d",dis[n]);
    return 0;
}