标签归档:spfa

hdu 6252 Subway Chasing(差分约束系统)

Problem Description
Mr. Panda and God Sheep are roommates and working in the same company. They always take subway to work together. There are N subway stations on their route, numbered from 1 to N. Station 1 is their home and station N is the company.
One day, Mr. Panda was getting up later. When he came to the station, God Sheep has departed X minutes ago. Mr. Panda was very hurried, so he started to chat with God Sheep to communicate their positions. The content is when Mr. Panda is between station A and B, God Sheep is just between station C and D.
B is equal to A+1 which means Mr. Panda is between station A and A+1 exclusive, or B is equal to A which means Mr. Panda is exactly on station A. Vice versa for C and D. What’s more, the communication can only be made no earlier than Mr. Panda departed and no later than God Sheep arrived.
After arriving at the company, Mr. Panda want to know how many minutes between each adjacent subway stations. Please note that the stop time at each station was ignored.

Input
The first line of the input gives the number of test cases, T. T test cases follow.
Each test case starts with a line consists of 3 integers N, M and X, indicating the number of stations, the number of chat contents and the minute interval between Mr. Panda and God Sheep. Then M lines follow, each consists of 4 integers A, B, C, D, indicating each chat content.
1≤T≤30
1≤N,M≤2000
1≤X≤109
1≤A,B,C,D≤N
A≤B≤A+1
C≤D≤C+1

Output
For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the minutes between stations in format t1,t2,…,tN−1. ti represents the minutes between station i and i+1. If there are multiple solutions, output a solution that meets 0=tc
ta+x<=td 否则 tb+x>tc
ta+x

BZOJ 2595: [Wc2008]游览计划(斯坦纳树)

Description

Input

第一行有两个整数,N和 M,描述方块的数目。
接下来 N行, 每行有 M 个非负整数, 如果该整数为 0, 则该方块为一个景点;
否则表示控制该方块至少需要的志愿者数目。 相邻的整数用 (若干个) 空格隔开,
行首行末也可能有多余的空格。

Output

由 N + 1行组成。第一行为一个整数,表示你所给出的方案
中安排的志愿者总数目。
接下来 N行,每行M 个字符,描述方案中相应方块的情况:
z  ‘_’(下划线)表示该方块没有安排志愿者;
z  ‘o’(小写英文字母o)表示该方块安排了志愿者;
z  ‘x’(小写英文字母x)表示该方块是一个景点;
注:请注意输出格式要求,如果缺少某一行或者某一行的字符数目和要求不
一致(任何一行中,多余的空格都不允许出现) ,都可能导致该测试点不得分。

Sample Input

4 4
0 1 1 0
2 5 5 1
1 5 5 1
0 1 1 0

Sample Output

6
xoox
___o
___o
xoox

HINT

 对于100%的数据,N,M,K≤10,其中K为景点的数目。输入的所有整数均在[0,2^16]的范围内

 

最早是在韩司机博客里看到这个东西,但是当时并没有学。。。最近学了一下。

斯坦纳树就是给定一些点求连通这些点的MST。一般需要联通的点数非常少。所以我们可以用状压表示当前连通了哪些点。

就拿这道题来说,我们用dp[i][j][S]表示当前以(i,j)为根且连通状态为S的情况下的最小代价。

主要是两个dp过程。我们可以把整个dp过程按照连通状态分层,层和层之间的转移就是通过枚举子集的方式进行转移(针对连通状态的改变),然后每层用spfa的方式进行转移(针对换根)。注意子集枚举的时候需要减去当前根的代价,因为被算了两次。为什么层与层之间不需要考虑换根呢?因为这种情况我们可以通过分层从前到后转换,为了减少spfa的复杂度所以就这么做好了。。

复杂度为O(spfa+3^k)。。。

居然spfa写挂了,真傻逼了。。。

 

 

poj 3268 Silver Cow Party(spfa)

Language:
Silver Cow Party
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 20287 Accepted: 9289

Description

One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤ XN). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires Ti (1 ≤ Ti ≤ 100) units of time to traverse.

Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow’s return route might be different from her original route to the party since roads are one-way.

Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?

Input

Line 1: Three space-separated integers, respectively: N, M, and X
Lines 2..M+1: Line i+1 describes road i with three space-separated integers: Ai, Bi, and Ti. The described road runs from farm Ai to farm Bi, requiring Ti time units to traverse.

Output

Line 1: One integer: the maximum of time any one cow must walk.

Sample Input

Sample Output

Hint

Cow 4 proceeds directly to the party (3 units) and returns via farms 1 and 3 (7 units), for a total of 10 time units.

题意:求出x到各个点的最短路加上各个点到x的最短路的最大值。

如果每个点都跑一遍spfa的话,复杂度就有点大了。因为是单向边,所以可以开两个邻接表,一个是正向,一个是反向。那么各自从x跑一遍spfa就可以了。因为反向跑的话,就相当于是从各个点到x的最短路。