bef-> NO.15

Veröffentlicht am

高斯消元法

感觉这个算法没什么可说的，其实就是将每个未知数系数绝对值最大那一行将这个未知数当成主元，按顺序消去其他行，最后得到上三角矩阵后不断回带即可。

不过似乎还有点问题，以后再调先这样用着吧（原理肯定是对的了）

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
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#define maxn 555
const double eps = 1e-8;
double A[maxn][maxn];
bool flag;
int  n ;
void Gauss() {
    for(int i = 0; i < n; i ++) {//for each row(varieble)
        int r = i;
        for(int j = i + 1; j < n; j ++)
            if(fabs(A[j][i]) > fabs(A[r][i])) r = j;
        if(r != i) for(int j = 0; j <= n; j ++) std :: swap(A[r][j], A[i][j]);
		for(int j = n; j >= i; j --) {
            for(int k = i + 1; k < n; k ++)
                A[k][j] -= A[k][i] / A[i][i] * A[i][j];
        }
    }
    
    
    for(int i = n - 1; i >= 0; i --) {
        for(int j = i + 1; j < n; j ++){
        	A[i][n] -= A[j][n] * A[i][j];
		}
		if(fabs(A[i][i]) < eps && fabs(A[i][n]) > eps){
			puts("-1") ; 
			flag = true; return;
		}
		else if(fabs(A[i][n]) < eps){
			puts("0");
			flag = true;	return;
		}
        A[i][n] /= A[i][i];
    }
}
int main()
{
	scanf("%d",&n);
	for(int i = 0 ; i < n ; ++i)
		for(int j = 0 ; j <= n ; ++j)	
			scanf("%lf",&A[i][j]);
	Gauss();
	if(flag) return 0;
	for(int i = 0 ; i < n ; ++i)
		printf("x%d=%.2lf\n",i+1,A[i][n]);
}

判断无穷解和负解还有点问题。

注意如果当前主元系数为0，就要跳过，否则会出错！

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
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#define maxn 555
const double eps = 1e-8;
double A[maxn][maxn];
bool flag;
int  n ;
void Gauss() {
    for(int i = 0; i < n; i ++) {//for each row(varieble)
        int r = i;
        for(int j = i + 1; j < n; j ++)
            if(fabs(A[j][i]) > fabs(A[r][i])) r = j;
        if(r != i) for(int j = 0; j <= n; j ++) std :: swap(A[r][j], A[i][j]);
    	if(fabs(A[i][i]) < eps)	continue;
		for(int j = n; j >= i; j --) {
            for(int k = i + 1; k < n; k ++)
                A[k][j] -= A[k][i] / A[i][i] * A[i][j];
        }
    }
    puts("The Matrix now :");
    for(int i = 0 ; i < n ; ++i)
    {
    	for(int j = 0 ; j <= n ; ++j)
    		printf("%.2lf "  , A[i][j]);
    	putchar(10);
	}
    for(int i = n - 1; i >= 0; i --) {
        for(int j = i + 1; j < n; j ++){
        	A[i][n] -= A[j][n] * A[i][j];
		}
		if(fabs(A[i][i]) < eps && fabs(A[i][n]) > eps){
			puts("-1") ; 
			flag = true; return;
		}
		if(fabs(A[i][n]) < eps && fabs(A[i][i]) < eps){
			puts("0");
			flag = true;	return;
		}
        A[i][n] /= A[i][i];
    }
}
int main()
{
	scanf("%d",&n);
	for(int i = 0 ; i < n ; ++i)
		for(int j = 0 ; j <= n ; ++j)	
			scanf("%lf",&A[i][j]);
	Gauss();
	if(flag) return 0;
	for(int i = 0 ; i < n ; ++i)
		printf("x%d=%.2lf\n",i+1,A[i][n]);
}

90分代码

在回带之前加了奇怪的判断就过了，不过一般情况下似乎不用吧

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
// luogu-judger-enable-o2
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#define maxn 555
const double eps = 1e-8;
double A[maxn][maxn];
bool flag;
int  n ;
void Gauss() {
    for(int i = 0; i < n; i ++) {//for each row(varieble)
        int r = i;
        for(int j = i + 1; j < n; j ++)
            if(fabs(A[j][i]) > fabs(A[r][i])) r = j;
        if(r != i) for(int j = 0; j <= n; j ++) std :: swap(A[r][j], A[i][j]);
    	if(fabs(A[i][i]) < eps)	continue;
        for(int j = n; j >= i; j --) {
            for(int k = i + 1; k < n; k ++)
                A[k][j] -= A[k][i] / A[i][i] * A[i][j];
        }
    }
    

    for(int i = 0 ; i < n ; ++i)
	{
		bool IF = false , ALL = false;
		for(int j = 0 ; j < n ; ++j)
			if(fabs(A[i][j]) > eps)
				IF = true;
		if(fabs(A[i][n]) > eps)
			ALL = true;
		if(!IF){
			if(!ALL) {
				puts("0"); flag = true; return;
			}
			else {
				puts("-1") ; flag = true ; return;
			}
			
		}
	}
    
    for(int i = n - 1; i >= 0; i --) {
        for(int j = i + 1; j < n; j ++){
        	A[i][n] -= A[j][n] * A[i][j];
        }
        if(fabs(A[i][i]) < eps){
            if(fabs(A[i][n]) < eps){
                puts("0") , flag = true;
                return;
            }
            else if(fabs(A[i][n]) > eps){//ax = b 
                puts("-1") , flag = true;
                return;
            }
        }
        A[i][n] /= A[i][i];
    }
    	

    
}
int main()
{
    scanf("%d",&n);
    for(int i = 0 ; i < n ; ++i)
        for(int j = 0 ; j <= n ; ++j)	
            scanf("%lf",&A[i][j]);
    Gauss();
    if(flag) return 0;
    for(int i = 0 ; i < n ; ++i)
        printf("x%d=%.2lf\n",i+1,A[i][n]);
}

[USACO08OCT]牧场散步Pasture Walking

题目描述

The N cows (2 <= N <= 1,000) conveniently numbered 1..N are grazing among the N pastures also conveniently numbered 1..N. Most conveniently of all, cow i is grazing in pasture i.

Some pairs of pastures are connected by one of N-1 bidirectional walkways that the cows can traverse. Walkway i connects pastures A_i and B_i (1 <= A_i <= N; 1 <= B_i <= N) and has a length of L_i (1 <= L_i <= 10,000).

The walkways are set up in such a way that between any two distinct pastures, there is exactly one path of walkways that travels between them. Thus, the walkways form a tree.

The cows are very social and wish to visit each other often. Ever in a hurry, they want you to help them schedule their visits by computing the lengths of the paths between 1 <= L_i <= 10,000 pairs of pastures (each pair given as a query p1,p2 (1 <= p1 <= N; 1 <= p2 <= N).

POINTS: 200

有N(2<=N<=1000)头奶牛，编号为1到W，它们正在同样编号为1到N的牧场上行走.为了方 便，我们假设编号为i的牛恰好在第i号牧场上.

有一些牧场间每两个牧场用一条双向道路相连，道路总共有N - 1条，奶牛可以在这些道路 上行走.第i条道路把第Ai个牧场和第Bi个牧场连了起来(1 <= A_i <= N; 1 <= B_i <= N)，而它的长度 是 1 <= L_i <= 10,000.在任意两个牧场间，有且仅有一条由若干道路组成的路径相连.也就是说，所有的道路构成了一棵树.

奶牛们十分希望经常互相见面.它们十分着急，所以希望你帮助它们计划它们的行程，你只 需要计算出Q(1 < Q < 1000)对点之间的路径长度•每对点以一个询问p1,p2 (1 <= p1 <= N; 1 <= p2 <= N). 的形式给出.

输入输出格式

输入格式：

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

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

* Lines N+1..N+Q: Each line contains two space-separated integers representing two distinct pastures between which the cows wish to travel: p1 and p2

输出格式：

* Lines 1..Q: Line i contains the length of the path between the two pastures in query i.

输入输出样例

输入样例#1：

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

输出样例#1：

1
2
2 
7

说明

Query 1: The walkway between pastures 1 and 2 has length 2.

Query 2: Travel through the walkway between pastures 3 and 4, then the one between 4 and 1, and finally the one between 1 and 2, for a total length of 7.

题解

按照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
72
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
int head[maxn] , cnt , n , m , s[maxn];
struct edge{
	int next , to , dis;
}e[maxn*2];
inline void add(int x , int y , int d)
{
	e[++cnt].next = head[x];
	e[cnt].to = y;
	e[cnt].dis = d;
	head[x] = cnt;
}
struct HPD{
	int  f[maxn] , top[maxn] , dep[maxn] , hs[maxn], sz[maxn];
	void dfs1(int x , int fx)
	{
		dep[x] = dep[fx] + 1;
		f[x] = fx;
		sz[x] = 1;
		int hson = 0;
		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[hson])	hson = e[i].to;
		}
		hs[x] = hson;
	}
	void dfs2(int x , int tp)
	{
		top[x] = tp;
		if(!hs[x]) return;
		dfs2(hs[x], tp);
		for(int i = head[x] ; i ; i = e[i].next)
			if(e[i].to != f[x] && e[i].to != hs[x])
				dfs2(e[i].to , e[i].to);
				
	}
	inline 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]];
		}
		return dep[x] > dep[y] ? y : x;
	}
} tr;
void dfs(int x , int fx , int dis)
{
	s[x] = s[fx] + dis;
	for(int i = head[x] ;  i ; i = e[i].next)
		if(e[i].to != fx)
			dfs(e[i].to , x , e[i].dis);
}
int main()
{
	scanf("%d%d",&n,&m);
	int x , y , d;
	for(int i = 1 ; i <= n - 1 ; ++i)
		scanf("%d%d%d",&x,&y,&d) , add(x,y,d) , add(y,x,d);
	dfs(1,1,0);
	tr.dfs1(1,1);
	tr.dfs2(1,1);
	for(int i = 1 ; i <= m ; ++i)
		scanf("%d%d",&x,&y) , printf("%d\n",s[x] + s[y] - 2 * s[tr.LCA(x,y)]);
}

以后不可能写倍增LCA的，这辈子不可能的。

今天下午和晚上主要刷USACO和POI中蓝题及以下难度，更有挑战性的题目放到联赛以后去做吧，得保证一下基础题量了。

[USACO10JAN]奶酪塔Cheese Towers

题目描述

FJ要建一个奶酪塔，高度最大为T。他有N种奶酪。第i种奶酪的高度为Hi（一定是5的倍数），价值为Vi。一块高度Hi>=K的奶酪被称为大奶酪，一个奶酪如果在它上方有大奶酪（如果有多块就只算一次），它的高度Hi就会变成原来的4/5.。FJ想让他的奶酪塔价值和最大。请你求出这个最大值。

输入格式：

第一行三个数N,T,K，意义如上所述。 接下来n行，每行两个数V_i,h_i（注意顺序）

输出格式：

奶酪塔的最大价值

题目描述

Farmer John wants to save some blocks of his cows’ delicious Wisconsin cheese varieties in his cellar for the coming winter. He has room for one tower of cheese in his cellar, and that tower’s height can be at most T (1 <= T <= 1,000). The cows have provided him with a virtually unlimited number of blocks of each kind of N (1 <= N <= 100) different types of cheese (conveniently numbered 1..N). He’d like to store (subject to the constraints of height) the most

valuable set of blocks he possibly can. The cows will sell the rest to support the orphan calves association.

Each block of the i-th type of cheese has some value V_i (1 <= V_i <= 1,000,000) and some height H_i (5 <= H_i <= T), which is always a multiple of 5.

Cheese compresses. A block of cheese that has height greater than or equal to K (1 <= K <= T) is considered ‘large’ and will crush any and all of the cheese blocks (even other large ones) located below it in the tower. A crushed block of cheese doesn’t lose any value, but its height reduces to just 4/5 of its old height. Because the height of a block of cheese is always a multiple of 5, the height of a crushed block of cheese will always be an integer. A block of cheese is either crushed or not crushed; having multiple large blocks above it does not crush it more. Only tall blocks of cheese crush other blocks; aggregate height of a tower does not affect whether a block is crushed or not.

What is the total value of the best cheese tower FJ can construct?

Consider, for example, a cheese tower whose maximum height can be 53 to be build from three types of cheese blocks. Large blocks are those that are greater than or equal to 25. Below is a chart of the values and heights of the various cheese blocks he stacks:

Type Value Height

1 100 25

2 20 5

3 40 10

FJ constructs the following tower:

Type Height Value

top -> [1] 25 100

1
2
3
4
[2]    4     20   <- crushed by [1] above 
[3]    8     40   <- crushed by [1] above 
[3]    8     40   <- crushed by [1] above 
bottom -> [3]    8     40   <- crushed by [1] above

The topmost cheese block is so large that the blocks below it are crushed. The total height is:

1
2
3
4
5
25 + 4 + 8 + 8 + 8 = 53 
The total height does not exceed 53 and thus is 'legal'. The total value is: 
100 + 20 + 40 + 40 + 40 = 240. 
This is the best tower for this particular set of cheese blocks. 
要建一个奶酪塔，高度最大为T。他有N块奶酪。第i块高度为Hi（一定是5的倍数），价值为Vi。一块高度>=K的奶酪被称为大奶酪，一个奶酪如果在它上方有大奶酪（多块只算一次），它的高度就会变成原来的4/5.。 很显然John想让他的奶酪他价值和最大。求这个最大值。

输入输出格式

输入格式：

* Line 1: Three space-separated integers: N, T, and K

* Lines 2..N+1: Line i+1 contains two space separated integers: V_i and H_i

输出格式：

* Line 1: The value of the best tower FJ can build

输入输出样例

输入样例#1：

1
2
3
4
3 53 25 
100 25 
20 5 
40 10

输出样例#1：

1
240

题解

看了看题，觉得题挺简单的，我做背包的时候直接把大于k的转移的容量乘5/4不就行了，然而后来想了想这样会多压缩。。。所以结果偏大。

再思考下题意可以发现一个简单的性质：一块大奶酪放在顶端一定是最优的。这样我们就可以让所有奶酪做普通的完全背包，然后枚举大于k的奶酪来更新答案。

绿题还看题解

注意是小于等于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 <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxm 10005
#define maxn 105
int f[maxm] , n , m , k; 
struct Node{
	int v , w;
	bool operator < (const Node& x) const{
		return w < x.w;
	}
}p[maxn];
int main()
{
//	freopen("Cheese.in","r",stdin);
	scanf("%d%d%d",&n,&m,&k);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d%d",&p[i].v,&p[i].w);
	std::memset(f,-20,sizeof(f));
	f[0] = 0;
	std::sort(p+1,p+n+1);
	for(int i = 1 ; i <= n ; ++i)
		for(int j = p[i].w ; j <= 5*m/4 ; ++j)
			f[j] = std::max(f[j-p[i].w] + p[i].v , f[j]);
	int ans = -0x7fffffff;
	for(int i = 1 ; i <= m ; ++i)
		ans = std::max(ans , f[i]);
	for(int i = 1 ; i <= n ; ++i)
	{
		if(p[i].w < k) 	continue;
		for(int j = p[i].w ; j <= m ; ++j)
			ans = std::max(ans , f[5 * (j-p[i].w)/4] + p[i].v);
	}
	printf("%d",ans);
}

[USACO13JAN]画栅栏Painting the Fence

题目描述

Farmer John has devised a brilliant method to paint the long fence next to his barn (think of the fence as a one-dimensional number line). He simply attaches a paint brush to his favorite cow Bessie, and then retires to drink a cold glass of water as Bessie walks back and forth across the fence, applying paint to any segment of the fence that she walks past.

Bessie starts at position 0 on the fence and follows a sequence of N moves (1 <= N <= 100,000). Example moves might be “10 L”, meaning Bessie moves 10 units to the left, or “15 R”, meaning Bessie moves 15 units to the right. Given a list of all of Bessie’s moves, FJ would like to know what area of the fence gets painted with at least K coats of paint. Bessie will move at most 1,000,000,000 units away from the origin during her walk.

Farmer John 想出了一个给牛棚旁的长围墙涂色的好方法。（为了简单起见，我们把围墙看做一维的数轴，每一个单位长度代表一块栅栏）他只是简单的把刷子蘸满颜料，系在他最喜欢的奶牛Bessie上，然后让Bessie来回地经过围墙，自己则在一旁喝一杯冰镇的凉水。（……-_-|||) Bessie 经过的所有围墙都会被涂上一层颜料。Bessie从围墙上的位置0出发，并将会进行N次移动(1 <= N <= 100,000)。比如说，“10 L”的意思就是Bessie向左移动了10个单位。再比如说“15 R”的意思就是Bessie向右移动了15个单位。给出一系列Bessie移动的清单。FJ 想知道有多少块栅栏涂上了至少K层涂料。注意：Bessie最多会移动到离原点1,000,000,000单位远的地方。

输入输出格式

输入格式：

* 第1行： 两个整数： N K

* 第2…N+1 行： 每一行都描述了Bessie的一次移动。 （比如说 “15 L”）

输出格式：

* 一个整数：被至少涂上K层涂料的栅栏数

（注意：输出的最后一定要输出换行符！否则会WA）

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
6 2 
2 R 
6 L 
1 R 
8 L 
1 R 
2 R

输出样例#1：

1
6

说明

PS1：来源：usaco jan silver P01 想看原题的请戳http://www.usaco.org/index.php?page=viewproblem2&cpid=226）

PS2：测试数据也可以在在http://www.usaco.org/index.php?page=jan13problems上下载，还可以看到题解（不过是英文的:-D）

PS3:如果有翻译的问题或题目的不理解，可以在问答后面留言的说。

题解

是个很傻逼的差分后前缀和，结果写了奇怪的毒瘤线段树。。

复赛这样是真的药丸，我敢说以我现在的状态去300分真的够呛。

想到算法却没法具体实现没有用，想到差分+扫描线却因为思考时的瑕疵浪费了1小时，有何用？

其实是扫描线基础题。、

将读入点记录属性，从小到大排序让扫描线从左往右（从大到小让扫描线从右到做也行。。）利用差分+树状数组维护线段覆盖时效性。

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 200005
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
int L[maxn] , R[maxn] , bit[maxn], n , tot , cnt , k , ans , x , rec[maxn] , b[maxn];
char ch;
struct Node{
    int v , type;
    bool operator < (const Node& x)const{
        if(v == x.v)	return type < x.type;//left forward
        return v < x.v;
    }
}p[maxn<<1];
inline int query(int x)
{
    int ans = 0;
    for(int i = x; i ; i -= (i & -i))
        ans += bit[i];
    return ans;
}
inline void update(int x , int v)
{
    for(int i = x ; i <= tot ; i += (i & -i))
        bit[i] += v;
}
int main()
{
    scanf("%d%d",&n,&k);
    int cur = 0;
    for(int i = 1 ; i <= n ; ++i)
    {
        
        ++cnt;
        p[cnt].v = cur;
        ++cnt;
        scanf("%d",&x);
        std::cin>>ch;
        p[cnt].v = cur + ((ch == 'L') ? (-x) : x);
        cur = p[cnt].v; 
        if(p[cnt].v < p[cnt-1].v)	std::swap(p[cnt].v , p[cnt-1].v);
        p[cnt-1].type = 0 , p[cnt].type = 1;

//		printf("%d %d\n",p[cnt-1].v , p[cnt].v);
    }
    std::sort(p+1,p+cnt+1);
    for(int i = 1 ; i <= cnt ; ++i)
        if(p[i].v == p[i-1].v)
            b[i] = tot;
        else b[i] = ++tot;
    update(b[1],1);
    int las = 0;
    for(int i = 2 ; i <= cnt ; ++i)
    {
        int num = query(b[i]-1);
        if(num >= k)	ans += p[i].v - las;
        if(p[i].type)	update(b[i] , -1);
        else update(b[i],1);
        las = p[i].v;
    }
    printf("%d",ans);
}
显然经过缜密思考后一遍就写对了。有时候错不是因为代码能力差，而是因为想的方法还不够好

Try to be better

[USACO12JAN]牛联盟Bovine Alliance

题目描述

Bessie and her bovine pals from nearby farms have finally decided that they are going to start connecting their farms together by trails in an effort to form an alliance against the farmers. The cows in each of the N (1 <= N <= 100,000) farms were initially instructed to build a trail to exactly one other farm, for a total of N trails. However months into the project only M (1 <= M < N) of these trails had actually been built.

Arguments between the farms over which farms already built a trail now threaten to split apart the cow alliance. To ease tension, Bessie wishes to calculate how many ways the M trails that exist so far could have been built. For example, if there is a trail connecting farms 3 and 4, then one possibility is that farm 3 built the trail, and the other possibility is that farm 4 built the trail. Help Bessie by calculating the number of different assignments of trails to the farms that built them, modulo 1,000,000,007. Two assignments are considered different if there is at least one trail built by a different farm in each assignment.

给出n个点m条边的图，现把点和边分组，每条边只能和相邻两点之一分在一组，点可以单独一组，问分组方案数。

输入输出格式

输入格式：

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

* Lines 2..1+M: Line i+1 describes the ith trail. Each line contains two space-separated integers u_i and v_i (1 <= u_i, v_i <= N, u_i != v_i) describing the pair of farms connected by the trail.

输出格式：

* Line 1: A single line containing the number of assignments of trails to farms, taken modulo 1,000,000,007. If no assignment satisfies the above conditions output 0.

输入输出样例

输入样例#1：

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

输出样例#1：

1
6

说明

Note that there can be two trails between the same pair of farms.

There are 6 possible assignments. Letting {a,b,c,d} mean that farm 1 builds trail a, farm 2 builds trail b, farm 3 builds trail c, and farm 4 builds trail d, the assignments are:

1
2
3
4
5
6
{2, 3, 4, 5} 
{2, 3, 5, 4} 
{1, 3, 4, 5} 
{1, 3, 5, 4} 
{1, 2, 4, 5} 
{1, 2, 5, 4}

题解

我们应该先想想该如何对联通块计数（最后答案肯定乘法原理就行啦）

5分钟以内不难想出一颗树有V（点数）种方案，简单环有两种，边再多就没有了。

然后写一个并查集，除了维护父亲之外还要维护本集合中的点数和边数，非常好写（并查集用的时候真好用！）

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define mod 1000000007
#define maxn 100005
int  tot[maxn] , n , m , f[maxn] , szv[maxn] , sze[maxn];
bool vis[maxn];
long long ans = 1;
int find(int x)
{
	if(f[x] != x)	return f[x] = find(f[x]);
	return f[x];
}
int main(){
	scanf("%d%d",&n,&m);
	int x , y;
	for(int i = 1 ; i <= n ; ++i)
		f[i] = i , szv[i] = 1 , sze[i] = 0;
	for(int i = 1 ; i <= m ; ++i)
	{
		scanf("%d%d",&x,&y);
		int fx = find(x) , fy = find(y);
		if(fx != fy){//merge
			szv[fx] += szv[fy];
			sze[fx] += sze[fy] + 1;
			f[fy] = f[fx];
			sze[fy] = szv[fy] = 0;
		}
		else{
			++sze[fx];
		}
	}
//	for(int i = 1 ; i <= n ; ++i)
//		printf("%d %d %d\n",find(i),szv[find(i)] , sze[find(i)]);
	for(int i = 1 ; i <= n ; ++i)
	{
		int fx = find(i);
		if(vis[fx])	continue;
		if(sze[fx] == szv[fx])	(ans *= 2) %= mod;
		else if(sze[fx] == szv[fx] - 1)	(ans *= szv[fx]) %= mod;
		else {
			puts("0");
			return 0;
		}
		vis[fx] = true;
	}
	printf("%lld",ans);
}

似乎写个树上背包写出了很睿智的错误（我把当前点父亲的边用作儿子的转移了，我说怎么一直错，画个图！！）

本质一个分组背包，不过注意背包的大小可以动态调整，否则虽然不会错但是会TLE（根据子树大小转移均摊算是

的）

P1273 有线电视网

题目描述

某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。

从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。

现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。

写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。

输入输出格式

输入格式：

输入文件的第一行包含两个用空格隔开的整数N和M，其中2≤N≤3000，1≤M≤N-1，N为整个有线电视网的结点总数，M为用户终端的数量。

第一个转播站即树的根结点编号为1，其他的转播站编号为2到N-M，用户终端编号为N-M+1到N。

接下来的N-M行每行表示—个转播站的数据，第i+1行表示第i个转播站的数据，其格式如下：

K A1 C1 A2 C2 … Ak Ck

K表示该转播站下接K个结点(转播站或用户)，每个结点对应一对整数A与C，A表示结点编号，C表示从当前转播站传输信号到结点A的费用。最后一行依次表示所有用户为观看比赛而准备支付的钱数。

输出格式：

输出文件仅一行，包含一个整数，表示上述问题所要求的最大用户数。

输入输出样例

输入样例#1：

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

输出样例#1：

1
2

说明

样例解释

img

如图所示，共有五个结点。结点①为根结点，即现场直播站，②为一个中转站，③④⑤为用户端，共M个，编号从N-M+1到N，他们为观看比赛分别准备的钱数为3、4、2，从结点①可以传送信号到结点②，费用为2，也可以传送信号到结点⑤，费用为3（第二行数据所示），从结点②可以传输信号到结点③，费用为2。也可传输信号到结点④，费用为3（第三行数据所示），如果要让所有用户（③④⑤）都能看上比赛，则信号传输的总费用为：

2+3+2+3=10，大于用户愿意支付的总费用3+4+2=9，有线电视网就亏本了，而只让③④两个用户看比赛就不亏本了。

选儿子必须选父亲（经过）。

显然是树上背包。

分组背包解决即可。（还有一个问题为什么当前点size可以动态更新啊。。）

upd：我懂了，原因很简单，因为到当前你最多选当前的size个点。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
#define maxn 3005
int head[maxn] , cnt , n , f[maxn][maxn] , m , v[maxn] , sz[maxn];
struct edge {
	int next , to , dis;
} e[maxn*2];
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;
}
void dfs(int x , int fx) {
	sz[x] = 1;
	if(x >= n - m + 1) {
		f[x][1] = v[x];
		return;
	}
	for(int i = head[x] ; i ; i = e[i].next) {
		int v = e[i].to;
		if(v == fx)	continue;
		dfs(v,x);
		sz[x] += sz[e[i].to];
		for(int j = sz[x] ; j >= 1 ; --j)
			for(int k = 1 ; k <= sz[e[i].to] ; ++k)
				if(j - k >= 0)
					f[x][j] = std::max(f[x][j] , f[x][j-k] + f[v][k] - e[i].dis);
		for(int k = sz[e[i].to] ; k ; --k)
			f[x][k] = std::max(f[x][k] , f[v][k] - e[i].dis);
	}
}
int main() {
	std::memset(f,-20,sizeof(f));
	scanf("%d%d",&n,&m);
	int x , y , dis;
	for(int i = 1 ; i <= n ; ++i)
		f[i][0] = 0;
	for(int i = 1 ; i <= n - m ; ++i) {
		int x;
		scanf("%d",&x);
		for(int j = 1 ; j <= x ; ++j)
			scanf("%d%d",&y,&dis) , add(i,y,dis) , add(y,i,dis);
	}
	for(int i = n - m + 1 ; i <= n ; ++i)
		scanf("%d",&v[i]);
	dfs(1,1);
	for(int i = m ; i >= 0 ; --i)
		if(f[1][i] >= 0) {
			printf("%d\n",i);
			return 0;
		}
}

[USACO11NOV]瓦交换Tile Exchanging

题目描述

Farmer John wants to remodel the floor of his barn using a collection of square tiles he recently purchased from the local square mart store (which of course, only sells square objects). Unfortunately, he didn’t measure the size of the barn properly before making his purchase, so now he needs to exchange some of his tiles for new square tiles of different sizes.

The N square tiles previously purchased by FJ have side lengths A_1…A_N. He would like to exchange some of these with new square tiles so that the total sum of the areas of the his tiles is exactly M. Square mart is currently offering a special deal: a tile of side length A_i can be exchanged for a new tile of side length B_i for a cost of

|A_i-B_i|*|A_i-B_i| units. However, this deal only applies to previously-purchased tiles — FJ is not allowed to exchange a tile that he has already obtained via exchanging some other tile (i.e., a size-3 tile cannot be exchanged for a size-2 tile, which is then exchanged for a size-1 tile).

Please determine the minimum amount of money required to exchange tiles so that the sum of the areas of the tiles becomes M. Output -1 if it is impossible to obtain an area of M.

有N个正方形，依次给出它们的边长，要求可以换掉一些正方形：如果变长为A_i的正方形换成边长为B_i的正方形所需代价为：|A_i-B_i|*|A_i-B_i|。问至少花费多少代价使得这N个正方形面积总和为M？若无论如何也不可能使这N个正方形面积总和为M则输出-1。

输入输出格式

输入格式：

* Line 1: Two space-separated integers, N (1<=N<=10) and M

(1<=M<=10,000).

* Lines 2..1+N: Each line contains one of the integers A_1 through A_N, describing the side length of an input square

(1<=A_i<=100).

输出格式：

* Line 1: The minimum cost of exchanging tiles to obtain M units of total area, or -1 if this is impossible.

输入输出样例

输入样例#1：

1
2
3
4
3 6 
3 
3 
1

输出样例#1：

1
5

说明

There are 3 tiles. Two are squares of side length 3, and one is a square with side length 1. We would like to exchange these to make a total area of 6.

Exchange one of the side-3 squares for a side-2 square, and another side-3 square for a side-1 square. This gives the desired area of 4+1+1=6 and costs 4+1=5 units.

题解

属于简单dp了。

我们考虑一个无后效的可转移的状态：

表示前i个面积为j的时候的最小话费。

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#define maxn 15
#define maxm 10005
int f[maxn][maxm] , w[maxn] , n , m;
int abs(int x){
    return x > 0 ? x : -x;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d",&w[i]);
    std::memset(f,0x7f,sizeof(f));
    f[0][0] = 0;
    int maxsqrt = std::sqrt(m);
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 1 ; j <= m ; ++j){
            for(int k = 0 ; k <= maxsqrt && k * k <= j ; ++k)
                f[i][j] = std::min(f[i][j] , f[i-1][j-k*k] + abs(w[i]-k)*abs(w[i]-k));
        }
    }
    if(f[n][m] > 50000550){
        puts("-1");
        return 0;
    }
    printf("%d\n",f[n][m]);	
}