图论

• [图论]pku3417      摘要: 我的做法是，对于每条新边，记录树中与之对应的路径。然后对于每条树边，统计被对应的次数。最后记录每个点到树根的路径上，有多少个1（设为q[i]）。对于新边(x,y)，它对答案的贡献就是q[x] + q[y] - 2q[lca(x,y)]。除了这些，答案还应加上树中0边的数量 * m。
  
    阅读全文
  posted @ 2007-10-06 20:53 Felicia 阅读(494) | 评论 (0)  编辑
• [图论][zz]给出一个没有偶圈的简单无向图，求两个顶点间路径的数目      摘要: 给出一个没有偶圈的简单无向图，求两个顶点间路径的数目
  
    阅读全文
  posted @ 2007-09-19 10:08 Felicia 阅读(969) | 评论 (2)  编辑
• [图论]pku1125      摘要: 简单题。很早以前做的。贴一下凌乱的代码。
  
    阅读全文
  posted @ 2007-09-02 20:09 Felicia 阅读(491) | 评论 (2)  编辑
• [图论]最大流(类实现)      摘要: 复杂度 O(n^2m)。支持一边构建网络，一边求最大流。每次调用 flow()，得到当前新增的流量。
  
    阅读全文
  posted @ 2007-08-13 21:12 Felicia 阅读(1010) | 评论 (1)  编辑
• 单源最短路 Dijkstra O(mlogn) (类实现)      摘要: 单源最短路 Dijkstra O(mlogn) (类实现)
  
    阅读全文
  posted @ 2007-08-13 10:01 Felicia 阅读(816) | 评论 (1)  编辑
• 二分图最大匹配(类实现)      摘要: 二分图最大匹配(类实现)
  
    阅读全文
  posted @ 2007-08-11 21:30 Felicia 阅读(1216) | 评论 (0)  编辑