﻿<?xml version="1.0" encoding="utf-8" standalone="yes"?><rss version="2.0" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:trackback="http://madskills.com/public/xml/rss/module/trackback/" xmlns:wfw="http://wellformedweb.org/CommentAPI/" xmlns:slash="http://purl.org/rss/1.0/modules/slash/"><channel><title>C++博客-zercal</title><link>http://www.cppblog.com/zercal/</link><description /><language>zh-cn</language><lastBuildDate>Wed, 15 Apr 2026 00:27:16 GMT</lastBuildDate><pubDate>Wed, 15 Apr 2026 00:27:16 GMT</pubDate><ttl>60</ttl><item><title>PKU推荐题目</title><link>http://www.cppblog.com/zercal/archive/2007/10/30/35524.html</link><dc:creator>zercal</dc:creator><author>zercal</author><pubDate>Tue, 30 Oct 2007 07:56:00 GMT</pubDate><guid>http://www.cppblog.com/zercal/archive/2007/10/30/35524.html</guid><wfw:comment>http://www.cppblog.com/zercal/comments/35524.html</wfw:comment><comments>http://www.cppblog.com/zercal/archive/2007/10/30/35524.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cppblog.com/zercal/comments/commentRss/35524.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/zercal/services/trackbacks/35524.html</trackback:ping><description><![CDATA[POJ上一些题目在<br><a href="http://162.105.81.202/course/problemSolving/" target=_blank><u><font color=#0000ff>http://162.105.81.202/course/problemSolving/</font></u></a> <br>可以找到解题报告。<br>《算法艺术与信息学竞赛》的习题提示在网上可搜到<br><br>一.动态规划<br>参考资料：<br>刘汝佳《算法艺术与信息学竞赛》<br>《算法导论》<br><br>推荐题目：<br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1141" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1141</font></u></a> <br>简单<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2288" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2288</font></u></a> <br>中等，经典TSP问题<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2411" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2411</font></u></a> <br>中等，状态压缩DP<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1112" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1112</font></u></a> <br>中等<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1848" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1848</font></u></a> <br>中等，树形DP。<br>可参考《算法艺术与信息学竞赛》动态规划一节的树状模型<br><br><a href="http://acm.zju.edu.cn/show_problem.php?pid=1234" target=_blank><u><font color=#0000ff>http://acm.zju.edu.cn/show_problem.php?pid=1234</font></u></a> <br>中等，《算法艺术与信息学竞赛》中的习题<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1947" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1947</font></u></a> <br>中等，《算法艺术与信息学竞赛》中的习题<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1946" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1946</font></u></a> <br>中等，《算法艺术与信息学竞赛》中的习题<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1737" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1737</font></u></a> <br>中等，递推<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1821" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1821</font></u></a> <br>中等，需要减少冗余计算<br><br><a href="http://acm.zju.edu.cn/show_problem.php?pid=2561" target=_blank><u><font color=#0000ff>http://acm.zju.edu.cn/show_problem.php?pid=2561</font></u></a> <br>中等，四边形不等式的简单应用<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1038" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1038</font></u></a> <br>较难，状态压缩DP，《算法艺术与信息学竞赛》中有解答<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1390" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1390</font></u></a> <br>较难，《算法艺术与信息学竞赛》中有解答<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=3017" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=3017</font></u></a> <br>较难，需要配合数据结构优化（我的题目^_^）<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1682" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1682</font></u></a> <br>较难，写起来比较麻烦<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2047" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2047</font></u></a> <br>较难<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2152" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2152</font></u></a> <br>难，树形DP<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=3028" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=3028</font></u></a> <br>难，状态压缩DP，题目很有意思<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=3124" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=3124</font></u></a> <br>难<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2915" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2915</font></u></a> <br>非常难<br><br><br>二.搜索<br>参考资料：<br>刘汝佳《算法艺术与信息学竞赛》<br>推荐题目：<br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1011" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1011</font></u></a> <br>简单，深搜入门题<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1324" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1324</font></u></a> <br>中等，广搜<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2044" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2044</font></u></a> <br>中等，广搜<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2286" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2286</font></u></a> <br>较难，广搜<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1945" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1945</font></u></a> <br>难，IDA*，迭代加深搜索，需要较好的启发函数<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2449" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2449</font></u></a> <br>难，可重复K最短路，A*。<br>可参考解题报告:<br><a href="http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1144" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1144</font></u></a> <br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1190" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1190</font></u></a> <br>难，深搜剪枝，《算法艺术与信息学竞赛》中有解答<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1084" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1084</font></u></a> <br>难，《算法艺术与信息学竞赛》习题<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2989" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2989</font></u></a> <br>难，深搜<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1167" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1167</font></u></a> <br>较难，《算法艺术与信息学竞赛》中有解答<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1069" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1069</font></u></a> <br>很难<br><br><br>三.&nbsp;常用数据结构<br>参考资料：<br>刘汝佳《算法艺术与信息学竞赛》<br>《算法导论》<br>线段树资料：<br><a href="http://home.ustc.edu.cn/~zhuhcheng/ACM/segment_tree.pdf" target=_blank><u><font color=#0000ff>http://home.ustc.edu.cn/~zhuhcheng/ACM/segment_tree.pdf</font></u></a> <br>树状数组资料<br><a href="http://home.ustc.edu.cn/~zhuhcheng/ACM/tree.ppt" target=_blank><u><font color=#0000ff>http://home.ustc.edu.cn/~zhuhcheng/ACM/tree.ppt</font></u></a> <br>关于线段树和树状数组更多相关内容可在网上搜到<br>后缀数组资料<br><a href="http://home.ustc.edu.cn/~zhuhcheng/ACM/suffix_array.pdf" target=_blank><u><font color=#0000ff>http://home.ustc.edu.cn/~zhuhcheng/ACM/suffix_array.pdf</font></u></a> <br><a href="http://home.ustc.edu.cn/~zhuhcheng/ACM/linear_suffix.pdf" target=_blank><u><font color=#0000ff>http://home.ustc.edu.cn/~zhuhcheng/ACM/linear_suffix.pdf</font></u></a> <br><br>推荐题目<br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2482" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2482</font></u></a> <br>较难，线段树应用，《算法艺术与信息学竞赛》中有解答<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1151" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1151</font></u></a> <br>简单，线段树应用矩形面积并，《算法艺术与信息学竞赛》中有解答<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=3225" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=3225</font></u></a> <br>较难，线段树应用，可参考解题报告<br><a href="http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1233" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1233</font></u></a> <br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2155" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2155</font></u></a> <br>难，二维树状数组。<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2777" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2777</font></u></a> <br>中等，线段树应用。<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2274" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2274</font></u></a> <br>难，堆的应用，《算法艺术与信息学竞赛》中有解答<br><br><a href="http://acm.zju.edu.cn/show_problem.php?pid=2334" target=_blank><u><font color=#0000ff>http://acm.zju.edu.cn/show_problem.php?pid=2334</font></u></a> <br>中等，左偏树，二项式堆或其他可合并堆的应用。<br>左偏树参考<a href="http://www.nist.gov/dads/HTML/leftisttree.html" target=_blank><u><font color=#0000ff>http://www.nist.gov/dads/HTML/leftisttree.html</font></u></a> <br>二项式堆参见《算法导论》相关章节<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1182" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1182</font></u></a> <br>中等，并查集<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1816" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1816</font></u></a> <br>中等，字典树<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2778" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2778</font></u></a> <br>较难，多串匹配树<br>参考：<a href="http://home.ustc.edu.cn/~zhuhcheng/ACM/zzy2004.pdf" target=_blank><u><font color=#0000ff>http://home.ustc.edu.cn/~zhuhcheng/ACM/zzy2004.pdf</font></u></a> <br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1743" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1743</font></u></a> <br>难，后缀数组<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2774" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2774</font></u></a> <br>较难，最长公共子串，经典问题，后缀数组<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2758" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2758</font></u></a> <br>很难，后缀数组<br>可参考解题报告<br><a href="http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1178" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1178</font></u></a> <br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2448" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2448</font></u></a> <br>很难，数据结构综合运用<br><br>四.图论基础<br>参考资料：<br>刘汝佳《算法艺术与信息学竞赛》<br>《算法导论》<br>《网络算法与复杂性理论》谢政<br><br>推荐题目:&nbsp;<br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2337" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2337</font></u></a> <br>简单，欧拉路<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=3177" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=3177</font></u></a> <br>中等，无向图割边<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2942" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2942</font></u></a> <br>较难，无向图双连通分支<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1639" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1639</font></u></a> <br>中等，最小度限制生成树，《算法艺术与信息学竞赛》中有解答<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2728" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2728</font></u></a> <br>中等，最小比率生成树，《算法艺术与信息学竞赛》中有解答<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=3013" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=3013</font></u></a> <br>简单，最短路问题<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1275" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1275</font></u></a> <br>中等，差分约束系统，Bellman-Ford求解，《算法艺术与信息学竞赛》中有解答<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1252" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1252</font></u></a> <br>简单，Bellman-Ford<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1459" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1459</font></u></a> <br>中等，网络流<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2391" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2391</font></u></a> <br>较难，网络流<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1325" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1325</font></u></a> <br>中等，二部图最大匹配<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2226" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2226</font></u></a> <br>较难，二部图最大匹配<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2195" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2195</font></u></a> <br>中等，二部图最大权匹配<br>KM算法参考《网络算法与复杂性理论》<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2516" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2516</font></u></a> <br>较难，二部图最大权匹配<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1986" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1986</font></u></a> <br>中等，LCA（最近公共祖先）问题<br>参考Tarjan's&nbsp;LCA&nbsp;algorithm&nbsp;《算法导论》第21章习题<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2723" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2723</font></u></a> <br>较难，2-SAT问题<br>参考：<a href="http://home.ustc.edu.cn/~zhuhcheng/ACM/2-SAT.PPT" target=_blank><u><font color=#0000ff>http://home.ustc.edu.cn/~zhuhcheng/ACM/2-SAT.PPT</font></u></a> <br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2749" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2749</font></u></a> <br>较难，2-SAT问题<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=3164" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=3164</font></u></a> <br>较难，最小树形图<br>参考《网络算法与复杂性理论》中朱-刘算法<br><br>五.数论及组合计数基础<br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1811" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1811</font></u></a> <br>简单，素数判定，大数分解<br>参考算法导论相关章节<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2888" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2888</font></u></a> <br>较难，Burnside引理<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2891" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2891</font></u></a> <br>中等，解模方程组<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2154" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2154</font></u></a> <br>中等，经典问题，波利亚定理<br><br><a href="http://cs.scu.edu.cn/soj/problem.action?id=2703" target=_blank><u><font color=#0000ff>http://cs.scu.edu.cn/soj/problem.action?id=2703</font></u></a> <br>难，极好的题目，Burnside引理+模线性方程组<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2764" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=2764</font></u></a> <br>较难，需要数学方法，该方法在《具体数学》第七章有讲<br><br><a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1977" target=_blank><u><font color=#0000ff>http://acm.pku.edu.cn/JudgeOnline/problem?id=1977</font></u></a> <br>简单，矩阵快速乘法<br><br><br>
<img src ="http://www.cppblog.com/zercal/aggbug/35524.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/zercal/" target="_blank">zercal</a> 2007-10-30 15:56 <a href="http://www.cppblog.com/zercal/archive/2007/10/30/35524.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>南京挂了</title><link>http://www.cppblog.com/zercal/archive/2007/10/30/35523.html</link><dc:creator>zercal</dc:creator><author>zercal</author><pubDate>Tue, 30 Oct 2007 07:52:00 GMT</pubDate><guid>http://www.cppblog.com/zercal/archive/2007/10/30/35523.html</guid><wfw:comment>http://www.cppblog.com/zercal/comments/35523.html</wfw:comment><comments>http://www.cppblog.com/zercal/archive/2007/10/30/35523.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cppblog.com/zercal/comments/commentRss/35523.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/zercal/services/trackbacks/35523.html</trackback:ping><description><![CDATA[<p>无奈啊,本来实力就不行,经验又不够,运气又差.又蒙了,想不挂都难...<br><br></p>
<p>第一道题是我们最善长的题目,结果题目意思理解错误,直接卡了3个小时,把我们都卡蒙了...<br>第2题3题都是我们最弱的高级数据结构(另一个同样弱的就是几何了),如果第一题早出,那么第2题字典树还是能出的,但是后缀数组就只好放弃了...<br>总的来说,拿不了银是实力问题,没拿铜就是比赛经验和人品的问题了...</p>
<img src ="http://www.cppblog.com/zercal/aggbug/35523.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/zercal/" target="_blank">zercal</a> 2007-10-30 15:52 <a href="http://www.cppblog.com/zercal/archive/2007/10/30/35523.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>PKU1639最小度限制生成树</title><link>http://www.cppblog.com/zercal/archive/2007/10/09/33828.html</link><dc:creator>zercal</dc:creator><author>zercal</author><pubDate>Tue, 09 Oct 2007 08:10:00 GMT</pubDate><guid>http://www.cppblog.com/zercal/archive/2007/10/09/33828.html</guid><wfw:comment>http://www.cppblog.com/zercal/comments/33828.html</wfw:comment><comments>http://www.cppblog.com/zercal/archive/2007/10/09/33828.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cppblog.com/zercal/comments/commentRss/33828.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/zercal/services/trackbacks/33828.html</trackback:ping><description><![CDATA[&nbsp;&nbsp;&nbsp;&nbsp; 摘要: 终于AC了，大概在8月份就会做这道题了，一直没有去写（bs下自己）。拖了好久昨天下定决心说一定要把这道题AC了（pku1639），于是就开始写，结果一下从18：00wa到21：30.。。。都怨操作系统老师，我都在睡觉了她讲课还把我搞的头疼了一天&#8230;今天起来决定重写,之前写的那个实在是太烂了.&nbsp;精神好了干什么都顺利,在经过几个莫名其妙的小错误后,终于A了&#823...&nbsp;&nbsp;<a href='http://www.cppblog.com/zercal/archive/2007/10/09/33828.html'>阅读全文</a><img src ="http://www.cppblog.com/zercal/aggbug/33828.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/zercal/" target="_blank">zercal</a> 2007-10-09 16:10 <a href="http://www.cppblog.com/zercal/archive/2007/10/09/33828.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>调整状态...努力...</title><link>http://www.cppblog.com/zercal/archive/2007/10/06/33650.html</link><dc:creator>zercal</dc:creator><author>zercal</author><pubDate>Sat, 06 Oct 2007 12:26:00 GMT</pubDate><guid>http://www.cppblog.com/zercal/archive/2007/10/06/33650.html</guid><wfw:comment>http://www.cppblog.com/zercal/comments/33650.html</wfw:comment><comments>http://www.cppblog.com/zercal/archive/2007/10/06/33650.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cppblog.com/zercal/comments/commentRss/33650.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/zercal/services/trackbacks/33650.html</trackback:ping><description><![CDATA[<p>最近状态一直很不好...乱七八糟的事情烦得要死,文艺部开学也正忙,心情也不好,搞得这半个多月都很没有动力.还有一个月就要出去比赛了,这种状态真是....<br>还都是要努力才行啊...</p>
<p>十一完了会熄灯...慢慢的把状态转过来,不去管恶心的事情(我恨死校团委了),而且文艺部的事情现在也都可以比较放心(其实还是很不放心的...),慢慢的把精力放在ACM上吧,水平那么烂,再不努力.......<br></p>
<p>恩,十月份的目标:<br>1,把标程都整理出来,主要是图论的,需要标程的整理出一个精简的比赛用的标程,不需要的那些经典问题也都要写一遍,压得那几道题目也都尽量过了.数论的就要好好努力把书多看看...偏偏计科还不学信安数基...搞了这么久感觉人信安的随便抓个人数论都比我强...郁闷<br>2,多看写论文...看一些是一些吧...<br>3,保证比赛量的同时自己也要做些练习题...秒杀娱乐题就不做了,毕竟在Arbiter里我不用当代码手.不过中档的题目(对于我来说就是难题了T T)要多做,争取一道题目有一道题目的收获吧,保持状态也是很重要的.<br>4,具体数学...看一点是一点吧...有些事情是真的勉强不来的...IQ不够那也没办法不是...<br>5,规范作息...一开始熄灯我估计又要开始失眠了...<br>6,保持好心情...这个最难...工作时要表现的有自信,不能影响别人happy...比赛时不管怎样都要冷静...其实我是实在什么都不想做...啊啊啊啊啊啊啊....真是太没心情了......</p>
<img src ="http://www.cppblog.com/zercal/aggbug/33650.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/zercal/" target="_blank">zercal</a> 2007-10-06 20:26 <a href="http://www.cppblog.com/zercal/archive/2007/10/06/33650.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>单元最短路（dijkstra+堆）不是很精简</title><link>http://www.cppblog.com/zercal/archive/2007/10/06/33647.html</link><dc:creator>zercal</dc:creator><author>zercal</author><pubDate>Sat, 06 Oct 2007 12:04:00 GMT</pubDate><guid>http://www.cppblog.com/zercal/archive/2007/10/06/33647.html</guid><wfw:comment>http://www.cppblog.com/zercal/comments/33647.html</wfw:comment><comments>http://www.cppblog.com/zercal/archive/2007/10/06/33647.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cppblog.com/zercal/comments/commentRss/33647.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/zercal/services/trackbacks/33647.html</trackback:ping><description><![CDATA[<div style="BORDER-RIGHT: #cccccc 1px solid; PADDING-RIGHT: 5px; BORDER-TOP: #cccccc 1px solid; PADDING-LEFT: 4px; FONT-SIZE: 13px; PADDING-BOTTOM: 4px; BORDER-LEFT: #cccccc 1px solid; WIDTH: 98%; WORD-BREAK: break-all; PADDING-TOP: 4px; BORDER-BOTTOM: #cccccc 1px solid; BACKGROUND-COLOR: #eeeeee"><span style="COLOR: #008080">&nbsp;&nbsp;1</span>&nbsp;<span style="COLOR: #000000">#include</span><span style="COLOR: #000000">&lt;</span><span style="COLOR: #000000">iostream</span><span style="COLOR: #000000">&gt;</span><span style="COLOR: #000000"><br></span><span style="COLOR: #008080">&nbsp;&nbsp;2</span>&nbsp;<span style="COLOR: #000000"></span><span style="COLOR: #0000ff">using</span><span style="COLOR: #000000">&nbsp;</span><span style="COLOR: #0000ff">namespace</span><span style="COLOR: #000000">&nbsp;std;<br></span><span style="COLOR: #008080">&nbsp;&nbsp;3</span>&nbsp;<span style="COLOR: #000000"></span><span style="COLOR: #0000ff">#define</span><span style="COLOR: #000000">&nbsp;maxn&nbsp;100000</span><span style="COLOR: #000000"><br></span><span style="COLOR: #008080">&nbsp;&nbsp;4</span>&nbsp;<span style="COLOR: #000000"></span><span style="COLOR: #0000ff">#define</span><span style="COLOR: #000000">&nbsp;maxint&nbsp;100000000</span><span style="COLOR: #000000"><br></span><span style="COLOR: #008080">&nbsp;&nbsp;5</span>&nbsp;<span style="COLOR: #000000"><br></span><span style="COLOR: #008080">&nbsp;&nbsp;6</span>&nbsp;<span style="COLOR: #000000"></span><span style="COLOR: #0000ff">struct</span><span style="COLOR: #000000">&nbsp;adj{<br></span><span style="COLOR: #008080">&nbsp;&nbsp;7</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;ed;<br></span><span style="COLOR: #008080">&nbsp;&nbsp;8</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;ll;<br></span><span style="COLOR: #008080">&nbsp;&nbsp;9</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;adj&nbsp;</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">pe;<br></span><span style="COLOR: #008080">&nbsp;10</span>&nbsp;<span style="COLOR: #000000">};<br></span><span style="COLOR: #008080">&nbsp;11</span>&nbsp;<span style="COLOR: #000000"><br></span><span style="COLOR: #008080">&nbsp;12</span>&nbsp;<span style="COLOR: #000000"></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;vn,maxd;</span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">点数&nbsp;需要将vn赋初值&nbsp;</span><span style="COLOR: #008000"><br></span><span style="COLOR: #008080">&nbsp;13</span>&nbsp;<span style="COLOR: #008000"></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;dui[maxn],d[maxn],father[maxn],hx[maxn];</span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">点，堆从1开始&nbsp;</span><span style="COLOR: #008000"><br></span><span style="COLOR: #008080">&nbsp;14</span>&nbsp;<span style="COLOR: #008000"></span><span style="COLOR: #0000ff">struct</span><span style="COLOR: #000000">&nbsp;adj&nbsp;</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">node[maxn];</span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">邻接表&nbsp;，要memset&nbsp;</span><span style="COLOR: #008000"><br></span><span style="COLOR: #008080">&nbsp;15</span>&nbsp;<span style="COLOR: #008000"></span><span style="COLOR: #000000"><br></span><span style="COLOR: #008080">&nbsp;16</span>&nbsp;<span style="COLOR: #000000"></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;take(</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;x)<br></span><span style="COLOR: #008080">&nbsp;17</span>&nbsp;<span style="COLOR: #000000">{<br></span><span style="COLOR: #008080">&nbsp;18</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;k;<br></span><span style="COLOR: #008080">&nbsp;19</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">while</span><span style="COLOR: #000000">(d[dui[x]]</span><span style="COLOR: #000000">&lt;</span><span style="COLOR: #000000">d[dui[x</span><span style="COLOR: #000000">/</span><span style="COLOR: #000000">2</span><span style="COLOR: #000000">]]</span><span style="COLOR: #000000">&amp;&amp;</span><span style="COLOR: #000000">x</span><span style="COLOR: #000000">&gt;</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">)<br></span><span style="COLOR: #008080">&nbsp;20</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;{<br></span><span style="COLOR: #008080">&nbsp;21</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;swap(hx[dui[x]],hx[dui[x</span><span style="COLOR: #000000">/</span><span style="COLOR: #000000">2</span><span style="COLOR: #000000">]]);<br></span><span style="COLOR: #008080">&nbsp;22</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;swap(dui[x],dui[x</span><span style="COLOR: #000000">/</span><span style="COLOR: #000000">2</span><span style="COLOR: #000000">]);<br></span><span style="COLOR: #008080">&nbsp;23</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">x</span><span style="COLOR: #000000">/</span><span style="COLOR: #000000">2</span><span style="COLOR: #000000">;<br></span><span style="COLOR: #008080">&nbsp;24</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<br></span><span style="COLOR: #008080">&nbsp;25</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">while</span><span style="COLOR: #000000">((x</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">2</span><span style="COLOR: #000000">)</span><span style="COLOR: #000000">&lt;=</span><span style="COLOR: #000000">maxd)<br></span><span style="COLOR: #008080">&nbsp;26</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;{<br></span><span style="COLOR: #008080">&nbsp;27</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">x</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">2</span><span style="COLOR: #000000">;<br></span><span style="COLOR: #008080">&nbsp;28</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">if</span><span style="COLOR: #000000">(k</span><span style="COLOR: #000000">&lt;</span><span style="COLOR: #000000">maxd</span><span style="COLOR: #000000">&amp;&amp;</span><span style="COLOR: #000000">d[dui[k]]</span><span style="COLOR: #000000">&gt;</span><span style="COLOR: #000000">d[dui[k</span><span style="COLOR: #000000">+</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">]])<br></span><span style="COLOR: #008080">&nbsp;29</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">;<br></span><span style="COLOR: #008080">&nbsp;30</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">if</span><span style="COLOR: #000000">(d[dui[x]]</span><span style="COLOR: #000000">&gt;</span><span style="COLOR: #000000">d[dui[k]])<br></span><span style="COLOR: #008080">&nbsp;31</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<br></span><span style="COLOR: #008080">&nbsp;32</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;swap(hx[dui[x]],hx[dui[k]]);<br></span><span style="COLOR: #008080">&nbsp;33</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;swap(dui[x],dui[k]);<br></span><span style="COLOR: #008080">&nbsp;34</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">k;<br></span><span style="COLOR: #008080">&nbsp;35</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br></span><span style="COLOR: #008080">&nbsp;36</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">else</span><span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">break</span><span style="COLOR: #000000">;<br></span><span style="COLOR: #008080">&nbsp;37</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;}<br></span><span style="COLOR: #008080">&nbsp;38</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">return</span><span style="COLOR: #000000">&nbsp;</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;<br></span><span style="COLOR: #008080">&nbsp;39</span>&nbsp;<span style="COLOR: #000000">}<br></span><span style="COLOR: #008080">&nbsp;40</span>&nbsp;<span style="COLOR: #000000"><br></span><span style="COLOR: #008080">&nbsp;41</span>&nbsp;<span style="COLOR: #000000"></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;</span><span style="COLOR: #0000ff">out</span><span style="COLOR: #000000">()<br></span><span style="COLOR: #008080">&nbsp;42</span>&nbsp;<span style="COLOR: #000000">{<br></span><span style="COLOR: #008080">&nbsp;43</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;x,i;<br></span><span style="COLOR: #008080">&nbsp;44</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">if</span><span style="COLOR: #000000">(maxd</span><span style="COLOR: #000000">&lt;</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">)&nbsp;</span><span style="COLOR: #0000ff">return</span><span style="COLOR: #000000">&nbsp;</span><span style="COLOR: #000000">-</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">;<br></span><span style="COLOR: #008080">&nbsp;45</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;x</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">dui[</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">];<br></span><span style="COLOR: #008080">&nbsp;46</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;dui[</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">dui[maxd</span><span style="COLOR: #000000">--</span><span style="COLOR: #000000">];<br></span><span style="COLOR: #008080">&nbsp;47</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;take(</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">);<br></span><span style="COLOR: #008080">&nbsp;48</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">return</span><span style="COLOR: #000000">&nbsp;x;<br></span><span style="COLOR: #008080">&nbsp;49</span>&nbsp;<span style="COLOR: #000000">}<br></span><span style="COLOR: #008080">&nbsp;50</span>&nbsp;<span style="COLOR: #000000"><br></span><span style="COLOR: #008080">&nbsp;51</span>&nbsp;<span style="COLOR: #000000"><br></span><span style="COLOR: #008080">&nbsp;52</span>&nbsp;<span style="COLOR: #000000"></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;djs(</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;st,</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;ee)<br></span><span style="COLOR: #008080">&nbsp;53</span>&nbsp;<span style="COLOR: #000000">{<br></span><span style="COLOR: #008080">&nbsp;54</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;i,j,k,x;<br></span><span style="COLOR: #008080">&nbsp;55</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;adj&nbsp;</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">p;<br></span><span style="COLOR: #008080">&nbsp;56</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;maxd</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">vn;<br></span><span style="COLOR: #008080">&nbsp;57</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">for</span><span style="COLOR: #000000">(i</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">;i</span><span style="COLOR: #000000">&lt;=</span><span style="COLOR: #000000">vn;i</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">)<br></span><span style="COLOR: #008080">&nbsp;58</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;{<br></span><span style="COLOR: #008080">&nbsp;59</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dui[i]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">i;<br></span><span style="COLOR: #008080">&nbsp;60</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;d[i]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">maxint;<br></span><span style="COLOR: #008080">&nbsp;61</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;hx[i]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">i;<br></span><span style="COLOR: #008080">&nbsp;62</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;}<br></span><span style="COLOR: #008080">&nbsp;63</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;d[st]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;<br></span><span style="COLOR: #008080">&nbsp;64</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;father[st]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">st;<br></span><span style="COLOR: #008080">&nbsp;65</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;take(hx[st]);<br></span><span style="COLOR: #008080">&nbsp;66</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;x</span><span style="COLOR: #000000">=</span><span style="COLOR: #0000ff">out</span><span style="COLOR: #000000">();<br></span><span style="COLOR: #008080">&nbsp;67</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">while</span><span style="COLOR: #000000">(x</span><span style="COLOR: #000000">!=-</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">)<br></span><span style="COLOR: #008080">&nbsp;68</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;{<br></span><span style="COLOR: #008080">&nbsp;69</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">if</span><span style="COLOR: #000000">(x</span><span style="COLOR: #000000">==</span><span style="COLOR: #000000">ee)&nbsp;</span><span style="COLOR: #0000ff">break</span><span style="COLOR: #000000">;<br></span><span style="COLOR: #008080">&nbsp;70</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">node[x];<br></span><span style="COLOR: #008080">&nbsp;71</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">while</span><span style="COLOR: #000000">(p</span><span style="COLOR: #000000">!=</span><span style="COLOR: #000000">NULL)<br></span><span style="COLOR: #008080">&nbsp;72</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<br></span><span style="COLOR: #008080">&nbsp;73</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">if</span><span style="COLOR: #000000">(d[p</span><span style="COLOR: #000000">-&gt;</span><span style="COLOR: #000000">ed]</span><span style="COLOR: #000000">&gt;</span><span style="COLOR: #000000">d[x]</span><span style="COLOR: #000000">+</span><span style="COLOR: #000000">p</span><span style="COLOR: #000000">-&gt;</span><span style="COLOR: #000000">ll)<br></span><span style="COLOR: #008080">&nbsp;74</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<br></span><span style="COLOR: #008080">&nbsp;75</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;d[p</span><span style="COLOR: #000000">-&gt;</span><span style="COLOR: #000000">ed]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">d[x]</span><span style="COLOR: #000000">+</span><span style="COLOR: #000000">p</span><span style="COLOR: #000000">-&gt;</span><span style="COLOR: #000000">ll;<br></span><span style="COLOR: #008080">&nbsp;76</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;father[p</span><span style="COLOR: #000000">-&gt;</span><span style="COLOR: #000000">ed]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">x;<br></span><span style="COLOR: #008080">&nbsp;77</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;take(hx[p</span><span style="COLOR: #000000">-&gt;</span><span style="COLOR: #000000">ed]);<br></span><span style="COLOR: #008080">&nbsp;78</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br></span><span style="COLOR: #008080">&nbsp;79</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">p</span><span style="COLOR: #000000">-&gt;</span><span style="COLOR: #000000">pe;<br></span><span style="COLOR: #008080">&nbsp;80</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br></span><span style="COLOR: #008080">&nbsp;81</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x</span><span style="COLOR: #000000">=</span><span style="COLOR: #0000ff">out</span><span style="COLOR: #000000">();<br></span><span style="COLOR: #008080">&nbsp;82</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;}<br></span><span style="COLOR: #008080">&nbsp;83</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">return</span><span style="COLOR: #000000">&nbsp;d[ee];<br></span><span style="COLOR: #008080">&nbsp;84</span>&nbsp;<span style="COLOR: #000000">}<br></span><span style="COLOR: #008080">&nbsp;85</span>&nbsp;<span style="COLOR: #000000"><br></span><span style="COLOR: #008080">&nbsp;86</span>&nbsp;<span style="COLOR: #000000"></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;insert(</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;a,</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;b,</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;c)<br></span><span style="COLOR: #008080">&nbsp;87</span>&nbsp;<span style="COLOR: #000000">{<br></span><span style="COLOR: #008080">&nbsp;88</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;adj&nbsp;</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">p;<br></span><span style="COLOR: #008080">&nbsp;89</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;p</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">node[a];<br></span><span style="COLOR: #008080">&nbsp;90</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;node[a]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">(adj</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">)malloc(</span><span style="COLOR: #0000ff">sizeof</span><span style="COLOR: #000000">(adj));<br></span><span style="COLOR: #008080">&nbsp;91</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;node[a]</span><span style="COLOR: #000000">-&gt;</span><span style="COLOR: #000000">ed</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">b;<br></span><span style="COLOR: #008080">&nbsp;92</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;node[a]</span><span style="COLOR: #000000">-&gt;</span><span style="COLOR: #000000">ll</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">c;<br></span><span style="COLOR: #008080">&nbsp;93</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;node[a]</span><span style="COLOR: #000000">-&gt;</span><span style="COLOR: #000000">pe</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">p;<br></span><span style="COLOR: #008080">&nbsp;94</span>&nbsp;<span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">return</span><span style="COLOR: #000000">&nbsp;</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;<br></span><span style="COLOR: #008080">&nbsp;95</span>&nbsp;<span style="COLOR: #000000">}<br></span><span style="COLOR: #008080">&nbsp;96</span>&nbsp;<span style="COLOR: #000000"><br></span><span style="COLOR: #008080">&nbsp;97</span>&nbsp;<span style="COLOR: #000000"><br></span><span style="COLOR: #008080">&nbsp;98</span>&nbsp;<span style="COLOR: #000000"><br></span><span style="COLOR: #008080">&nbsp;99</span>&nbsp;<span style="COLOR: #000000"><br></span><span style="COLOR: #008080">100</span>&nbsp;<span style="COLOR: #000000"><br></span><span style="COLOR: #008080">101</span>&nbsp;<span style="COLOR: #000000"><br></span><span style="COLOR: #008080">102</span>&nbsp;<span style="COLOR: #000000"></span></div>
<p><br>&nbsp;</p>
<p>刚开始学图论的时候写的...没有精简长度也没有刻意省时间...</p>
<img src ="http://www.cppblog.com/zercal/aggbug/33647.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/zercal/" target="_blank">zercal</a> 2007-10-06 20:04 <a href="http://www.cppblog.com/zercal/archive/2007/10/06/33647.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>匈牙利算法求二分图最大匹配</title><link>http://www.cppblog.com/zercal/archive/2007/10/06/33645.html</link><dc:creator>zercal</dc:creator><author>zercal</author><pubDate>Sat, 06 Oct 2007 11:57:00 GMT</pubDate><guid>http://www.cppblog.com/zercal/archive/2007/10/06/33645.html</guid><wfw:comment>http://www.cppblog.com/zercal/comments/33645.html</wfw:comment><comments>http://www.cppblog.com/zercal/archive/2007/10/06/33645.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cppblog.com/zercal/comments/commentRss/33645.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/zercal/services/trackbacks/33645.html</trackback:ping><description><![CDATA[<div style="BORDER-RIGHT: #cccccc 1px solid; PADDING-RIGHT: 5px; BORDER-TOP: #cccccc 1px solid; PADDING-LEFT: 4px; FONT-SIZE: 13px; PADDING-BOTTOM: 4px; BORDER-LEFT: #cccccc 1px solid; WIDTH: 98%; WORD-BREAK: break-all; PADDING-TOP: 4px; BORDER-BOTTOM: #cccccc 1px solid; BACKGROUND-COLOR: #eeeeee"><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top><span style="COLOR: #000000">#include&nbsp;</span><span style="COLOR: #000000">&lt;</span><span style="COLOR: #000000">stdio.h</span><span style="COLOR: #000000">&gt;</span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top>#include&nbsp;</span><span style="COLOR: #000000">&lt;</span><span style="COLOR: #000000">cstring</span><span style="COLOR: #000000">&gt;</span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">匈牙利算法</span><span style="COLOR: #008000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;&nbsp;xv</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">5</span><span style="COLOR: #000000">,yv</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">5</span><span style="COLOR: #000000">,n</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">5</span><span style="COLOR: #000000">;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">&nbsp;顶点数（数字5认你定）&nbsp;</span><span style="COLOR: #008000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;&nbsp;g[</span><span style="COLOR: #000000">5</span><span style="COLOR: #000000">][</span><span style="COLOR: #000000">5</span><span style="COLOR: #000000">];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">&nbsp;g[i][j]=1&nbsp;表示&nbsp;xi与yj相邻&nbsp;</span><span style="COLOR: #008000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;&nbsp;sy[</span><span style="COLOR: #000000">5</span><span style="COLOR: #000000">];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">&nbsp;辅助：当轮被搜过的y点都是1&nbsp;&nbsp;</span><span style="COLOR: #008000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;&nbsp;cnt,xm[</span><span style="COLOR: #000000">5</span><span style="COLOR: #000000">],ym[</span><span style="COLOR: #000000">5</span><span style="COLOR: #000000">];&nbsp;&nbsp;</span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">&nbsp;输出&nbsp;&nbsp;</span><span style="COLOR: #008000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #0000ff">void</span><span style="COLOR: #000000">&nbsp;&nbsp;init()<br><img id=Codehighlighter1_210_313_Open_Image onclick="this.style.display='none'; Codehighlighter1_210_313_Open_Text.style.display='none'; Codehighlighter1_210_313_Closed_Image.style.display='inline'; Codehighlighter1_210_313_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif" align=top><img id=Codehighlighter1_210_313_Closed_Image style="DISPLAY: none" onclick="this.style.display='none'; Codehighlighter1_210_313_Closed_Text.style.display='none'; Codehighlighter1_210_313_Open_Image.style.display='inline'; Codehighlighter1_210_313_Open_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif" align=top></span><span id=Codehighlighter1_210_313_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"><img src="http://www.cppblog.com/Images/dot.gif"></span><span id=Codehighlighter1_210_313_Open_Text><span style="COLOR: #000000">{<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;cnt</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">&nbsp;;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;memset(g,&nbsp;</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">&nbsp;,</span><span style="COLOR: #0000ff">sizeof</span><span style="COLOR: #000000">(g));<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;memset(xm,</span><span style="COLOR: #000000">-</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">,</span><span style="COLOR: #0000ff">sizeof</span><span style="COLOR: #000000">(xm));<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;memset(ym,</span><span style="COLOR: #000000">-</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">,</span><span style="COLOR: #0000ff">sizeof</span><span style="COLOR: #000000">(ym));<br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif" align=top>}</span></span><span style="COLOR: #000000">&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;path(</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;u)&nbsp;</span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">&nbsp;返回是否找到增广路（递归，时间复杂度O（n*n））&nbsp;</span><span style="COLOR: #008000"><br><img id=Codehighlighter1_362_641_Open_Image onclick="this.style.display='none'; Codehighlighter1_362_641_Open_Text.style.display='none'; Codehighlighter1_362_641_Closed_Image.style.display='inline'; Codehighlighter1_362_641_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif" align=top><img id=Codehighlighter1_362_641_Closed_Image style="DISPLAY: none" onclick="this.style.display='none'; Codehighlighter1_362_641_Closed_Text.style.display='none'; Codehighlighter1_362_641_Open_Image.style.display='inline'; Codehighlighter1_362_641_Open_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif" align=top></span><span id=Codehighlighter1_362_641_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"><img src="http://www.cppblog.com/Images/dot.gif"></span><span id=Codehighlighter1_362_641_Open_Text><span style="COLOR: #000000">{<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;v;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">for</span><span style="COLOR: #000000">(v</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;v</span><span style="COLOR: #000000">&lt;</span><span style="COLOR: #000000">yv;v</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">)<br><img id=Codehighlighter1_401_622_Open_Image onclick="this.style.display='none'; Codehighlighter1_401_622_Open_Text.style.display='none'; Codehighlighter1_401_622_Closed_Image.style.display='inline'; Codehighlighter1_401_622_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif" align=top><img id=Codehighlighter1_401_622_Closed_Image style="DISPLAY: none" onclick="this.style.display='none'; Codehighlighter1_401_622_Closed_Text.style.display='none'; Codehighlighter1_401_622_Open_Image.style.display='inline'; Codehighlighter1_401_622_Open_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span id=Codehighlighter1_401_622_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"><img src="http://www.cppblog.com/Images/dot.gif"></span><span id=Codehighlighter1_401_622_Open_Text><span style="COLOR: #000000">{<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">if</span><span style="COLOR: #000000">((g[u][v]</span><span style="COLOR: #000000">==</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">)</span><span style="COLOR: #000000">&amp;&amp;</span><span style="COLOR: #000000">(sy[v]</span><span style="COLOR: #000000">==</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">))&nbsp;&nbsp;<br><img id=Codehighlighter1_450_616_Open_Image onclick="this.style.display='none'; Codehighlighter1_450_616_Open_Text.style.display='none'; Codehighlighter1_450_616_Closed_Image.style.display='inline'; Codehighlighter1_450_616_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif" align=top><img id=Codehighlighter1_450_616_Closed_Image style="DISPLAY: none" onclick="this.style.display='none'; Codehighlighter1_450_616_Closed_Text.style.display='none'; Codehighlighter1_450_616_Open_Image.style.display='inline'; Codehighlighter1_450_616_Open_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span id=Codehighlighter1_450_616_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"><img src="http://www.cppblog.com/Images/dot.gif"></span><span id=Codehighlighter1_450_616_Open_Text><span style="COLOR: #000000">{&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sy[v]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">if</span><span style="COLOR: #000000">((ym[v]</span><span style="COLOR: #000000">==-</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">)</span><span style="COLOR: #000000">||</span><span style="COLOR: #000000">(path(ym[v])</span><span style="COLOR: #000000">==</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">))<br><img id=Codehighlighter1_532_605_Open_Image onclick="this.style.display='none'; Codehighlighter1_532_605_Open_Text.style.display='none'; Codehighlighter1_532_605_Closed_Image.style.display='inline'; Codehighlighter1_532_605_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif" align=top><img id=Codehighlighter1_532_605_Closed_Image style="DISPLAY: none" onclick="this.style.display='none'; Codehighlighter1_532_605_Closed_Text.style.display='none'; Codehighlighter1_532_605_Open_Image.style.display='inline'; Codehighlighter1_532_605_Open_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span id=Codehighlighter1_532_605_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"><img src="http://www.cppblog.com/Images/dot.gif"></span><span id=Codehighlighter1_532_605_Open_Text><span style="COLOR: #000000">{<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;xm[u]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">v;ym[v]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">u;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">return</span><span style="COLOR: #000000">&nbsp;</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}</span></span><span style="COLOR: #000000">&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}</span></span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;}</span></span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">return</span><span style="COLOR: #000000">&nbsp;</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;&nbsp;&nbsp;&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif" align=top>}</span></span><span style="COLOR: #000000">&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #0000ff">void</span><span style="COLOR: #000000">&nbsp;main()<br><img id=Codehighlighter1_656_989_Open_Image onclick="this.style.display='none'; Codehighlighter1_656_989_Open_Text.style.display='none'; Codehighlighter1_656_989_Closed_Image.style.display='inline'; Codehighlighter1_656_989_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif" align=top><img id=Codehighlighter1_656_989_Closed_Image style="DISPLAY: none" onclick="this.style.display='none'; Codehighlighter1_656_989_Closed_Text.style.display='none'; Codehighlighter1_656_989_Open_Image.style.display='inline'; Codehighlighter1_656_989_Open_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif" align=top></span><span id=Codehighlighter1_656_989_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"><img src="http://www.cppblog.com/Images/dot.gif"></span><span id=Codehighlighter1_656_989_Open_Text><span style="COLOR: #000000">{<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;&nbsp;i,j;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">初始化</span><span style="COLOR: #008000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top></span><span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;init();<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">for</span><span style="COLOR: #000000">(i</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;i</span><span style="COLOR: #000000">&lt;</span><span style="COLOR: #000000">n;i</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">)<br><img id=Codehighlighter1_719_804_Open_Image onclick="this.style.display='none'; Codehighlighter1_719_804_Open_Text.style.display='none'; Codehighlighter1_719_804_Closed_Image.style.display='inline'; Codehighlighter1_719_804_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif" align=top><img id=Codehighlighter1_719_804_Closed_Image style="DISPLAY: none" onclick="this.style.display='none'; Codehighlighter1_719_804_Closed_Text.style.display='none'; Codehighlighter1_719_804_Open_Image.style.display='inline'; Codehighlighter1_719_804_Open_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span id=Codehighlighter1_719_804_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"><img src="http://www.cppblog.com/Images/dot.gif"></span><span id=Codehighlighter1_719_804_Open_Text><span style="COLOR: #000000">{<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">for</span><span style="COLOR: #000000">(j</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;j</span><span style="COLOR: #000000">&lt;</span><span style="COLOR: #000000">n;j</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">)<br><img id=Codehighlighter1_754_798_Open_Image onclick="this.style.display='none'; Codehighlighter1_754_798_Open_Text.style.display='none'; Codehighlighter1_754_798_Closed_Image.style.display='inline'; Codehighlighter1_754_798_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif" align=top><img id=Codehighlighter1_754_798_Closed_Image style="DISPLAY: none" onclick="this.style.display='none'; Codehighlighter1_754_798_Closed_Text.style.display='none'; Codehighlighter1_754_798_Open_Image.style.display='inline'; Codehighlighter1_754_798_Open_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span id=Codehighlighter1_754_798_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"><img src="http://www.cppblog.com/Images/dot.gif"></span><span id=Codehighlighter1_754_798_Open_Text><span style="COLOR: #000000">{<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf(</span><span style="COLOR: #000000">"</span><span style="COLOR: #000000">%d</span><span style="COLOR: #000000">"</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">&amp;</span><span style="COLOR: #000000">g[i][j]);<br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}</span></span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;}</span></span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">核心</span><span style="COLOR: #008000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top></span><span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">for</span><span style="COLOR: #000000">(i</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;i</span><span style="COLOR: #000000">&lt;</span><span style="COLOR: #000000">xv;i</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">)<br><img id=Codehighlighter1_841_952_Open_Image onclick="this.style.display='none'; Codehighlighter1_841_952_Open_Text.style.display='none'; Codehighlighter1_841_952_Closed_Image.style.display='inline'; Codehighlighter1_841_952_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif" align=top><img id=Codehighlighter1_841_952_Closed_Image style="DISPLAY: none" onclick="this.style.display='none'; Codehighlighter1_841_952_Closed_Text.style.display='none'; Codehighlighter1_841_952_Open_Image.style.display='inline'; Codehighlighter1_841_952_Open_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span id=Codehighlighter1_841_952_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"><img src="http://www.cppblog.com/Images/dot.gif"></span><span id=Codehighlighter1_841_952_Open_Text><span style="COLOR: #000000">{<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">if</span><span style="COLOR: #000000">(xm[i]</span><span style="COLOR: #000000">==-</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">)<br><img id=Codehighlighter1_873_946_Open_Image onclick="this.style.display='none'; Codehighlighter1_873_946_Open_Text.style.display='none'; Codehighlighter1_873_946_Closed_Image.style.display='inline'; Codehighlighter1_873_946_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif" align=top><img id=Codehighlighter1_873_946_Closed_Image style="DISPLAY: none" onclick="this.style.display='none'; Codehighlighter1_873_946_Closed_Text.style.display='none'; Codehighlighter1_873_946_Open_Image.style.display='inline'; Codehighlighter1_873_946_Open_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span id=Codehighlighter1_873_946_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"><img src="http://www.cppblog.com/Images/dot.gif"></span><span id=Codehighlighter1_873_946_Open_Text><span style="COLOR: #000000">{<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;memset(sy,</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">,</span><span style="COLOR: #0000ff">sizeof</span><span style="COLOR: #000000">(sy));<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cnt</span><span style="COLOR: #000000">+=</span><span style="COLOR: #000000">path(i);<br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}</span></span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;}</span></span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">打印</span><span style="COLOR: #008000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top></span><span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;printf(</span><span style="COLOR: #000000">"</span><span style="COLOR: #000000">sum=%d</span><span style="COLOR: #000000">"</span><span style="COLOR: #000000">,cnt);<br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif" align=top>}</span></span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span></div>
<img src ="http://www.cppblog.com/zercal/aggbug/33645.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/zercal/" target="_blank">zercal</a> 2007-10-06 19:57 <a href="http://www.cppblog.com/zercal/archive/2007/10/06/33645.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>拓扑排序求逆序对</title><link>http://www.cppblog.com/zercal/archive/2007/10/06/33644.html</link><dc:creator>zercal</dc:creator><author>zercal</author><pubDate>Sat, 06 Oct 2007 11:48:00 GMT</pubDate><guid>http://www.cppblog.com/zercal/archive/2007/10/06/33644.html</guid><wfw:comment>http://www.cppblog.com/zercal/comments/33644.html</wfw:comment><comments>http://www.cppblog.com/zercal/archive/2007/10/06/33644.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cppblog.com/zercal/comments/commentRss/33644.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/zercal/services/trackbacks/33644.html</trackback:ping><description><![CDATA[<p>&nbsp;</p>
<div style="BORDER-RIGHT: #cccccc 1px solid; PADDING-RIGHT: 5px; BORDER-TOP: #cccccc 1px solid; PADDING-LEFT: 4px; FONT-SIZE: 13px; PADDING-BOTTOM: 4px; BORDER-LEFT: #cccccc 1px solid; WIDTH: 98%; WORD-BREAK: break-all; PADDING-TOP: 4px; BORDER-BOTTOM: #cccccc 1px solid; BACKGROUND-COLOR: #eeeeee"><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top><span style="COLOR: #000000">#include</span><span style="COLOR: #000000">&lt;</span><span style="COLOR: #000000">iostream</span><span style="COLOR: #000000">&gt;</span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #0000ff">using</span><span style="COLOR: #000000">&nbsp;</span><span style="COLOR: #0000ff">namespace</span><span style="COLOR: #000000">&nbsp;std;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;a[</span><span style="COLOR: #000000">110000</span><span style="COLOR: #000000">],b[</span><span style="COLOR: #000000">110000</span><span style="COLOR: #000000">],res;</span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">res需要赋初值0&nbsp;</span><span style="COLOR: #008000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;merge(</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;st,</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;mid,</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;ed)<br><img id=Codehighlighter1_116_404_Open_Image onclick="this.style.display='none'; Codehighlighter1_116_404_Open_Text.style.display='none'; Codehighlighter1_116_404_Closed_Image.style.display='inline'; Codehighlighter1_116_404_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif" align=top><img id=Codehighlighter1_116_404_Closed_Image style="DISPLAY: none" onclick="this.style.display='none'; Codehighlighter1_116_404_Closed_Text.style.display='none'; Codehighlighter1_116_404_Open_Image.style.display='inline'; Codehighlighter1_116_404_Open_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif" align=top></span><span id=Codehighlighter1_116_404_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"><img src="http://www.cppblog.com/Images/dot.gif"></span><span id=Codehighlighter1_116_404_Open_Text><span style="COLOR: #000000">{<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;sa,ea,sb,eb,i,j;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;sa</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">st,ea</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">mid,sb</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">mid</span><span style="COLOR: #000000">+</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">,eb</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">ed;i</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">j</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">while</span><span style="COLOR: #000000">(sa</span><span style="COLOR: #000000">&lt;=</span><span style="COLOR: #000000">ea</span><span style="COLOR: #000000">&amp;&amp;</span><span style="COLOR: #000000">sb</span><span style="COLOR: #000000">&lt;=</span><span style="COLOR: #000000">eb)<br><img id=Codehighlighter1_200_290_Open_Image onclick="this.style.display='none'; Codehighlighter1_200_290_Open_Text.style.display='none'; Codehighlighter1_200_290_Closed_Image.style.display='inline'; Codehighlighter1_200_290_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif" align=top><img id=Codehighlighter1_200_290_Closed_Image style="DISPLAY: none" onclick="this.style.display='none'; Codehighlighter1_200_290_Closed_Text.style.display='none'; Codehighlighter1_200_290_Open_Image.style.display='inline'; Codehighlighter1_200_290_Open_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span id=Codehighlighter1_200_290_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"><img src="http://www.cppblog.com/Images/dot.gif"></span><span id=Codehighlighter1_200_290_Open_Text><span style="COLOR: #000000">{<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">if</span><span style="COLOR: #000000">(a[sa]</span><span style="COLOR: #000000">&lt;=</span><span style="COLOR: #000000">b[sb])<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b[i</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">a[sa</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">];<br><img id=Codehighlighter1_246_287_Open_Image onclick="this.style.display='none'; Codehighlighter1_246_287_Open_Text.style.display='none'; Codehighlighter1_246_287_Closed_Image.style.display='inline'; Codehighlighter1_246_287_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif" align=top><img id=Codehighlighter1_246_287_Closed_Image style="DISPLAY: none" onclick="this.style.display='none'; Codehighlighter1_246_287_Closed_Text.style.display='none'; Codehighlighter1_246_287_Open_Image.style.display='inline'; Codehighlighter1_246_287_Open_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">else</span><span id=Codehighlighter1_246_287_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"><img src="http://www.cppblog.com/Images/dot.gif"></span><span id=Codehighlighter1_246_287_Open_Text><span style="COLOR: #000000">{<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b[i</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">a[sb</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">];<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res</span><span style="COLOR: #000000">+=</span><span style="COLOR: #000000">mid</span><span style="COLOR: #000000">+</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">-</span><span style="COLOR: #000000">sa;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}</span></span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;}</span></span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">while</span><span style="COLOR: #000000">(sa</span><span style="COLOR: #000000">&lt;=</span><span style="COLOR: #000000">ea)<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b[i</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">a[sa</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">];<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">while</span><span style="COLOR: #000000">(sb</span><span style="COLOR: #000000">&lt;=</span><span style="COLOR: #000000">eb)<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b[i</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">b[sb</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">];<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">for</span><span style="COLOR: #000000">(j</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;j</span><span style="COLOR: #000000">&lt;</span><span style="COLOR: #000000">i;j</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">)<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[st</span><span style="COLOR: #000000">+</span><span style="COLOR: #000000">j]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">b[j];<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">return</span><span style="COLOR: #000000">&nbsp;</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;&nbsp;&nbsp;&nbsp;&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif" align=top>}</span></span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;mst(</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;st,</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;ed)<br><img id=Codehighlighter1_430_546_Open_Image onclick="this.style.display='none'; Codehighlighter1_430_546_Open_Text.style.display='none'; Codehighlighter1_430_546_Closed_Image.style.display='inline'; Codehighlighter1_430_546_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif" align=top><img id=Codehighlighter1_430_546_Closed_Image style="DISPLAY: none" onclick="this.style.display='none'; Codehighlighter1_430_546_Closed_Text.style.display='none'; Codehighlighter1_430_546_Open_Image.style.display='inline'; Codehighlighter1_430_546_Open_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif" align=top></span><span id=Codehighlighter1_430_546_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"><img src="http://www.cppblog.com/Images/dot.gif"></span><span id=Codehighlighter1_430_546_Open_Text><span style="COLOR: #000000">{<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;mid,i,j,k;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">if</span><span style="COLOR: #000000">(st</span><span style="COLOR: #000000">&lt;</span><span style="COLOR: #000000">ed)<br><img id=Codehighlighter1_460_532_Open_Image onclick="this.style.display='none'; Codehighlighter1_460_532_Open_Text.style.display='none'; Codehighlighter1_460_532_Closed_Image.style.display='inline'; Codehighlighter1_460_532_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif" align=top><img id=Codehighlighter1_460_532_Closed_Image style="DISPLAY: none" onclick="this.style.display='none'; Codehighlighter1_460_532_Closed_Text.style.display='none'; Codehighlighter1_460_532_Open_Image.style.display='inline'; Codehighlighter1_460_532_Open_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span id=Codehighlighter1_460_532_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"><img src="http://www.cppblog.com/Images/dot.gif"></span><span id=Codehighlighter1_460_532_Open_Text><span style="COLOR: #000000">{<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;mid</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">(st</span><span style="COLOR: #000000">+</span><span style="COLOR: #000000">ed)</span><span style="COLOR: #000000">/</span><span style="COLOR: #000000">2</span><span style="COLOR: #000000">;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;mst(st,mid);<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;mst(mid</span><span style="COLOR: #000000">+</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">,ed);<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;merge(st,mid,ed);<br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;}</span></span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">return</span><span style="COLOR: #000000">&nbsp;</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;&nbsp;&nbsp;&nbsp;&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif" align=top>}</span></span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span></div>
<img src ="http://www.cppblog.com/zercal/aggbug/33644.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/zercal/" target="_blank">zercal</a> 2007-10-06 19:48 <a href="http://www.cppblog.com/zercal/archive/2007/10/06/33644.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>中国剩余定理（菜鸟版，勉强能用）</title><link>http://www.cppblog.com/zercal/archive/2007/10/06/33643.html</link><dc:creator>zercal</dc:creator><author>zercal</author><pubDate>Sat, 06 Oct 2007 11:43:00 GMT</pubDate><guid>http://www.cppblog.com/zercal/archive/2007/10/06/33643.html</guid><wfw:comment>http://www.cppblog.com/zercal/comments/33643.html</wfw:comment><comments>http://www.cppblog.com/zercal/archive/2007/10/06/33643.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cppblog.com/zercal/comments/commentRss/33643.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/zercal/services/trackbacks/33643.html</trackback:ping><description><![CDATA[<div style="BORDER-RIGHT: #cccccc 1px solid; PADDING-RIGHT: 5px; BORDER-TOP: #cccccc 1px solid; PADDING-LEFT: 4px; FONT-SIZE: 13px; PADDING-BOTTOM: 4px; BORDER-LEFT: #cccccc 1px solid; WIDTH: 98%; WORD-BREAK: break-all; PADDING-TOP: 4px; BORDER-BOTTOM: #cccccc 1px solid; BACKGROUND-COLOR: #eeeeee"><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top><span style="COLOR: #000000">#include</span><span style="COLOR: #000000">&lt;</span><span style="COLOR: #000000">iostream</span><span style="COLOR: #000000">&gt;</span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #0000ff">using</span><span style="COLOR: #000000">&nbsp;</span><span style="COLOR: #0000ff">namespace</span><span style="COLOR: #000000">&nbsp;std;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #0000ff">#define</span><span style="COLOR: #000000">&nbsp;maxn&nbsp;10000&nbsp;</span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">数的数量</span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;num[maxn],lef[maxn];&nbsp;</span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">除数和余数&nbsp;</span><span style="COLOR: #008000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #0000ff">long</span><span style="COLOR: #000000">&nbsp;</span><span style="COLOR: #0000ff">long</span><span style="COLOR: #000000">&nbsp;mm[maxn],use[maxn];<br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">扩展欧几里德求逆元&nbsp;</span><span style="COLOR: #008000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;extended_euclid(</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;a,</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;b,</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;</span><span style="COLOR: #000000">&amp;</span><span style="COLOR: #000000">x,</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;</span><span style="COLOR: #000000">&amp;</span><span style="COLOR: #000000">y)&nbsp;<br><img id=Codehighlighter1_195_365_Open_Image onclick="this.style.display='none'; Codehighlighter1_195_365_Open_Text.style.display='none'; Codehighlighter1_195_365_Closed_Image.style.display='inline'; Codehighlighter1_195_365_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif" align=top><img id=Codehighlighter1_195_365_Closed_Image style="DISPLAY: none" onclick="this.style.display='none'; Codehighlighter1_195_365_Closed_Text.style.display='none'; Codehighlighter1_195_365_Open_Image.style.display='inline'; Codehighlighter1_195_365_Open_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif" align=top></span><span id=Codehighlighter1_195_365_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"><img src="http://www.cppblog.com/Images/dot.gif"></span><span id=Codehighlighter1_195_365_Open_Text><span style="COLOR: #000000">{&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">if</span><span style="COLOR: #000000">(b</span><span style="COLOR: #000000">==</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">)&nbsp;<br><img id=Codehighlighter1_216_260_Open_Image onclick="this.style.display='none'; Codehighlighter1_216_260_Open_Text.style.display='none'; Codehighlighter1_216_260_Closed_Image.style.display='inline'; Codehighlighter1_216_260_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif" align=top><img id=Codehighlighter1_216_260_Closed_Image style="DISPLAY: none" onclick="this.style.display='none'; Codehighlighter1_216_260_Closed_Text.style.display='none'; Codehighlighter1_216_260_Open_Image.style.display='inline'; Codehighlighter1_216_260_Open_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span id=Codehighlighter1_216_260_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"><img src="http://www.cppblog.com/Images/dot.gif"></span><span id=Codehighlighter1_216_260_Open_Text><span style="COLOR: #000000">{&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">;y</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">return</span><span style="COLOR: #000000">&nbsp;a;&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;}</span></span><span style="COLOR: #000000">&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;t,d;&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;d</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">extended_euclid(b,a</span><span style="COLOR: #000000">%</span><span style="COLOR: #000000">b,x,y);&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;t</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">x;&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;x</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">y;&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;y</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">t</span><span style="COLOR: #000000">-</span><span style="COLOR: #000000">(a</span><span style="COLOR: #000000">/</span><span style="COLOR: #000000">b)</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">y;&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">return</span><span style="COLOR: #000000">&nbsp;d;&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif" align=top>}</span></span><span style="COLOR: #000000">&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">返回第一个正的解&nbsp;n为数的数量&nbsp;</span><span style="COLOR: #008000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span><span style="COLOR: #0000ff">long</span><span style="COLOR: #000000">&nbsp;</span><span style="COLOR: #0000ff">long</span><span style="COLOR: #000000">&nbsp;chinaleft(</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;n)<br><img id=Codehighlighter1_415_674_Open_Image onclick="this.style.display='none'; Codehighlighter1_415_674_Open_Text.style.display='none'; Codehighlighter1_415_674_Closed_Image.style.display='inline'; Codehighlighter1_415_674_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif" align=top><img id=Codehighlighter1_415_674_Closed_Image style="DISPLAY: none" onclick="this.style.display='none'; Codehighlighter1_415_674_Closed_Text.style.display='none'; Codehighlighter1_415_674_Open_Image.style.display='inline'; Codehighlighter1_415_674_Open_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif" align=top></span><span id=Codehighlighter1_415_674_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"><img src="http://www.cppblog.com/Images/dot.gif"></span><span id=Codehighlighter1_415_674_Open_Text><span style="COLOR: #000000">{<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;i,j,k,x,y;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">long</span><span style="COLOR: #000000">&nbsp;</span><span style="COLOR: #0000ff">long</span><span style="COLOR: #000000">&nbsp;pm,res;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">for</span><span style="COLOR: #000000">(i</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">,pm</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">;i</span><span style="COLOR: #000000">&lt;</span><span style="COLOR: #000000">n;i</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">)<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pm</span><span style="COLOR: #000000">*=</span><span style="COLOR: #000000">num[i];<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">for</span><span style="COLOR: #000000">(i</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;i</span><span style="COLOR: #000000">&lt;</span><span style="COLOR: #000000">n;i</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">)<br><img id=Codehighlighter1_508_585_Open_Image onclick="this.style.display='none'; Codehighlighter1_508_585_Open_Text.style.display='none'; Codehighlighter1_508_585_Closed_Image.style.display='inline'; Codehighlighter1_508_585_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif" align=top><img id=Codehighlighter1_508_585_Closed_Image style="DISPLAY: none" onclick="this.style.display='none'; Codehighlighter1_508_585_Closed_Text.style.display='none'; Codehighlighter1_508_585_Open_Image.style.display='inline'; Codehighlighter1_508_585_Open_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span id=Codehighlighter1_508_585_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"><img src="http://www.cppblog.com/Images/dot.gif"></span><span id=Codehighlighter1_508_585_Open_Text><span style="COLOR: #000000">{<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;mm[i]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">pm</span><span style="COLOR: #000000">/</span><span style="COLOR: #000000">num[i];<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;extended_euclid(mm[i],num[i],x,y);<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;use[i]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">mm[i]</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">x;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;}</span></span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">for</span><span style="COLOR: #000000">(i</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">,res</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;i</span><span style="COLOR: #000000">&lt;</span><span style="COLOR: #000000">n;i</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">)<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">(res</span><span style="COLOR: #000000">+</span><span style="COLOR: #000000">lef[i]</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">use[i])</span><span style="COLOR: #000000">%</span><span style="COLOR: #000000">pm;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">if</span><span style="COLOR: #000000">(res</span><span style="COLOR: #000000">&lt;</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">)&nbsp;res</span><span style="COLOR: #000000">+=</span><span style="COLOR: #000000">pm;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">return</span><span style="COLOR: #000000">&nbsp;res;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif" align=top>}</span></span><span style="COLOR: #000000"><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span></div>
<p>这一阵子在狂啃数论,真是不喜欢这种纯数学的东西...马上都要比赛了才刚刚会中国剩余定理...真是丢脸...<br></p>
<p><br>&nbsp;</p>
<p>&nbsp;</p>
<img src ="http://www.cppblog.com/zercal/aggbug/33643.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/zercal/" target="_blank">zercal</a> 2007-10-06 19:43 <a href="http://www.cppblog.com/zercal/archive/2007/10/06/33643.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>扩展欧几里德</title><link>http://www.cppblog.com/zercal/archive/2007/10/06/33642.html</link><dc:creator>zercal</dc:creator><author>zercal</author><pubDate>Sat, 06 Oct 2007 11:40:00 GMT</pubDate><guid>http://www.cppblog.com/zercal/archive/2007/10/06/33642.html</guid><wfw:comment>http://www.cppblog.com/zercal/comments/33642.html</wfw:comment><comments>http://www.cppblog.com/zercal/archive/2007/10/06/33642.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cppblog.com/zercal/comments/commentRss/33642.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/zercal/services/trackbacks/33642.html</trackback:ping><description><![CDATA[<div style="BORDER-RIGHT: #cccccc 1px solid; PADDING-RIGHT: 5px; BORDER-TOP: #cccccc 1px solid; PADDING-LEFT: 4px; FONT-SIZE: 13px; PADDING-BOTTOM: 4px; BORDER-LEFT: #cccccc 1px solid; WIDTH: 98%; WORD-BREAK: break-all; PADDING-TOP: 4px; BORDER-BOTTOM: #cccccc 1px solid; BACKGROUND-COLOR: #eeeeee">
<p><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;extended_euclid(</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;a,</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;b,</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;</span><span style="COLOR: #000000">&amp;</span><span style="COLOR: #000000">x,</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;</span><span style="COLOR: #000000">&amp;</span><span style="COLOR: #000000">y)&nbsp;<br><img id=Codehighlighter1_48_218_Open_Image onclick="this.style.display='none'; Codehighlighter1_48_218_Open_Text.style.display='none'; Codehighlighter1_48_218_Closed_Image.style.display='inline'; Codehighlighter1_48_218_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif" align=top></span><span id=Codehighlighter1_48_218_Open_Text><span style="COLOR: #000000">{&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">if</span><span style="COLOR: #000000">(b</span><span style="COLOR: #000000">==</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">)&nbsp;<br><img id=Codehighlighter1_69_113_Open_Image onclick="this.style.display='none'; Codehighlighter1_69_113_Open_Text.style.display='none'; Codehighlighter1_69_113_Closed_Image.style.display='inline'; Codehighlighter1_69_113_Closed_Text.style.display='inline';" src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif" align=top><img id=Codehighlighter1_69_113_Closed_Image style="DISPLAY: none; WIDTH: 11px; HEIGHT: 16px" onclick="this.style.display='none'; Codehighlighter1_69_113_Closed_Text.style.display='none'; Codehighlighter1_69_113_Open_Image.style.display='inline'; Codehighlighter1_69_113_Open_Text.style.display='inline';" height=16 src="http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif" width=11 align=top>&nbsp;&nbsp;&nbsp;</span><span id=Codehighlighter1_69_113_Closed_Text style="BORDER-RIGHT: #808080 1px solid; BORDER-TOP: #808080 1px solid; DISPLAY: none; BORDER-LEFT: #808080 1px solid; BORDER-BOTTOM: #808080 1px solid; BACKGROUND-COLOR: #ffffff"></span><span id=Codehighlighter1_69_113_Open_Text><span style="COLOR: #000000">{&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">;y</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">return</span><span style="COLOR: #000000">&nbsp;a;&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}</span></span><span style="COLOR: #000000">&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">&nbsp;t,d;&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;d</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">extended_euclid(b,a</span><span style="COLOR: #000000">%</span><span style="COLOR: #000000">b,x,y);&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">x;&nbsp;</span></span><span><span style="COLOR: #000000">&nbsp;<br></span></span><span><span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">y;&nbsp;<br></span></span><span><span style="COLOR: #000000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;y</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">t</span><span style="COLOR: #000000">-</span><span style="COLOR: #000000">(a</span><span style="COLOR: #000000">/</span><span style="COLOR: #000000">b)</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">y;&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align=top>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="COLOR: #0000ff">return</span><span style="COLOR: #000000">&nbsp;d;&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif" align=top>}</span></span><span style="COLOR: #000000">&nbsp;<br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top><br><img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align=top></span></p>
</div>
输出x*a+y*b=gcd(a,b)的一个特解
<img src ="http://www.cppblog.com/zercal/aggbug/33642.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/zercal/" target="_blank">zercal</a> 2007-10-06 19:40 <a href="http://www.cppblog.com/zercal/archive/2007/10/06/33642.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>又开博了</title><link>http://www.cppblog.com/zercal/archive/2007/10/06/33638.html</link><dc:creator>zercal</dc:creator><author>zercal</author><pubDate>Sat, 06 Oct 2007 11:13:00 GMT</pubDate><guid>http://www.cppblog.com/zercal/archive/2007/10/06/33638.html</guid><wfw:comment>http://www.cppblog.com/zercal/comments/33638.html</wfw:comment><comments>http://www.cppblog.com/zercal/archive/2007/10/06/33638.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cppblog.com/zercal/comments/commentRss/33638.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/zercal/services/trackbacks/33638.html</trackback:ping><description><![CDATA[<p>这次的博客主要是贴些自己的代码(不过本人水平有限~大牛们就不要bs哈)还有其他的资料什么的，私人的事情就不写了（再说我现在也没啥爆点了）.<br></p>
<p>&nbsp;</p>
<img src ="http://www.cppblog.com/zercal/aggbug/33638.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/zercal/" target="_blank">zercal</a> 2007-10-06 19:13 <a href="http://www.cppblog.com/zercal/archive/2007/10/06/33638.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item></channel></rss>