bef-> NO.32

Veröffentlicht am

题目描述

Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= 1,000,000), which includes both times A and B. Obviously, FJ must create a reservation system to determine which stall each cow can be assigned for her milking time. Of course, no cow will share such a private moment with other cows.

Help FJ by determining:The minimum number of stalls required in the barn so that each cow can have her private milking periodAn assignment of cows to these stalls over timeMany answers are correct for each test dataset; a program will grade your answer.

约翰的N(l<N< 50000)头奶牛实在是太难伺候了，她们甚至有自己独特的产奶时段.当 然对于某一头奶牛，她每天的产奶时段是固定的，为时间段A到B包括时间段A和时间段B.显然，约翰必须开发一个调控系统来决定每头奶牛应该被安排到哪个牛棚去挤 奶，因为奶牛们显然不希望在挤奶时被其它奶牛看见.

约翰希望你帮他计算一下：如果要满足奶牛们的要求，并且每天每头奶牛都要被挤过奶，至少需要多少牛棚 •每头牛应该在哪个牛棚被挤奶。如果有多种答案，你只需任意一种即可。

输入输出格式

输入格式：

Line 1: A single integer, N

Lines 2..N+1: Line i+1 describes cow i’s milking interval with two space-separated integers.

输出格式：

Line 1: The minimum number of stalls the barn must have.

Lines 2..N+1: Line i+1 describes the stall to which cow i will be assigned for her milking period.

输入输出样例

输入样例#1：

1
2
3
4
5
6
5
1 10
2 4
3 6
5 8
4 7

输出样例#1：

1
2
3
4
5
6
4
1
2
3
2
4

说明

Explanation of the sample:

Here’s a graphical schedule for this output:

Time 1 2 3 4 5 6 7 8 9 10

Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>>

Stall 2 .. c2>>>>>> c4>>>>>>>>> .. ..

Stall 3 .. .. c3>>>>>>>>> .. .. .. ..

Stall 4 .. .. .. c5>>>>>>>>> .. .. ..Other outputs using the same number of stalls are possible.

题解

一道很简单的贪心，D1T1难度多一点。

显然只要按照左端点排序，按顺序选即可，如果当前左端点和右端点冲突，就用下一个。

我分析了一下，这样做其实

不过依旧通过了。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 50005
struct Node{
	int l , r , k;
	bool operator < (const Node& x)const{
//		if(l == x.l)	return r < x.r;
		return l < x.l;
	}
}p[maxn];
int n;
int inc[maxn];
int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d%d",&p[i].l,&p[i].r),p[i].k = i;
	std::sort(p+1,p+n+1);
	int ans = 0 , tot = 0;
	while(tot < n)
	{
		++ans;
		int R = 0;
		for(int i = 1 ; i <= n ; ++i){
			if(p[i].l > R && (!inc[p[i].k]))
				++tot , inc[p[i].k] = ans , R = std::max(R , p[i].r);
		}		
	}
	printf("%d\n",ans);
	for(int i = 1 ; i <= n ; ++i)
		printf("%d\n",inc[i]);
}

其实我们可以用堆维护每个牛棚最右边的端点，每次去找最小的右端点看看能不能加入，显然这个优化非常明显，对于每头牛的复杂度为

最后时间复杂度为

Code:

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#define pii std::pair<int,int>
#define mp(x,y) std::make_pair((x),(y))
#define maxn 50005
struct Node{
	int l , r , k;
	bool operator < (const Node& x)const{
//		if(l == x.l)	return r < x.r;
		return l < x.l;
	}
}p[maxn];
int n;
int inc[maxn];
std::priority_queue<pii , std::vector<pii> , std::greater<pii> > q;
int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d%d",&p[i].l,&p[i].r),p[i].k = i;
	std::sort(p+1,p+n+1);
	int ans = 1;
	q.push(mp(p[1].r,1)) , inc[p[1].k] = ans;
	for(int i = 2 ; i <= n ; ++i){
		int k = q.top().first , num = q.top().second;
		if(k >= p[i].l)	++ans , q.push(mp(p[i].r,ans)) , inc[p[i].k] = ans;
		else{
			q.pop();
			k = std::max(k , p[i].r);
			q.push(mp(k,num));
			inc[p[i].k] = num;
		}
	}
	printf("%d\n",ans);
	for(int i = 1 ; i <= n ; ++i)
		printf("%d\n",inc[i]);
}

[USACO08FEB]酒店Hotel

题目描述

The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacation residence. This immense hotel has N (1 ≤ N ≤ 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake, of course).

The cows and other visitors arrive in groups of size Di (1 ≤ Di ≤ N) and approach the front desk to check in. Each group i requests a set of Di contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers r..r+Di-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of r to be the smallest possible.

Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters Xi and Di which specify the vacating of rooms Xi ..Xi +Di-1 (1 ≤ Xi ≤ N-Di+1). Some (or all) of those rooms might be empty before the checkout.

Your job is to assist Canmuu by processing M (1 ≤ M < 50,000) checkin/checkout requests. The hotel is initially unoccupied.

参考样例，第一行输入n，m ，n代表有n个房间，编号为1—-n，开始都为空房，m表示以下有m行操作，以下 每行先输入一个数 i ，表示一种操作：

若i为1，表示查询房间，再输入一个数x，表示在1—n 房间中找到长度为x的连续空房，输出连续x个房间中左端的房间号，尽量让这个房间号最小，若找不到长度为x的连续空房，输出0。

若i为2，表示退房，再输入两个数 x，y 代表 房间号 x—-x+y-1 退房，即让房间为空。

输入输出格式

输入格式：

* Line 1: Two space-separated integers: N and M

* Lines 2..M+1: Line i+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and Di (b) Three space-separated integers representing a check-out: 2, Xi, and Di

输出格式：

* Lines 1…..: For each check-in request, output a single line with a single integer r, the first room in the contiguous sequence of rooms to be occupied. If the request cannot be satisfied, output 0.

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
10 6
1 3
1 3
1 3
1 3
2 5 5
1 6

输出样例#1：

1
2
3
4
5
1
4
7
0
5

题解

主要是要会线段树维护最大子段，我因为一个地方想错而调了2小时。

又是一个两小时警告！线段树pushup更新当前区间最大子段是左儿子右儿子最大子段和中间新的一段取max，不是当前区间从左边最大，从右边最大，然后中间最大取max

错误：

1
2
3
4
5
6
7
inline void pushup(int Node , int ln , int rn){
	if(lmax[ls(Node)] != ln)	lmax[Node] = lmax[ls(Node)];
	else lmax[Node] = ln + lmax[rs(Node)];
	if(rmax[rs(Node)] != rn)	rmax[Node] = rmax[rs(Node)];
	else rmax[Node] = rn + rmax[ls(Node)];
	sum[Node] = max(lmax[ls(Node)] , rmax[ls(Node)] + lmax[rs(Node)] , rmax[rs(Node)]);//cautions for two hours ! are sums!!
}

正确：

1
2
3
4
5
6
7
inline void pushup(int Node , int ln , int rn){
	if(lmax[ls(Node)] != ln)	lmax[Node] = lmax[ls(Node)];
	else lmax[Node] = ln + lmax[rs(Node)];
	if(rmax[rs(Node)] != rn)	rmax[Node] = rmax[rs(Node)];
	else rmax[Node] = rn + rmax[ls(Node)];
	sum[Node] = max(sum[ls(Node)] , rmax[ls(Node)] + lmax[rs(Node)] , sum[rs(Node)]);//cautions for two hours ! are sums!!
}

知道这个这道题还是不难的

Code：

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
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define maxn 100005
int n , m , op , x , y;
struct SegmentTree
{
	#define ls(x) (x<<1)
	#define rs(x) (x<<1|1)
	int lmax[maxn<<2] , rmax[maxn<<2] , sum[maxn<<2] , tag[maxn<<2];
	inline int max(int x , int y , int z){
		int k = x > y? x : y;
		return k > z ? k : z;
	}
	void build(int l , int r , int Node)
	{
		sum[Node] = lmax[Node] = rmax[Node] = r - l + 1;
		if(l == r)	return ;
		int mid = l + r >> 1;
		build(l , mid , ls(Node));
		build(mid + 1 , r , rs(Node));
	}
	inline void pushup(int Node , int ln , int rn){
		if(lmax[ls(Node)] != ln)	lmax[Node] = lmax[ls(Node)];
		else lmax[Node] = ln + lmax[rs(Node)];
		if(rmax[rs(Node)] != rn)	rmax[Node] = rmax[rs(Node)];
		else rmax[Node] = rn + rmax[ls(Node)];
		sum[Node] = max(sum[ls(Node)] , rmax[ls(Node)] + lmax[rs(Node)] , sum[rs(Node)]);//cautions for two hours ! are sums!!
	}
	inline void pushdown(int Node , int ln , int rn)
	{
		if(tag[Node]) tag[ls(Node)] = tag[rs(Node)] = tag[Node];
		if(tag[Node] == 1){//mean the interval has been clear
			sum[ls(Node)] = sum[rs(Node)] = lmax[ls(Node)] = rmax[ls(Node)] = lmax[rs(Node)] = rmax[rs(Node)] = 0;
		}
		else if(tag[Node] == 2){
			sum[ls(Node)] = lmax[ls(Node)] = rmax[ls(Node)] = ln;
			sum[rs(Node)] = lmax[rs(Node)] = rmax[rs(Node)] = rn;
		}
		tag[Node] = 0;
	}
	void update(int L , int R , int l , int r , int Node , int v)
	{
		if(L <= l && r <= R)
		{
			if(v == 1){
				sum[Node] = lmax[Node] = rmax[Node] = 0;
			}
			else if(v == 2){
				sum[Node] = lmax[Node] = rmax[Node] = r - l + 1;
			}
			tag[Node] = v;
			return;
		}
		int mid = l + r >> 1;
		pushdown(Node , mid - l + 1 , r - mid);
		if(L <= mid)	update(L , R , l , mid , ls(Node) , v);
		if(R > mid)		update(L , R , mid + 1, r , rs(Node) , v);
		pushup(Node , mid - l + 1 , r - mid);
	}
	int queryPos(int l , int r , int Node , int len)
	{
		if(l == r)	return l;
		int mid = l + r >> 1;
		pushdown(Node , mid - l + 1 , r - mid);
		if(sum[ls(Node)] >= len)	return queryPos(l , mid , ls(Node) , len);
		if(rmax[ls(Node)] + lmax[rs(Node)] >= len)	return mid - rmax[ls(Node)] + 1;
		return queryPos(mid + 1 , r , rs(Node) , len);
	}
}tr;
int main()
{
	scanf("%d%d",&n,&m);
	tr.build(1,n,1);
	for(int i = 1 ; i <= m ; ++i){
		scanf("%d",&op);
		if(op == 1){
			scanf("%d",&x);
			if(tr.sum[1] >= x){
				int k = tr.queryPos(1,n,1,x);
				printf("%d\n",k);
				tr.update(k , k + x - 1 , 1 , n , 1 , 1);
			}
			else puts("0");
		}
		if(op == 2){
			scanf("%d%d",&x,&y);
			tr.update(x , x + y - 1 , 1 , n , 1 , 2);
		}
	}
}

[USACO13JAN]座位Seating

题目描述

To earn some extra money, the cows have opened a restaurant in their barn specializing in milkshakes. The restaurant has N seats (1 <= N <= 500,000) in a row. Initially, they are all empty.

Throughout the day, there are M different events that happen in sequence at the restaurant (1 <= M <= 300,000). The two types of events that can happen are:

  1. A party of size p arrives (1 <= p <= N). Bessie wants to seat the party in a contiguous block of p empty seats. If this is possible, she does so in the lowest position possible in the list of seats. If it is impossible, the party is turned away.
  2. A range [a,b] is given (1 <= a <= b <= N), and everybody in that range of seats leaves.

Please help Bessie count the total number of parties that are turned away over the course of the day.

有一排n个座位，m次操作。A操作：将a名客人安置到最左的连续a个空位中，没有则不操作。L操作：[a,b]的客人离开。

求A操作的失败次数。

输入输出格式

输入格式：

* Line 1: Two space-separated integers, N and M.

* Lines 2..M+1: Each line describes a single event. It is either a line of the form “A p” (meaning a party of size p arrives) or “L a b” (meaning that all cows in the range [a, b] leave).

输出格式：

* Line 1: The number of parties that are turned away.

输入输出样例

输入样例#1：

1
2
3
4
5
10 4 
A 6 
L 2 4 
A 5 
A 2

输出样例#1：

1
1

说明

There are 10 seats, and 4 events. First, a party of 6 cows arrives. Then all cows in seats 2..4 depart. Next, a party of 5 arrives, followed by a party of 2.

Party #3 is turned away. All other parties are seated.

题解

感觉写题速度太慢，考场上药丸，所以下午准备练下写题速度（3.5小时写5题中间不休息试试）

和上题一样，主要是想到最大子段和如何用线段树维护以及怎样确定最靠左的长度大于等于给定值的位置（分治的思想，能靠左就靠左，否则走右边，但是最大子段和由于左右之间有联系所以还要看看左区间和右区间中间合起来能不能行，画图讨论就能发现询中的选项一严格不劣于选项二）。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 500005
int n , m , op , x , y , ans;
struct SegmentTree
{
	#define s(x) sum[x]
	#define g(x) tag[x]
	#define lx(x) lmax[x]
	#define rx(x) rmax[x]
	#define ls(x) (x<<1)
	#define rs(x) (x<<1|1)
	int sum[maxn<<2] , lmax[maxn<<2] , rmax[maxn<<2] , tag[maxn<<2];
	inline int max(int x , int y, int z){
		int k = x > y ? x : y;
		return k > z ? k : z;
	}
	void build(int l , int r , int p)
	{
		s(p) = lx(p) = rx(p) = r - l + 1;
		if(l == r)	return;
		int mid = l + r >> 1;
		build(l , mid , ls(p));
		build(mid + 1 , r , rs(p));
	}
	inline void pushup(int p , int ln , int rn)
	{
		if(lx(ls(p)) == ln) lx(p) = ln + lx(rs(p));
		else lx(p) = lx(ls(p));
		if(rx(rs(p)) == rn)	rx(p) = rn + rx(ls(p));
		else rx(p) = rx(rs(p));
		s(p) = max(s(ls(p)) , s(rs(p)) , rx(ls(p)) + lx(rs(p)));
	}
	inline void pushdown(int p , int ln , int rn)
	{
		if(g(p) == 1){//clear
			lx(ls(p)) = lx(rs(p)) = s(ls(p)) = s(rs(p)) = rx(rs(p)) = rx(ls(p)) = 0;
			g(ls(p)) = g(rs(p)) = g(p);
			g(p) = 0;
		}
		else if(g(p) == 2){
			lx(ls(p)) = s(ls(p)) = rx(ls(p)) = ln;
			lx(rs(p)) = s(rs(p)) = rx(rs(p)) = rn;
			g(ls(p)) = g(rs(p)) = g(p);
			g(p) = 0;
		}
	}
	void update(int L , int R , int l , int r , int p , int v)
	{
		if(L <= l && r <= R){
			if(v == 1){
				s(p) = lx(p) = rx(p) = 0;
			}
			else{
				s(p) = lx(p) = rx(p) = r - l + 1;
			}
			g(p) = v;
			return; 
		}
		int mid = l + r >> 1;
		pushdown(p , mid - l + 1 , r - mid);
		if(L <= mid)	update(L , R , l , mid , ls(p) , v);
		if(R > mid)		update(L , R , mid + 1 , r , rs(p) , v);
		pushup(p , mid - l + 1 , r - mid);
	}
	int queryPos(int l , int r , int p , int len)
	{
		if(l == r)	return l;
		int mid = l + r >> 1;
		pushdown(p , mid - l + 1 , r - mid);
		if(s(ls(p)) >= len)	return queryPos(l , mid , ls(p) , len);
		if(lx(rs(p)) + rx(ls(p)) >= len)	return mid - rx(ls(p)) + 1;
		return queryPos(mid + 1 , r , rs(p) , len) ;
	}
}tr;
int main()
{
	scanf("%d%d",&n,&m);
	tr.build(1,n,1);
	for(int i = 1 ; i <= m ; ++i)
	{
		char op;
		std::cin>>op;
		if(op == 'A'){
			int x;
			scanf("%d",&x);
			if(tr.sum[1] < x) {
				++ans;
			}
			else{
				int k = tr.queryPos(1,n,1,x);
//				printf("%d\n",k);
				tr.update(k , k + x - 1 , 1 , n , 1 , 1);
			}
		}
		else{
			int x , y;
			scanf("%d%d",&x,&y);
			tr.update(x , y , 1 , n , 1 , 2);
		}
	}
	printf("%d",ans);
}

[USACO08JAN]电话线Telephone Lines

题目描述

Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system.

There are N (1 ≤ N ≤ 1,000) forlorn telephone poles conveniently numbered 1..N that are scattered around Farmer John’s property; no cables connect any them. A total of P (1 ≤ P ≤ 10,000) pairs of poles can be connected by a cable; the rest are too far apart.

The i-th cable can connect the two distinct poles Ai and Bi, with length Li (1 ≤ Li ≤ 1,000,000) units if used. The input data set never names any {Ai, Bi} pair more than once. Pole 1 is already connected to the phone system, and pole N is at the farm. Poles 1 and N need to be connected by a path of cables; the rest of the poles might be used or might not be used.

As it turns out, the phone company is willing to provide Farmer John with K (0 ≤ K < N) lengths of cable for free. Beyond that he will have to pay a price equal to the length of the longest remaining cable he requires (each pair of poles is connected with a separate cable), or 0 if he does not need any additional cables.

Determine the minimum amount that Farmer John must pay.

多年以后，笨笨长大了，成为了电话线布置师。由于地震使得某市的电话线全部损坏，笨笨是负责接到震中市的负责人。该市周围分布着N(1<=N<=1000)根据1……n顺序编号的废弃的电话线杆，任意两根线杆之间没有电话线连接，一共有p(1<=p<=10000)对电话杆可以拉电话线。其他的由于地震使得无法连接。

第i对电线杆的两个端点分别是ai,bi，它们的距离为li(1<=li<=1000000)。数据中每对(ai,bi)只出现一次。编号为1的电话杆已经接入了全国的电话网络，整个市的电话线全都连到了编号N的电话线杆上。也就是说，笨笨的任务仅仅是找一条将1号和N号电线杆连起来的路径，其余的电话杆并不一定要连入电话网络。

电信公司决定支援灾区免费为此市连接k对由笨笨指定的电话线杆，对于此外的那些电话线，需要为它们付费，总费用决定于其中最长的电话线的长度(每根电话线仅连接一对电话线杆)。如果需要连接的电话线杆不超过k对，那么支出为0.

请你计算一下，将电话线引导震中市最少需要在电话线上花多少钱？

输入输出格式

输入格式：

输入文件的第一行包含三个数字n,p,k;

第二行到第p+1行，每行分别都为三个整数ai,bi,li。

输出格式：

一个整数，表示该项工程的最小支出，如果不可能完成则输出-1.

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

输出样例#1：

1
4

题解

二分答案 + SPFA松弛dp

其实想到二分答案就好，dp显然的

虽然在写这道题时依然出了很多低级错误，但还是自己调出来了了。

考场期望得分：100

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#define maxn 1005
#define INF 0x7f7f7f7f
int head[maxn] , n , m , f[maxn][maxn], x , y , dis , knum , cnt;
bool vis[maxn];
struct edge{
	int next , to , dis;
}e[maxn*50];
inline void add(int x , int y , int dis)
{
	e[++cnt].next = head[x];
	e[cnt].to = y;
	e[cnt].dis = dis;
	head[x] = cnt;
}
inline bool SPFA(int now)
{
//	printf("ans now : %d\n",now);
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 0 ; j <= n ; ++j)
			f[i][j] = INF;
	std::memset(vis,false,sizeof(vis));
	std::queue<int> q;
	f[1][0] = 0;
	q.push(1) , vis[1] = true;
	while(!q.empty())
	{
		int k = q.front();
		vis[k] = false;
		q.pop();
		for(int i = head[k] ; i ; i = e[i].next){
			int v = e[i].to , d = e[i].dis;
			if(d > now){
				for(int j = 0 ; j <= knum ; ++j)
					if(f[k][j] + d < f[v][j+1]){
//						printf("f[%d][%d] = %d + %d < f[%d][%d] = %d\n",k,j,f[k][j],d,v,j+1,f[v][j+1]);
						f[v][j+1] = f[k][j] + d;
						if(!vis[v]){
							vis[v] = true;
							q.push(v);
						}
					}
			}
			else{
				for(int j = 0 ; j <= knum ; ++j)
					if(f[k][j] + d < f[v][j]){
//						printf("f[%d][%d] = %d + %d < f[%d][%d] = %d\n",k,j,f[k][j],d,v,j,f[v][j]);
						f[v][j] = f[k][j] + d;
						if(!vis[v]){
							vis[v] = true;
							q.push(v);
						}
					}
			}
		}
	}
//	for(int i = 0 ; i <= knum ; ++i)
//		printf("f[n][%d] = %d\n",i,f[n][i]);
	for(int i = 0 ; i <= knum ; ++i)
		if(f[n][i] < INF)	
			return true;
	return false;
}
int main()
{
	scanf("%d%d%d",&n,&m,&knum);
	for(int i = 1 ; i <= m ; ++i){
		scanf("%d%d%d",&x,&y,&dis); add(x,y,dis) , add(y,x,dis);
	}
	int l = 0 , r = 100000000 , ans = INF;
	while(l <= r){
		int mid = l + r >> 1;
		if(SPFA(mid)) ans = mid , r = mid - 1;
		else l = mid + 1;
	}
	if(ans == INF){
		printf("-1");
		return 0;
	}
	printf("%d",ans);
}

[USACO07NOV]牛继电器Cow Relays

题目描述

For their physical fitness program, N (2 ≤ N ≤ 1,000,000) cows have decided to run a relay race using the T (2 ≤ T ≤ 100) cow trails throughout the pasture.

Each trail connects two different intersections (1 ≤ I1i ≤ 1,000; 1 ≤ I2i ≤ 1,000), each of which is the termination for at least two trails. The cows know the lengthi of each trail (1 ≤ lengthi ≤ 1,000), the two intersections the trail connects, and they know that no two intersections are directly connected by two different trails. The trails form a structure known mathematically as a graph.

To run the relay, the N cows position themselves at various intersections (some intersections might have more than one cow). They must position themselves properly so that they can hand off the baton cow-by-cow and end up at the proper finishing place.

Write a program to help position the cows. Find the shortest path that connects the starting intersection (S) and the ending intersection (E) and traverses exactly N cow trails.

给出一张无向连通图，求S到E经过k条边的最短路。

输入输出格式

输入格式：

* Line 1: Four space-separated integers: N, T, S, and E

* Lines 2..T+1: Line i+1 describes trail i with three space-separated integers: lengthi , I1i , and I2i

输出格式：

* Line 1: A single integer that is the shortest distance from intersection S to intersection E that traverses exactly N cow trails.

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

输出样例#1：

1
10

题解

一开始还打算写SPFA松弛dp，但是看了看范围感觉不对，然后n还特别小。

于是就去学习了矩阵在图上的运用。具体参见一位集训队队员的论文。

1540976677462

1540976694732

1540976614400

这是弗洛伊德算法，再结合上面的分析我们胡乱填上矩阵发现这个是满足结合律的，手算一下发现可以，于是就快速幂

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 205
int id[maxn*10] , n , m , k , x , y , dis , s , t;
struct Matrix{
	int mat[maxn][maxn];
	Matrix(){
		std::memset(mat,0x3f,sizeof(mat));
	}
	inline int* operator[](const int x){
		return mat[x];
	}
}g;	
Matrix operator * (Matrix& x , Matrix& y){
	Matrix c;
	for(int i = 1 ; i <= n ; ++i)	
		for(int j = 1 ; j <= n ; ++j)
			for(int k = 1 ; k <= n ; ++k)
				c[i][j] = std::min(c[i][j] , x[i][k] + y[k][j]);
	return c;
}
Matrix pow(Matrix& x , int k){
	Matrix ans = x;
	--k;
	while(k){
		if(k&1) ans = ans * x;
		x = x * x;
		k >>= 1;
	}
	return ans;
}
int main()
{
	scanf("%d%d%d%d",&k,&m,&s,&t);
	for(int i = 1 ; i <= m ; ++i){
		scanf("%d%d%d",&dis,&x,&y);
		x = id[x] ? id[x] : id[x] = ++n;
		y = id[y] ? id[y] : id[y] = ++n;
		g[x][y] = g[y][x] = std::min(g[x][y] , dis);
	}
	Matrix ans = pow(g , k);
	printf("%d",ans[id[s]][id[t]]);
}

[APIO2009]抢掠计划

题目描述

Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定， 在每个路口都设立了一个 Siruseri 银行的 ATM 取款机。令人奇怪的是，Siruseri 的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。

Banditji 计划实施 Siruseri 有史以来最惊天动地的 ATM 抢劫。他将从市中心 出发，沿着单向道路行驶，抢劫所有他途径的 ATM 机，最终他将在一个酒吧庆 祝他的胜利。

使用高超的黑客技术，他获知了每个 ATM 机中可以掠取的现金数额。他希 望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可 以经过同一路口或道路任意多次。但只要他抢劫过某个 ATM 机后，该 ATM 机 里面就不会再有钱了。 例如，假设该城中有 6 个路口，道路的连接情况如下图所示：

img

市中心在路口 1，由一个入口符号→来标识，那些有酒吧的路口用双圈来表

示。每个 ATM 机中可取的钱数标在了路口的上方。在这个例子中，Banditji 能抢 劫的现金总数为 47，实施的抢劫路线是：1-2-4-1-2-3-5。

输入输出格式

输入格式：

第一行包含两个整数 N、M。N 表示路口的个数，M 表示道路条数。接下来 M 行，每行两个整数，这两个整数都在 1 到 N 之间，第 i+1 行的两个整数表示第 i 条道路的起点和终点的路口编号。接下来 N 行，每行一个整数，按顺序表示每 个路口处的 ATM 机中的钱数。接下来一行包含两个整数 S、P，S 表示市中心的 编号，也就是出发的路口。P 表示酒吧数目。接下来的一行中有 P 个整数，表示 P 个有酒吧的路口的编号。

输出格式：

输出一个整数，表示 Banditji 从市中心开始到某个酒吧结束所能抢劫的最多 的现金总数。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
6 7 
1 2 
2 3 
3 5 
2 4 
4 1 
2 6 
6 5 
10 
12 
8 
16 
1 
5 
1 4 
4 3 5 6

输出样例#1：

1
47

说明

50%的输入保证 N, M<=3000。所有的输入保证 N, M<=500000。每个 ATM 机中可取的钱数为一个非负整数且不超过 4000。

输入数据保证你可以从市中心 沿着 Siruseri 的单向的道路到达其中的至少一个酒吧。

题解

一道sb Tarjan+SPFA松弛dp/拓扑dp我写挂好几次。。。

也就D1T2难度。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <iostream>
#include <cstring>
#include <map>
#define maxn 1000005
int head[maxn] , f[maxn] , n , m  , vis[maxn] , valid[maxn], s , idx , p , tot , dfn[maxn] , val[maxn] , g[maxn] , low[maxn] , scc[maxn] , d[maxn] ,  ans , cnt;
bool ins[maxn] , spfa[maxn] , conn[maxn];
std::stack<int> st;
std::map<int,int> rep[maxn];
struct edge{
	int next , to;
}e[maxn*2];
struct E{
	int fr , to;
}er[maxn*2];
inline void add(int x , int y)
{
	e[++cnt].next = head[x];
	e[cnt].to = y;
	++d[y];
	head[x] = cnt;
}
inline void DP()
{
	std::queue<int> q;
	spfa[scc[s]] = true;
	for(int i = 1 ; i <= tot ; ++i)
		g[i] = f[i];
	q.push(scc[s]);
	while(!q.empty())
	{
		int k = q.front();
		q.pop();
		spfa[k] = false;
		for(int i = head[k] ; i ; i = e[i].next){
			int v = e[i].to;
//			conn[v] = true;
			if(f[v] <= f[k] + g[v]){
				f[v] = f[k] + g[v];
				if(!spfa[v]){
					spfa[v] = true;
					q.push(v);
				}
			}
		}
	}
//	for(int i = 1 ; i <= tot ; ++i)
//		std::cout << conn[i] << ' ' << valid[i] << std::endl;
	for(int i = 1 ; i <= tot ; ++i)
		if(valid[i])	
			ans = std::max(ans , f[i]);
}
void Tarjan(int x)
{
	dfn[x] = low[x] = ++idx;
	st.push(x);
	ins[x] = true;
	for(int i = head[x] ; i ; i = e[i].next)
	{
		int v = e[i].to;
		if(!dfn[v]){
			Tarjan(v);
			low[x] = std::min(low[x] , low[v]);
		}
		else if(ins[v]){
			low[x] = std::min(low[x] , dfn[v]);
		}
	}
	if(dfn[x] == low[x]){
		++tot;
		while(st.top() != x){
			int v = st.top();
			st.pop();
			f[tot] += val[v];
			scc[v] = tot;
			ins[v] = false;
			valid[tot] |= vis[v]; // not vis[x] !!! no more sb mistakes!!!
//			printf("%d %d\n",valid[tot] , vis[x]);
		}
		f[tot] += val[x];
		scc[x] = tot;
		ins[x] = false;
		valid[tot] |= vis[x];
		st.pop();
	}
}
int main()
{
//	freopen("APIO.in","r",stdin);
//	freopen("APIO.out","w",stdout);
	scanf("%d%d",&n,&m);
	int nums = 0;
	int x , y;
	for(int i = 1 ; i <= m  ; ++i)
		scanf("%d%d",&x,&y) , add(x,y) , er[++nums].fr = x , er[nums].to = y;
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&val[i]);
	scanf("%d%d",&s,&p);
	for(int i = 1 ; i <= p ; ++i){
		int x;
		scanf("%d",&x);
		vis[x] = 1;
	}

	Tarjan(s);
//	for(int i = 1 ; i <= n ; ++i)
//		if(vis[i])
//			printf("%d %d %d\n",i,scc[i] , valid[scc[i]]);

	std::memset(head,0,sizeof(head));
	std::memset(e,0,sizeof(e));
	std::memset(d,0,sizeof(d));
	cnt = 0;
	
	for(int i = 1 ; i <= nums ; ++i){
		int u = er[i].fr , v = er[i].to;
		if(scc[u] != scc[v] && (scc[u] != 0 && scc[v] != 0)){
			add(scc[u],scc[v]);
		}
	}
	DP();
	printf("%d",ans);
}

[USACO10FEB]慢下来Slowing down

题目描述

Every day each of Farmer John’s N (1 <= N <= 100,000) cows conveniently numbered 1..N move from the barn to her private pasture. The pastures are organized as a tree, with the barn being on pasture 1. Exactly N-1 cow unidirectional paths connect the pastures; directly connected pastures have exactly one path. Path i connects pastures A_i and B_i (1 <= A_i <= N; 1 <= B_i <= N).

Cow i has a private pasture P_i (1 <= P_i <= N). The barn’s small door lets only one cow exit at a time; and the patient cows wait until their predecessor arrives at her private pasture. First cow 1 exits and moves to pasture P_1. Then cow 2 exits and goes to pasture P_2, and so on.

While cow i walks to P_i she might or might not pass through a pasture that already contains an eating cow. When a cow is present in a pasture, cow i walks slower than usual to prevent annoying her friend.

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
Consider the following pasture network, where the number between
parentheses indicates the pastures' owner.

        1 (3)        
       / \
  (1) 4   3 (5)
     / \   
(2) 2   5 (4)

First, cow 1 walks to her pasture:

        1 (3)        
       / \
  [1] 4*  3 (5)
     / \   
(2) 2   5 (4)

When cow 2 moves to her pasture, she first passes into the barn's
pasture, pasture 1. Then she sneaks around cow 1 in pasture 4 before
arriving at her own pasture.

        1 (3)
       / \
  [1] 4*  3 (5)
     / \   
[2] 2*  5 (4)

Cow 3 doesn't get far at all -- she lounges in the barn's pasture, #1.

        1* [3]
       / \
  [1] 4*  3 (5)
     / \   
[2] 2*  5 (4)

Cow 4 must slow for pasture 1 and 4 on her way to pasture 5:

        1* [3]
       / \
  [1] 4*  3 (5)
     / \   
[2] 2*  5* [4]

Cow 5 slows for cow 3 in pasture 1 and then enters her own private pasture:

        1* [3]
       / \
  [1] 4*  3*[5]
     / \   
[2] 2*  5* [4]

FJ would like to know how many times each cow has to slow down.

每天Farmer John的N头奶牛(1 <= N <= 100000，编号1…N)从粮仓走向他的自己的牧场。牧场构成了一棵树，粮仓在1号牧场。恰好有N-1条道路直接连接着牧场，使得牧场之间都恰好有一条路径相连。第i条路连接着A_i，B_i，(1 <= A_i <= N; 1 <= B_i <= N)。 奶牛们每人有一个私人牧场P_i (1 <= P_i <= N)。粮仓的门每次只能让一只奶牛离开。耐心的奶牛们会等到他们的前面的朋友们到达了自己的私人牧场后才离开。首先奶牛1离开，前往P_1；然后是奶牛2，以此类推。

当奶牛i走向牧场P_i时候，他可能会经过正在吃草的同伴旁。当路过已经有奶牛的牧场时，奶牛i会放慢自己的速度，防止打扰他的朋友。

FJ想要知道奶牛们总共要放慢多少次速度。

输入输出格式

输入格式：

* Line 1: Line 1 contains a single integer: N

* Lines 2..N: Line i+1 contains two space-separated integers: A_i and B_i

* Lines N+1..N+N: line N+i contains a single integer: P_i

输出格式：

* Lines 1..N: Line i contains the number of times cow i has to slow down.

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
10
5 
1 4 
5 4 
1 3 
2 4 
4 
2 
1 
5 
3

输出样例#1：

1
2
3
4
0 
1 
0 
2

题解

一开始想整个巧妙的方法，最后发现HPD维护下就行了。NOIp不会考这么简单的吧。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
int head[maxn] , cnt , n , val[maxn] ;
struct edge{
	int next , to;
}e[maxn*2];
struct HPD
{
	#define ls(x) (x<<1)
	#define rs(x) (x<<1|1)
	int id[maxn] , hs[maxn] , sz[maxn] , dep[maxn] , top[maxn] , v[maxn] , f[maxn] , sum[maxn<<2] , add[maxn<<2] , idx;
	void dfs1(int x , int fx)
	{
		f[x] = fx;
		dep[x] = dep[fx] + 1;
		sz[x] = 1;
		for(int i = head[x] ; i ; i = e[i].next){
			int v = e[i].to;
			if(v == fx)	continue;
			dfs1(v , x);
			sz[x] += sz[v];
			if(sz[v] > sz[hs[x]])	hs[x] = v;
		}
	}
	void dfs2(int x , int topV)
	{
		top[x] = topV;
		id[x] = ++idx;
		v[id[x]] = val[x];
		if(!hs[x]) return;
		dfs2(hs[x] , topV);
		for(int i = head[x] ; i ; i = e[i].next){
			int v = e[i].to;
			if(v == f[x] || v == hs[x])	continue;
			dfs2(v , v);
		}
	}
	inline void pushup(int p){
		sum[p] = sum[ls(p)] + sum[rs(p)];
	}
	inline void pushdown(int p , int ln , int rn){
		if(add[p]){
			add[ls(p)] += add[p] , add[rs(p)] += add[p];
			sum[ls(p)] += ln * add[p] , sum[rs(p)] += rn * add[p];
			add[p] = 0;
		}
	}
	void update(int pos , int l , int r , int p , int v)
	{
		if(l == r){
			sum[p] += v;
			return;
		}
		int mid = l + r >> 1;
		if(pos <= mid)	update(pos , l , mid , ls(p) , v);
		else update(pos , mid + 1, r , rs(p) , v);
		pushup(p);	
	}
	int query(int L , int R , int l , int r , int p)
	{
		if(L <= l && r <= R){
			return sum[p];
		}
		int mid = l + r >> 1 , ans = 0;
		if(L <= mid)	ans += query(L , R , l , mid , ls(p));
		if(R > mid) ans += query(L , R , mid + 1, r , rs(p));
		return ans;
	}
	int qLink(int x , int y)
	{
		int ans = 0;
		while(top[x] != top[y])
		{
			if(dep[top[x]] < dep[top[y]]) std::swap(x,y);
			ans += query(id[top[x]] , id[x] , 1 , n , 1);
			x = f[top[x]];
		}
		if(dep[x] < dep[y]) std::swap(x,y);
		ans += query(id[y] , id[x] , 1 , n , 1);
		return ans;
	}
	inline void print()
	{
		puts("ID");
		for(int i = 1 ; i <= n ; ++i)
			printf("%d ",id[i]);
		puts("SZ");
		for(int i = 1 ; i <= n ; ++i)
			printf("%d ",sz[i]);
		puts("top");
		for(int i = 1 ; i <= n ; ++i)
			printf("%d ",top[i]);
	}
}tr;
inline void add(int x , int y)
{
	e[++cnt].next = head[x] ;
	e[cnt].to = y;
	head[x] = cnt;
}
int main()
{
	scanf("%d",&n);
	int x , y;
	for(int i = 1 ; i <= n-1 ; ++i)
		scanf("%d%d",&x,&y) , add(x,y) , add(y,x);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&val[i]);
	tr.dfs1(1,1);
	tr.dfs2(1,1);
	for(int i = 1 ; i <= n ; ++i){
		printf("%d\n",tr.qLink(1,val[i]));
		tr.update(tr.id[val[i]] , 1 , n , 1 , 1);
	}
}

注意变量名不要太相似，容易写错，比如p什么的，以后还是用node吧。