题解 P4878 【[USACO05DEC] 布局】

发表于 | 更新于 | 阅读次数：

蒟蒻刚好在学查分约束，为了满足自己的好奇心点了进来….

咳咳切入正题，这题是用差分约束的（废话）

那么差分约束是什么呢，（前置知识——>最短路（SPFA P3371) ),我们得到一串不等式（不等式应该不用补充了吧…）

形如 a-b>=c,b-a<=c balabala…

敲黑板

那么对于这道题，我们是不是可以得到每个奶牛之间的距离不等式?

A 号奶牛与 BB 号奶牛之间的距离须 ≤D

分别把两头奶牛的位置换为dis[x]和dis[u]，将e[i].weigh视为它们之间的那个D然后可以得到

dis[x]-dis[u]<=e[i].weigh

是不是很眼熟啊

对，就是SPFA中的松弛操作！

对于第二个限制，我们在不等式两边同时乘上-1，来使其变成<=的类型，

那么这道题就非常好做，

我们每次读入第一个限制，将限制看为边权，从第一个点连一条有向边至第二个点，

对于第二个限制，我们从第二个点连一条有向边至第一个点，求一遍最短路。那么dis[n]就是我们的答案啦。

坑点：可能这个图是不联通的，那就在每个点与0连一条虚边，那么就可以判断是否合法。

代码实际上不长（因为我是换行狂魔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<bits/stdc++.h>
using namespace std;
void read(int &x)
{
    x=0;
    char ch=getchar();
    int pd=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')pd=-pd;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    x=x*pd;
}
void write(const int &x)
{
    int tmp=x;
    int s=0;
    char g[10001];
    if(tmp==0)
    {
    	putchar('0');
    	return;
	}
    if(tmp<0)
    {
        tmp=-tmp;
        putchar('-');
    }
    while(tmp>0)
    {
        g[s++]=tmp%10+'0';
        tmp/=10;
    }
    while(s>0)
    {
        putchar(g[--s]);
    }
}
 const int N=1e5+10;
 int t,h[N],dis[N],use[N],n,m1,m2;
 bool visit[N];
struct dd
{
	int end,weigh,nt;
}e[2*N];
const int big=0x7fffffff;
void add(int begin,int end,int weigh)
{
	++t;
	e[t].end=end;
	e[t].weigh=weigh;
	e[t].nt=h[begin];
	h[begin]=t;
} 
int spfa(int start )
{
	queue<int>q;
	memset(visit,false,sizeof(visit));
	memset(use,0,sizeof(use));
	for(register int i=1;i<=n;++i)
	{
		dis[i]=big;
	}
	dis[start]=0;
	q.push(start);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		use[x]++;
		if(use[x]>n)
		{
			return -1;
		}
		visit[x]=0;
		for(register int i=h[x];i;i=e[i].nt)
		{
			int u=e[i].end;
			if(dis[u]>dis[x]+e[i].weigh)
			{
				dis[u]=dis[x]+e[i].weigh;
				if(!visit[u])
				{
					
					q.push(u);visit[u]=1;
				}
			}
		}
	}
	if(dis[n]==big)
	{
		return -2;
	}
	return dis[n];
}
int main()
{
	read(n);
	read(m1);
	read(m2);
	for(register int i=1;i<=m1;++i)
	{
		int x,y,z;
		read(x);
		read(y);
		read(z);
		add(x,y,z);
	}
	for(register int i=1;i<=m2;++i)
	{
		int x,y,z;
		read(x);
		read(y);
		read(z);
		add(y,x,-z);
	}
	for(register int i=1;i<=n;++i)
	{
		add(0,i,0);
	}
	int ans=spfa(0);
	if(ans==-1||ans==-2)
	{
		write(ans);
		return 0;
	}
	write(spfa(1));
}