博文
Zoj 2546 Walk Though the Forest(2008-03-02 15:36:00)
摘要：
2767343
2008-03-02 15:15:48
Accepted
2546
C++
00:00.45
4364K
C.D.=.=
写了个最简单的单源路径算法。完全是O(V^2)。比起2281的最小堆+链表差了不止一个档次……
后续还有一个记忆化搜索的处理，当value[u]>value[v]的时候可以把u的路径可能数加到v上。Waterloo的那一次LC还比较简单，加上网站提供标程与数据，已经轻松Clear。
1#include <cstdio> 2#include <string> 3 4#define MAXN 200000000 5 6int N, M, value[1001], visited[1001], a[1001][1001], num[1001]; 7 8int init (); 9void dijk ();10void dp ();11int func ( int );1213int main ()14{15 //freopen ( "in.txt", "r", stdin );16 while ( init () )17 {18 dijk ();19 dp ();20 //print ();21 ......
Zoj 2740 Message System(2008-02-17 16:50:00)
摘要：
2753473
2008-02-17 16:25:45
Accepted
2740
C++
00:00.00
436K
C.D.
世界上最郁闷的事情，不是连续五个WA，而是连续莫名其妙的WA，却不知道错在哪里；比这更郁闷的事情，是改动之后的连续五个AC，却发现再也找不到刚才究竟错在哪里……
遥想当年，浙大初赛时，雄姿英发；谈笑间，代码灰飞烟灭。故题重做，多情应笑我，迟来三年。卡了近三年的题目，回过头来再看也是一道简单题。
求图是否为连通生成树。预处理边数M，然后用并查集检查一下是否有回路，马上就可以解决。
因为满足生成树的情况下，M恒等于点数N-1，所以在预处理后就不需要考虑是否所有点都能够被访问。开始的时候写了一个BFS算法，遍历，结果失败。（我果然还是比较菜……= =）
#include <cstdio>#include <string>int N, M, p[1001], num[1001];int init ();void init_set ();int find_set ( int );int union_set ( int, int );int main (){ //freopen ( "in.txt", "r", stdin ); while ( init () ) { } return 0;}void init_set (){ int i; for ( i = 1; i <=&......
Zoj 2281 Way to Freedom(2008-02-11 15:23:00)
摘要：无向图中给定单源，求到某点路径中最小权边的最大值。可以将其看成求单源最短路径的变种，使用dijkstra算法+最大堆。单源最短路径的算法是：记录从源点出发访问每一点i的最短路为value[i]，对于当前所有value中的最小值点u，进行BFS式的操作，对于每条Edge(u,v)，如果edge(u,v)+value[u] < value[v] 则更新v。这是一个贪心的算法，可以证明每次出队列的u最优。
本题求的是最大单边，对此稍做修改。记录每条边目前能承受的最大重量为value[i]（即从源点所遍历路径的最小权中的最大值）。设u是当前结点，对于每条Edge(u,v)，当路径扩展到v时的最小value（min(edge, value[u])）——即路径的最短边——大于value[v] 时更新。在联通图内，每一次要求的路径都是最大，因此在BFS的过程中，边是从大到小排列，对于当前所有value中的最大值点u进行操作。因为点的数目巨大，遍历需要N<100000，可以用堆存放value。实际程序里堆存放的是点的index，使用一个辅助数组来存放index在heap中的位置，如heap[1] = 6, idx[6] = 1。为了编程方便，heap以1开始。由于边数目巨大(M<1000000)，因此使用链表储存。使用num数组保存起点为i的起始位置，next数组保存链表。num[i]=a,next[a]=b,next[b]=c,next[c]=d,next[d]=0，这里abcd都为边数组中的位置，表示以i为起点的边终点为abcd。
1#include <cstdio> 2#include <string> 3 4#define min(x, y) ( x < y ? x : y ) 5#define INF 2000000001 6 7int N, M, src, dst......
Zju 1586 QS Network(2007-03-27 14:53:00)
摘要：这题显然还是用prim，经过优化后的prim效率可以达到O(n2)。
离省赛越来越近，我也越来越没有状态，这种小白题从昨天晚上开始做，做到断网；今天爬起来继续做，才发现是把a[i][k]赋值 无限大的条件写错了——无良的出题者居然加入了两个端点间距离可能为0的情况......
#include <cstdio>#include <string>
int a[1010][1010], s[1010], dis[1010], t, n;
void pd (){ int i; for ( i = 0; i < n; i ++ ) { printf ( "%d ", dis[i] ); } printf ( "\n" );}
void init (){ int i, k; scanf ( "%d", &n ); for ( i = 0; i < n; i ++ ) { scanf ( "%d", &s[i] ); } for ( i = 0; i < n; i ++ ) { for ( k = 0; k < n; k ++ ) { scanf ( "%d", &a[i][k] ); &nb......
Zju 1705 Exchange Rates(2007-02-14 20:30:00)
摘要：放到图论里面，是因为用到了近似Floyd的算法。这题的输入麻烦，到最后直接用C++搞定了。
题目给出一系列物品之间的交换关系（比如6个i交换15个k），要求递推计算出给出的物品之间交换关系。采用的方法是建立图。a[i][k]代表了i和k交换时需要i的个数，a[k][i]是需要k的个数。每次更新信息之后对图遍历，对于那些已知a[i][j]和a[j][k]的路径，求出a[i][k]，就如同Floyd求最短路径一样。
其实不用vector和string也可以解决，但是懒惰了 = = 。
PS:到了寒假，ZOJ似乎又复苏了，做题目的人好多。当初信心满满地想着要在3月份前做到400题，现在看起来像个笑话。好吧……随便做点，我最大的计划就是没有计划。
#include <iostream>#include <vector>#include <string>#include <cstring>using namespace std;
int a[60][60];vector < string > sv;
void ps (){ int i, k; for ( i = 0; i < sv.size (); i ++ ) { for ( k = 0; k < sv.size (); k ++ ) { printf ( "%d ", a[i][k] ); } }}
int gcd ( int x, int y ){ int t; if ( x > y ) { t = x, x = y, y = t; } while ( x ) { t = x; x = y % x; y = t; } return y;}
int index ( string str ) { int i; for ( i = 0; i < sv.size (); i ++ ) {&nbs......
Zju 1119 SPF(2006-09-11 23:24:00)
摘要：
2062175
2006-09-11 23:10:31
Accepted
1119
C++
00:00.08
4368K
St.Crux
若干年以前，这个题就应该被AC了——对弱题的冲动、严蔚敏老师的数据结构、标程——AC的三大要素我都有了，但是我一直停留在第一阶段——被邓公称作是一百年不变的初级阶段。三十年前，光明日报的编辑写过，实践是检验真理的唯一标准。然而在特定的时间，特定的地点，特定的人物身上，实践只会成为怀疑真理的唯一标准。幸好我还有第三样法宝。
修改过的标程
#include <cstdio>#include <string>
int x, y, vx, idx, a[1001][1001], dfn[1001], low[1001], sub[1001], root, c = 0, mx, mn;// low[] means the lowest point one root and its subtree point to
int min(int a, int b){ return a > b ? b : a;}
void init(){ memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(sub, 0, sizeof(sub)); idx = 1, low[vx] = dfn[vx] = idx, root = 0;}
void dfs(int i){ int k; for(k = mn; k <= mx; k ++) { if(a[i][k]) // k adjacent to i { if(!dfn[k]) // k not visited -- k is in subtree { idx ++; &nb......
Zju 1789 The Suspects(2006-08-27 22:53:00)
摘要：
2045607
2006-08-27 22:32:59
Accepted
1789
C++
00:00.02
668K
St.Crux
2045606
2006-08-27 22:32:16
Accepted
1789
C++
00:00.02
556K
St.Crux
上面那个是优化过的，没看错.......可能数据碰巧不喜欢这样被优化。
这是标准解法。
#include <cstdio>#include <string>
int p[30001], r[30001], n, m, t, x, y, ans;
int findset(int i){ if(i == -1 || i >= n) return -1; if(p[i] != -1 && p[i] != i) p[i] = findset(p[i]); return p[i];}
int ufs(int a, int b){ a = findset(a); b = findset(b); if(a == b) return a; if(a == -1) return b; if(b == -1) return a; if(r[a] < r[b]) { p[a] = b; return b; } else { if(r[a] == r[b]) r[a] ++; p[b] = a; return a; }}
void init(){ memset(r, 0, sizeof(r)); int i; for(i = 0; i < n; i ++) { p[i] = -1; }}
int main(){ //freopen("in.txt", "r", stdin); while(scanf("%d %d"......
Zju 1103 Hike on a Graph(2006-08-16 19:28:00)
摘要：
2025283
2006-08-16 19:12:19
Accepted
1103
C++
00:00.07
1544K
St.Crux
这个题其实不难。可是我用了半个下午的时间研究如何dp......这件事告诉我一个深刻的道理......下次用一个小时研究就可以了。
好吧，这个题还是有写头滴，幸好queue让我简便了不少。还有一开始看错题意，每一枚棋子是不能同时移动的。
#include <iostream>#include <fstream>#include <queue>#include <cstring>using namespace std;
class pt{public: int i, k, j, c;};
queue<pt> pq, tq, ttq;int n, p1, p2, p3, b[50][50][50], ans;char a[50][50];
void init(){ p1 --, p2 --, p3 --; memset(b, 0, sizeof(b)); ans = -1; pq = tq; b[p1][p2][p3] = 1; pt tpt; tpt.i = p1, tpt.k = p2, tpt.j = p3, tpt.c = 0; pq.push(tpt);}
void bfs(){ while(!pq.empty()) { //pb(); pt tpt, ttpt; int i, k, j; tpt = pq.front(); if(tpt.i == tpt.k && tpt.k == tpt.j) { ans = tpt.c; break; } for(i = 0; i < n; i ++) { if(......
Zju 1092 Arbitrage(2006-08-14 23:33:00)
摘要：
2021578
2006-08-14 23:10:47
Accepted
1092
C++
00:00.37
856K
St.Crux
输出的时候犯了一个小错误："Yes"当作“YES”了。
这个题是很基础的最短路径题，不限次数倒买倒卖，求能否过一定的收益率（这里为1）。我记得uva上有一个题是问在t次交换内能否达到一定的汇率......那样似乎还要记录路径了......上次学校里搞选拔赛的时候做过，做不出。现在还是做不出 TAT
另，memset(a, 0, sizeof(a))对double数组无效。但可以写memset(a, 0x00, sizeof(a))
#include <iostream>#include <fstream>#include <cstring>#include <string>#include <map>using namespace std;
double a[30][30];map<string, int> sm, dm;int n, c = 0, ac;
int main(){ //ifstream cin("in.txt"); while(cin >> n && n) { sm = dm; int i, k, t, j; for(i = 0; i < n; i ++) { string s; cin >> s; sm[s] = i; for(k = 0; k < n; k ++) { a[i][k] = 0; //清零 } } cin >> t; for(i = 0; i < t; i ++......
Zju 1082 Stockbroker Grapevine(2006-08-12 20:45:00)
摘要：
2017811
2006-08-12 20:23:54
Accepted
1082
C++
00:00.00
428K
St.Crux
最短路径的前提就是i点到k点能够访问。反之就是访问不能。
W.Floyd把j放在外面，i，k放在循环里面。我曾经错误的认为i和k是应该在外层循环，结果造成了长期的心理错觉，以致于一遇见这样的题目就ac不能，进而对Floyd先生产生了强烈的怨念。但是Floyd有证明么？
#include <cstdio>#include <string>
#define MX 1001
int a[100][100], n, m;
int main(){ //freopen("in.txt", "r", stdin); while(scanf("%d", &n) && n) { int i, k, j, ac = 1; for(i = 0; i < n; i ++) { scanf("%d", &m); for(k = 0; k < n; k ++) { a[i][k] = MX; } for(k = 0; k < m; k ++) { int ti, tn; scanf("%d %d", &ti, &tn); a[i][ti - 1] = tn; } } //pa(); for(j = 0; j < n; j ++) { for(i = 0; i < n; i ++) ......