博文
Zoj 1542 Network(2008-01-23 13:28:00)
摘要：
2730750
2008-01-23 13:12:47
Accepted
1542
C++
00:00.24
728K
C.D.
求最大边最短的生成树。
我怀疑即为最小生成树【？】。因为假如按照Prim算法，每次求得的都为一个集合到另一个集合的最短边，也就是不可能生成两棵树，一颗三条边为2，2，2，一颗为1，1，3；这样的情况应该会产生1，1，2 的生成树。【未严格证明】
但是在求最大边的时候，显然是用排序+并查集更易得到结果。
值得注意的是几点。
1.在unionset操作里使用了不同的返回值分辨不同的处理情况。
2.qsort的处理。
/*
zoj 1542
author: Crux.D
date: 2008.1.23
description: mst, kruscal, n-1 edge
*/
#include <cstdio>
#include <string>
#include <cstdlib>
typedef struct
{
int t1, t2, l;
} Con;
Con hub[15000], ans[1001];
int N, M, ans_num, max_len; // hub个数，connection数量，生成树边数（N-1），最大边长度
int cmp ( const void *a, const void *b )
{
Con *A = ( Con* ) a;
Con *B = ( Con* ) b;
if ( A->l == B->l )
{
if ( A->t1 == B->t1 )
return A->t2 > B->t2;
return A->t1 > B->t1;
......
Zoj 2833 Friendship(2008-01-22 18:40:00)
摘要：
2730205
2008-01-22 18:15:30
Accepted
2833
C++
00:00.95
1180K
C.D.
这大概就是所谓的RPWT，拿出来炫耀一下。【灰溜溜爬开】
其实这题的时限是3000ms，还宽裕的很。但前十名都能把时间压到500ms以内，说明普通的并查集还有值得优化的地方。顺便讲一句，这题通过的人数好X多。第一次写的时候根本就忘了什么是压缩路径，可耻地TLE鸟。【= =】 发现上一次写并查集是一年前的事情，结果又忘记怎么做了……【为什么是又】
所谓的并查集，也只不过是一枚特殊的树罢了。这棵树在完成findset操作之后，高度至多为2，而且形式为根节点下面N个叶子——这就是压缩；在完成两棵树的合并之后高度至多为3.为了方便编写，采用的是数组而不是链表；这一点我倒是牢牢记住了。
/* zoj 2833
author : Crux.D
date : 2008.1.21
description : unionset
*/
#include <cstdio>
#include <string>
int parent[100001], num[100001], N, M, cs = 0;
void init ()
{
int i;
for ( i = 0; i <= N; i ++ )
{
parent[i] = -1;
num[i] = 1;
}
if ( cs ++ )
printf ( "\n" );
printf ( "Case %d:\n", cs );
}
int find_set ( int n )
{
//寻找树的根节点
int pre = n;
while ( parent[pre] != -1 )
{
pre = parent[pre];
&nbs......
Zju 1097 Code the Tree(2006-12-17 23:23:00)
摘要：
2173944
2006-12-17 23:15:34
Accepted
1097
C++
00:00.02
876K
Crux.D
烦题，输入巨无聊。如果不想自己写的话参考一下吧。
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
string s;
int a[51][51], b[51], c[51], si, mx;
int node()
{
int t = 0;
while(s[si] >= '0' && s[si] <= '9')
{
t *= 10;
t += s[si ++] - '0';
}
return t;
}
void build(int n)
{
int t;
if(n > mx) mx = n;
while(s[si] == '(')
{
si ++;
t = node();
if(n)
{
b[n] ++;
b[t] ++;
a[t][n] = 1;
a[n][t] = 1;
}
build(t);
si ++;
}
}
void init()
{
si = 0, mx = 0;
memset(b, 0, sizeof(b));
memset(a, 0,......
Zju 1268 Is It A Tree?(2006-08-31 22:55:00)
摘要：
2049913
2006-08-31 22:34:46
Accepted
1268
C++
00:00.00
448K
St.Crux
题如其名。如何判断一幅图为树？
设x, y是一对父子节点。对每个x, y，都必须满足如下条件。
1.每个节点没有两个父亲。反例p[y] != y，即y已有父节点。
2.没有回路。反例find_set(x) == y，父节点的祖先是子节点。
以上在输入时即可判断。
3.没有森林。遍历p[i]，没有两个以上的祖先节点。
在这里，采用了并查集作为数据结构，可以用路径压缩，求得根节点。
#include <cstdio>
#include <string>
int p[1001], x, y, b[1001], ac, c[1001], k = 1;
int find_set(int i)
{
if(p[i] != i)
{
p[i] = find_set(p[i]);
}
return p[i];
}
void proc()
{
int i, t = 0;
for(i = 0; i < 1001; i ++)
{
if(b[i])
{
c[find_set(i)] ++;
}
}
for(i = 0; i < 1001; i ++)
{
if(c[i] > 1)
t ++;
}
if(t > 1) ac = 0;
}
void init()
{
int i;
for(i = 0; i <= 1000; i ++)
p[i] = i;
......
Zju 1062 Trees Made to Order(2006-08-26 15:17:00)
摘要：
2043646
2006-08-26 14:29:40
Accepted
1062
C++
00:00.00
432K
St.Crux
给出一个N，求中序树形。
Sample Input
1
20
31117532
0
Sample Output
X
((X)X(X))X
(X(X(((X(X))X(X))X(X))))X(((X((X)X((X)X)))X)X)
这个题的思想是不断逼近。要构造一颗树，（最好）要知道他的左子树序列号和右子树序列号。这个一下子求不出来，但是我们可以先看一下能求出的东西。
N个节点数这儿有几棵树。An= C(2n, n) / (n + 1)，这个可以求，打一个表就可。且可求得N<20。
N这整棵树是几个节点。这个就好求了。用An一个一个的依次减，马上就求出来。减出来的数还得存着，待会儿还得减。
左子树几个节点。这个有点技巧了。这要明白一规律，当左子树有l个节点，右子树r个节点时，这样的树有几棵。答案是Al * Ar。这是全题的关键。而且这树是按左子树的节点树依次排下来的。这就好办了，和上面一样，一个一个挨个减下来。算出来以后右子树也出来了。这就是左子树的节点数和右子树的结点数。
最后就是这个序列号了。就拿这4,5,6,7,8来说吧。减到现在，就成了0,1,0,0,1。这有什么规律呢？没错，0,1分别是2号和3号在他们那一组（2棵树的）里的序列号。现在要用数学公式来说的话，就是：
设Sl为左边的序列号（在他们那一组里的，以下同）Sr为右边的，Al是左边节点数树的总个数，Ar同，t是N减到现在还剩的那个数。则可得：Sl = t / Ar, Sr = t % Ar。因为每棵树是从右开始排，填满了Ar * Al种排法就结束，换到下一种Ar －1的排法里去了，也不归这个排法的管了。左边呢？就Al种排法，一个一个来，比作齿轮的话，就先得让右边的Ar轮一遍，才轮到他动一格。于是这个题就变成简单的排列组合了。
具体的算法边界处还得考虑，这个也是挺麻烦的一个地方。
#include <cstdio>
int a[20] = { 1, 1, 2, 5, 14, 42, 132,
429, 143......