博文
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; } return A->l > B->l;}
void pt (){ int i; for ( i = 0; ......
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]; } int root = pre; //非递归从底到顶压缩路径，简化为高度为2的树 while ( n != root ) { &......
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, sizeof(a)); memset(c, 0, sizeof(c)); int i; string ts = ""; for(i = 0; i < s.size(); i ++) { if(s[i]......
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; ac = 1; memset(b, 0, sizeof(b)); memset(c, 0, sizeof(c));}
void pt(){ printf("Case %d is ", k ++); ......
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
120311175320
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, 1430, 4862, 16796, 58786, 208012,&n......