[SCOI2008] 天平

差分约束,套路地连边,套路地枚举得到答案

c1: \min(A-i) > \min(j-B)

c3: \min(i-A) > \min(B-j)

c2: \min(A-i)=\max(A-i) \,\, \min(B-j)=\max(B-j) \,\, A-i=B-j

具体式子看代码吧:

 

JZOJ 3808 | Luogu2103 道路值守

题目描述

Z-Kingdom有着四通八达的现代化交通。时值独立庆典之际,随着来自周边国家旅客的日益增多,犯罪行为也悄无声息开始滋长起来。

特别任务支援科的警察们从总部收到了关于调查伪装在游客中的犯罪分子的请求。通过调查,他们得到了一张地图,记载了Z-Kingdom内每一条道路的长度。

显然,为了减少犯罪行为被发现的可能性,犯罪分子总是会选择最短的路径来行动。为了方便安排人手和推测犯罪分子采取的路线,他们希望得知任意两个地点之间,有多少条犯罪分子可能会选择的道路。

输入输出格式

输入格式:

第一行,包含两个整数N,M,表示Z-Kingdom内的地点数和道路数。

接下来N行,每行包含三个整数x,y,z,表示道路连接的两个不同地点的标号,以及道路的长度。道路是双向的。

两个不同地点之间不会有超过一条道路。

输出格式:

输出一行,包含 N (N-1)/2 个整数

其中表示 x 号地点到 y 号地点之间有多少条犯罪分子可能会选择的道路。

先Floyd求出最短路

对于每一个点i:

{

枚举所有点j ,确保i,j联通,且i,j不是一点。

然后检查有多少点k与j有连边,且在i-j的最短路disi,j上。(也就是检查从i到j有多少条满足disi,j上且与j相连

       esumj=∑k1     k∈(g[k][j]!=0 && dis[i][k]+g[k][j]==dis[i][j])

最后考虑DP

枚举一个终点j,再枚举一个k,如果k在i-j的最短路上,那么esum[k]个方案计入C[i][j]。(有esumk条边可以到k点,在最短路上可以选k点,所以要计入方案数目)

}

USACO 牛的旅行 Cow Tours

一道比较困难的Floyd题目。

首先路径肯定都会算,就不说了。其次,Floyd也没有什么问题。

我们的策略是枚举两个不联通的点,把他们联通,求出新牧区的最小直径。

关键细节看代码

(如果有哪位dalao知道为什么要 if (i!=k && j!=k && i!=j) 麻烦您在评论中回复我