一、题意简述 　　

　　本题要求根据可能性列表将糊涂的记者Tom送回报社的速记符号和平时所用的单词建立对应，使总的可能性最大，求最大的可能性值。速记符号必有单词与之对应，且仅有一个单词与之对应。单词可能没有符号与之对应，若有符号与之对应，则与其对应的符号数不超过1。可能性均被描述为(0,1)之间的实数，精度要求为1e-12。若无解则输出NO ANSWER。

二、算法分析 　　

　　1、图论模型
　　
　　题目中给出了两个相对独立的集合并给出了这两个集合之间的一些联系，要求一个"最优"的解。很容易就可以同一个图论模型联系起来--二分图最佳匹配。在此，先给出几个概念：

　　（１）二分图：图G的顶点集合V分成两部分X和Y，G中每条边的两个端点一定一个属于X而另一个属于Y，这样的图称作二 分图。
　　（２）匹配：设Ｇ＝[V,E]是一个无向图，M∈E是Ｇ的若干条边的集合，如果Ｍ中的任意两条边都没有公共的端点，就称Ｍ是一个匹配。
　　（３）二分图最佳匹配：Ｇ是加权完全二分图，顶点划分为两个集合X,Y；X={X1,X2,…,Xn}，Y={Y1,Y2,…,Ym}，求权和最大的完备匹配，这种完备匹配称为最佳匹配。 　　

　　虽然最佳匹配的定义与本题有一定出入，我们仍然可以通过一系列改造借用它的算法。
　　将速记符号的集合看成X，将单词的集合看成Y,当一个速记符号Xi可能被翻译为一个单词Yj,且可能性大小为Ri,j时，就在它们之间连一条边，边权设为ln(Ri,j)。这样原问题就被转化为求二分图最佳匹配的问题了。 　　

　　2、求二分图最佳匹配的算法 　　

　　算法一、最大费用最大流 　　
　　该算法是从最小费用最大流的算法演化而来的，只需将寻找可增广轨时寻找最短路更改为寻找最长路即可。在原图上增加一个附加源s和一个附加汇t。从s分别向X中的顶点引一条边，容量为１，费用为０。从Y中的顶点分别向t引一条边，容量为１，费用为０。原图中的所有边的容量为１，费用为原边权。然后用上述方法求解即可。该算法比较普及，但若不经优化实现起来消耗空间较大，当数据量达到一定程度时就不得不使用保护模式，而使用保护模式势必会大大降低速度。因此我们另外介绍一种有效算法-- 　　

　　算法二、可行顶标法 　　
　　为了说明该算法，我们引入两个概念。

　　1、二分图G的可行顶标：对于X集合中的任一定点x和Y集合中的任一定点y，满足条件

　　　　　　　　　　　　　　　
则称L(u)是G的可行顶标。初始时

　　　　　　　　　　　　　　　 　

　　２、相等子图GL:由边集EL={xy∈E的边集E,L(x)+L(y)=W(xy)}组成的Ｇ的生成子图，称作相等子图，记为GL.。 　　
　　算法简单描述如下：对于每一个相等子图从1到n求前n个点完备匹配，如果没找到，则修改顶标后反复此过程直至求解完毕。 　　
　　修改顶标的方法如下：记GL的匹配中，外点的集合为S，内点的集合为T。设AL=min{L(x)+L(y)-W(xy),x∈S,y T}，则新的顶标

　　　　　　　　　　　　　　　 　　

　　上述即为可行顶标法求解的方法，该算法有空间小，速度快，编程简单等优点，在竞赛中是十分有用的。

三、注意点

　　１、由于本题的运算为实数运算（不精确）且题中有明确的精度规定，所以在计算过程中，应特别注意限制精度。
　　２、由于本题在求解过程中将实际的安全系数进行了修改处理，解中的安全系数并不是解，所以在输出时，应根据解的流量状况重新计算实际的安全系数。
　　３、由于本题要求答案保留4位有效数字，输出时应特殊处理。这里给出一种方法：反复将最后得出的实数x扩大10倍直至大等于104，将扩大的次数记为k，将x取整，再缩小10k倍，限定场宽为x:k+2:k，即可达到输出4位有效数字的目的。当进位后为1的数要另外判断。

四、小结

　　回顾本题的解题过程，首先，通过分析将原题中复杂的实际问题抽象为一个基本图论模型，然后，在对输入数据进行一定处理使其符合应用标准后，"套用"图论的常用算法求解。
　　图论是一个应用十分广泛的数学分支，在计算机编程中，对于某些问题，其它算法束手无策时，可以尝试用图论算法进行求解，也许会有柳暗花明的效果。
　　图论来源于实际问题，与实际问题联系紧密，深入研究图论算法，在倡导与实际相联系的今天，是十分重要且必要的。

[参考书目]
　　
　　 《青少年国际和全国信息学（计算机）奥林匹克竞赛指导－－图论的算法与程序设计》　吴文虎　王建德　　清华大学出版社