博文
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 );
12
13int main ()
14{
15 //freopen ( "in.txt", "r", stdin );
16 while ( init () )
17 {
18 dijk ();
19 dp ();
20 &......
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 ()
{
in......
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
......
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 ++ )
{
&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;
}
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 subtre......
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......
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)
{
&nb......
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; //清零
&n......
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();
f......