bef-> NO.29

Veröffentlicht am

[USACO10NOV]巧克力牛奶Chocolate Milk

题目描述

Farmer John’s milk production and shipping system is an intricate one! He uses milking machines for his many cows to harvest the milk that then flows into pipes.

Each of these pipes connects a milking machine to a joint, where it might be joined by exactly one more pipe (the milk flowing through both pipes merges). The milk then flows through additional pipes (which all start and end at joints) until it reaches the long central pipe connecting to the distribution room.

The milk then goes through a reverse process of splitting at various joints until it is flows into milk tanks that are picked up and taken to market.

Farmer John notices that there is at most one way for milk to travel from one joint to any other joint. Furthermore, since Farmer John is an efficient man by nature, he has made sure that milk will flow through each and every pipe; in other words, no pipe is unneeded.

If we think of a milking machine, joint, or milk tank as a node, there are N (2 <= N <= 100,000) nodes in total (and N-1 pipes

connecting them). The input describes each pipe as an ordered pair of nodes, A_i (1 <= A_i <= N) and B_i (1 <= B_i <= N; A_i < B_i) indicating milk flows from node A_i to node B_i. If there is no pipe coming in to A_i, it is a milking machine. Likewise, if no pipe goes out from B_i, it is a tank.

The demand of chocolate milk has skyrocketed in recent months, and Farmer John wants to install a chocolate inserter at one of the joints so he can create delicious chocolate milk for customers.

Being thrifty, Farmer John has only bought one chocolate inserter, so he wants to place it at a joint through which all the milk passes. He knows that such a joint exists.

Help Farmer John find all the possible places he can install the chocolate inserter. (Note that Farmer John cannot install the chocolate inserter at the same location as a milking machine.)

As an example, consider a milking setup like this one:

1
2
3
4
5
6
7
1 ----+
      |
      v
2 --> 4 --> 6 ------------------> 7 --> 8
            ^                     |
            |                     |
3 --> 5 ----+                     + --> 9

Visual inspection shows that the chocolate inserter can be installed at either joint 6 or 7, as all milk flows through those joints.

农民约翰的牛奶生产和运输系统是极其复杂的！他用挤奶机为他的许多奶牛收获牛奶，然后流入管道。

每一个管道连接挤奶机到一个节点，在那里它可能会加入一个管道（牛奶流过两个管道合并）。然后，牛奶流通过额外的管道（所有的开始点和结束点在其它节点上的），直到它到达一个关键的节点。

牛奶然后经过一个反向的过程，在不同的关节分裂，直到它流入牛奶罐被拾起，并送往市场。

农场主约翰注意到，牛奶从一个关节到另一个关节的方式最多。此外，由于农民约翰本质上是一个能干的人，他已经确信，牛奶会流通过每个管道；换句话说，没有管道是不必要的。

如果我们认为挤奶机，节点，或牛奶罐都看作一个节点，有N (2 <= N <= 100,000)节点总数（N-1个管道连接它们）。

输入描述每个管节点的有序对，A_i（1 <= A_i <= N）和B_i（1 <= B_i <= N；A_i < B_i）表示牛奶从A_i流向B_i。如果A_i入度为0，它是一个挤奶机。同样，B_i出度为0，它是一个牛奶罐。

巧克力牛奶的需求已经在最近几个月急剧增加，农民约翰想安装一个巧克力插件在一个节点上，保证他能为顾客创造美味的巧克力牛奶。

为了节俭，农民约翰只买了一个巧克力插件，所以他想把它安在一个牛奶都经过的节点上。他知道这样的节点存在。

帮助农民约翰找到所有可能的地方，他将在那儿安装巧克力的插件。（注：农民约翰巧克力插件不能安装在一个挤奶机上。）

1
2
3
4
5
6
7
1 ----+
      |
      v
2 --> 4 --> 6 ------------------> 7 --> 8
            ^                     |
            |                     |
3 --> 5 ----+                     + --> 9

巧克力插件可以安装在6或7上，所有牛奶流经这些节点。

输入输出格式

输入格式：

* Line 1: A single integer: N

* Lines 2..N: Line i+1 contains two space-separated integers that describe a pipe’s connectivity: A_i and B_i

第1行：一个整数：N

2到N行：包含空格分隔的两个整数描述管道的连接：A_i和B_i

输出格式：

* Lines 1..??: Integers, one per line and in ascending order, each denoting a possible joint at which to install the chocolate inserter.

第1行到？？行：每行一个整数，升序排列，每个表示可以安装巧克力插件的节点。

输入输出样例

输入样例#1：

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

输出样例#1：

1
2
6 
7

题解

这题我想了个乱搞做法结果没想到是正解23333

虽然从来没学过网络流但是我看完这道题莫名其妙的想到了最大流这个我都不知道概念的东西（跟最大流没有任何关系）

考虑一种类似模拟的算法：
将每台挤奶机设置一个流量，拓扑排序后平均转移流量，或者怎么分都行（差不多那种。。）因为我们只关心最大汇聚的流量是多少。

然后就交了10多遍轻松AC

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#define maxn 100005
int  n , x , y , d[maxn];
long long flow[maxn];
bool vis[maxn];
std::vector<int> e[maxn];
std::queue<int> q;
int main()
{
//	freopen("flow.in","r",stdin);
    scanf("%d",&n);
    for(int i = 1 ; i <= n-1 ; ++i){
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
        ++d[y];
    }
    for(int i = 1 ; i <= n ; ++i)
        if(!d[i])	q.push(i) , flow[i] = 100000 , vis[i] = true;
    while(!q.empty()){
        int k = q.front();
        q.pop();
        if(!e[k].size()) continue;
        long long rem = flow[k] - flow[k] / e[k].size();
//        printf("%d %d %lld\n",e[k].size() , rem , flow[k]);
        if(e[k].size() > 1) flow[e[k][0]] += rem / 2 , flow[e[k][1]] += rem - rem / 2;
        else flow[e[k][0]] += rem;
        for(int i = 0 ; i < e[k].size() ; ++i){
            --d[e[k][i]];
            if(!d[e[k][i]])	q.push(e[k][i]);
            flow[e[k][i]] += flow[k] / e[k].size();
        }
    }
    std::queue<int> ans;
    long long maxx = -0x7fffff;
    for(int i = 1 ; i <= n ; ++i){
        if(flow[i] > maxx){
            maxx = flow[i];
            while(!q.empty())	q.pop();
            q.push(i);
        }
        else if(flow[i] == maxx){
            q.push(i);
        }
    }
    while(!q.empty()) {
    	if(vis[q.front()]) {
    		q.pop()  ; continue;
		}
    	printf("%d\n",q.front()) , q.pop();
	}
        
}

二分图匹配

找出给定二分图最大图匹配。（四种图匹配中最简单一种了）

Dinic是可以的，不过联赛前不打算学这种高级算法。

使用匈牙利算法解决。

首先引入增广路概念：已匹配的边和未匹配的边在一条长度为奇数的路径中交替出现，且端点是两个未匹配的点。这条路径即是这组边集的增广路。

不断寻找增广路并取反，直到图中没有任何增广路即最大二分图匹配（berge theorem）

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
#define maxn 1005
int  n , cnt , m , match[maxn] , ans ,x, y , enums;
bool vis[maxn] , g[maxn][maxn];

bool DFS(int x)
{
	for(int i = 1 ; i <= m ; ++i){
		if(!g[x][i] || vis[i])	continue;
		vis[i] = true;
		if(!match[i] || DFS(match[i])){
			match[i] = x ;
			return true;
		}
	}
	return false;
}
int main()
{
//	freopen("graph.in","r",stdin);
	scanf("%d%d%d",&n,&m,&enums);
	for(int i = 1 ; i <= enums ; ++i){
		scanf("%d%d",&x,&y) ;
 		if (x<=n&&y<=m)
			g[x][y] = true;
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		std::memset(vis,false,sizeof(vis));
		if(DFS(i))	++ans;
	}
	printf("%d",ans);
}

这是一个较为低效的算法，复杂度为

n与m为二分图的两边的点。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
#define maxn 1005
int  n , cnt , m , match[maxn] , ans ,x, y , enums;
bool vis[maxn] , g[maxn][maxn];

bool DFS(int x)
{
	for(int i = 1 ; i <= m ; ++i){
		if(!g[x][i] || vis[i])	continue;
		vis[i] = true;
		if(!match[i] || DFS(match[i])){
			match[i] = x ;
			return true;
		}
	}
	return false;
}
int main()
{
//	freopen("graph.in","r",stdin);
	scanf("%d%d%d",&n,&m,&enums);
	for(int i = 1 ; i <= enums ; ++i){
		scanf("%d%d",&x,&y) ;
 		if (x<=n&&y<=m)
			g[x][y] = true;
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		std::memset(vis,false,sizeof(vis));
		if(DFS(i))	++ans;
	}
	printf("%d",ans);
}

[USACO15JAN]踩踏Stampede

题目描述

Farmer John’s N cows (1 <= N <= 50,000) appear to be stampeding along the road at the front of FJ’s farm, but they are actually just running in a foot race to see which cow is the fastest.

Viewed from above, each cow is represented by a unit-length horizontal line segment, specified by the coordinates of its left corner point at time t=0. For example, (-3,6) would specify a cow who at time t=0 is represented by the segment from (-3,6) to (-2,6). Each cow is moving to the right (in the +x direction) at a certain rate, specified by the integer amount of time it takes her to move 1 unit to the right.

FJ is not particularly thrilled that his cows are outside running instead of in the barn producing milk. He plans to admonish them with a stern lecture after the race ends. In order to determine which of his cows are participating in the race, FJ situates himself at (0,0) and looks along a ray extending in the +y direction. As the race unfolds, FJ sees a cow if she is ever the first cow visible along this ray. That is, a cow might not be visible if another cow is “in front” of her during the entire time she crosses FJ’s line of sight.

Please compute the number of cows FJ can see during the entire race.

DJ站在原点上向y轴正半轴看，然后有一群奶牛从他眼前飞过。这些奶牛初始都在第二象限，尾巴在(Xi,Yi)，头在(Xi+1,Yi)，每Ci秒向右走一个单位。 DJ能看见一匹奶牛当且仅当它身体任意某部位x坐标为0时，没有其它y坐标小于此奶牛的奶牛身体某部位x坐标为0。 问DJ能看见多少奶牛？

输入输出格式

输入格式：

INPUT: (file stampede.in)

The first line of the input contains N. Each of the following N lines describes a cow with three integers x y r, corresponding to a cow whose left endpoint is at (x,y) at time t=0, moving to the right at a continuous speed of 1 unit of distance every r units of time. The value of x is in the range -1000..-1, the value of y is in the range 1..1,000,000 (and distinct for every cow, to prevent any possible collisions), and the value of r is in the range 1..1,000,000.

输出格式：

OUTPUT: (file stampede.out)

A single integer, specifying the number of cows FJ can see during the

entire race (from t=0 onward).

输入输出样例

输入样例#1：

1
2
3
4
3 
-2 1 3 
-3 2 3 
-5 100 1

输出样例#1：

1
2

说明

SOLUTION NOTES:

FJ can see cows 1 and 2 but not cow 3.

题解

没想到还左闭右开。。。我怎么读题都没读出这个意思来。

总之思路就是离散化+扫描线+线段树。也就是我们算出每头牛的时间区间，然后从下到上线段覆盖完事了。

不卡我边界我就一边AC了嘤嘤嘤

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 50005
struct Node{
	int l , r , v;
	bool operator < (const Node& x)const{
		return v < x.v;
	}
}p[maxn];
struct Map{
	int v , type , k;
	bool operator < (const Map& x)const{
		return v < x.v;
	} 
}g[maxn*2];
int n , x , y , z , tot , ans;
struct SegmentTree
{
	int sum[maxn<<3] , add[maxn<<3];
	#define ls(x) (x<<1)
	#define rs(x) (x<<1|1)
	inline void pushup(int Node){
		sum[Node] = sum[ls(Node)] + sum[rs(Node)];
	}
	inline void pushdown(int Node , int ln , int rn)
	{
		if(add[Node]){
			sum[ls(Node)] = ln;
			sum[rs(Node)] = rn;
			add[ls(Node)] = add[rs(Node)] = 1;
			add[Node] = 0;
		}
	}
	void update(int L , int R , int l , int r , int Node){
		if(L <= l && r <= R){
			sum[Node] = r - l + 1;
			add[Node] = 1;
			return;
		}
		int mid = l + r >> 1;
		pushdown(Node , mid - l + 1 , r - mid);
		if(L <= mid)	update(L , R , l , mid , ls(Node));
		if(R > mid)		update(L , R , mid + 1 , r , rs(Node));
		pushup(Node);
	}
	int query(int L , int R , int l , int r , int Node){
		if(L <= l && r <= R){
			return sum[Node];
		}
		int mid = l + r >> 1 , ans = 0;
		pushdown(Node , mid - l + 1 , r - mid);
		if(L <= mid)	ans += query(L , R , l , mid , ls(Node));
		if(R > mid)		ans += query(L , R , mid + 1 , r , rs(Node));
		return ans;
	}
}tr;
int main(){
//	freopen("stamp.in","r",stdin);
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i){
		scanf("%d%d%d",&x,&y,&z);
		p[i].v = y;
		p[i].l = (-(1+x)) * z;
		p[i].r = p[i].l + z; 
	}
	std::sort(p+1,p+n+1);
	int num = 0;
	for(int i = 1 ; i <= n ; ++i){
		g[++num].v = p[i].l , g[num].type = 0 , g[num].k = i;
		g[++num].v = p[i].r , g[num].type = 1 , g[num].k = i;
	}
	std::sort(g+1,g+num+1);
	g[0].v = 1934537;
	for(int i = 1 ; i <= num ; ++i){
		if(g[i].type){
			if(g[i].v == g[i-1].v){
				p[g[i].k].r = tot;
			}
			else p[g[i].k].r = ++tot;
		}
		else{
			if(g[i].v == g[i-1].v){
				p[g[i].k].l = tot;
			}
			else p[g[i].k].l = ++tot;
		}
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		int l = p[i].l , r = p[i].r;
		int cur = tr.query(l , r - 1, 1 , tot , 1);
		if(cur != r - l)	++ans; 
		tr.update(l , r - 1 , 1 , tot , 1);
	}
	printf("%d",ans);
}

[AHOI2008]紧急集合 / 聚会

题目描述

欢乐岛上有个非常好玩的游戏，叫做“紧急集合”。在岛上分散有N个等待点，有N-1条道路连接着它们，每一条道路都连接某两个等待点，且通过这些道路可以走遍所有的等待点，通过道路从一个点到另一个点要花费一个游戏币。

参加游戏的人三人一组，开始的时候，所有人员均任意分散在各个等待点上（每个点同时允许多个人等待），每个人均带有足够多的游戏币（用于支付使用道路的花费）、地图（标明等待点之间道路连接的情况）以及对话机（用于和同组的成员联系）。当集合号吹响后，每组成员之间迅速联系，了解到自己组所有成员所在的等待点后，迅速在N个等待点中确定一个集结点，组内所有成员将在该集合点集合，集合所用花费最少的组将是游戏的赢家。

小可可和他的朋友邀请你一起参加这个游戏，由你来选择集合点，聪明的你能够完成这个任务，帮助小可可赢得游戏吗？

输入输出格式

输入格式：

第一行两个正整数N和M（N<=500000，M<=500000），之间用一个空格隔开。分别表示等待点的个数（等待点也从1到N进行编号）和获奖所需要完成集合的次数。 随后有N-1行，每行用两个正整数A和B，之间用一个空格隔开，表示编号为A和编号为B的等待点之间有一条路。 接着还有M行，每行用三个正整数表示某次集合前小可可、小可可的朋友以及你所在等待点的编号。

输出格式：

一共有M行，每行两个数P,C，用一个空格隔开。其中第i行表示第i次集合点选择在编号为P的等待点，集合总共的花费是C个游戏币。

输入输出样例

输入样例#1：

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

输出样例#1：

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

说明

提示：

40%的数据中N<=2000，M<=2000
100%的数据中，N<=500000，M<=500000

题解

一道贪心结论题。主要考察对LCA的理解，大概NOIp D1T2难度或者D2T1

显然当三点LCA相同时没有什么优化，当有且仅有一个LCA比较低，那就选这个点，最后容斥一下发现答案对于

为

考虑数据范围比较大（HPD好），HPD LCA即可。

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 500005
int head[maxn] , dep[maxn] , f[maxn] , top[maxn] , hs[maxn] , sz[maxn] , n , m , cnt;
struct edge{
    int next , to;
}e[maxn*2];
inline void add(int x , int y)
{
    e[++cnt].next = head[x];
    e[cnt].to = y;
    head[x] = cnt;
}
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){
        if(e[i].to == fx)	continue;
        dfs1(e[i].to , x);
        sz[x] += sz[e[i].to];
        if(sz[e[i].to] > sz[hs[x]]) hs[x] = e[i].to;
    }
}
void dfs2(int x , int topv)
{
    top[x] = topv;
    if(!hs[x])	return;
    dfs2(hs[x] , topv);
    for(int i = head[x] ; i ; i = e[i].next){
        if(e[i].to == f[x] || e[i].to == hs[x])		continue;
        dfs2(e[i].to , e[i].to);
    }
}
int LCA(int x , int y)
{
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])	std::swap(x,y);
        x = f[top[x]];
    }
    if(dep[x] > dep[y])	std::swap(x,y);
    return x;
}
int main()
{
    scanf("%d%d",&n,&m);
    int x , y;
    for(int i = 1 ; i <= n - 1 ; ++i)
        scanf("%d%d",&x,&y) , add(x,y) , add(y,x);
    dep[1] = -1; 
    dfs1(1,1);
    dfs2(1,1);
    int z;
    for(int i = 1 ; i <= m ; ++i){
        scanf("%d%d%d",&x,&y,&z);
        int f1 = LCA(x,y) , f2 = LCA(y,z) , f3 = LCA(x,z) , f = 0;
        if(f1 == f2 && f2 == f3){
            printf("%d %d\n",f1,dep[x] + dep[y] + dep[z] - 3 * dep[f1]);
            continue;
        }
        if(dep[f1] > dep[f])	f = f1;
        if(dep[f2] > dep[f])	f = f2;
        if(dep[f3] > dep[f])	f = f3;
        printf("%d %d\n",f,dep[x] + dep[y] + dep[z] - dep[f1] - dep[f2] - dep[f3]);

    }
}