一道难题的程序思路
程序思路应该怎样？有n个智能程序将参加淘汰赛。淘汰赛赛程设置如下：每次选择两个没有被淘汰的程序进行比赛，胜利的程序留下，失败的淘汰，比赛没有平局。比赛一直进行到只剩下一个程序，这个程序就是冠军。如果在以前的历史纪录中，程序A战胜了程序B，那么在这次比赛中A便一定能战胜B。如果在以前的历史纪录中，程序A和程序B之间没有比赛，那么在这次比赛中，既有可能A战胜B，也有可能B战胜A。因此合理的安排淘汰赛程可能会使某个程序取得冠军，给出你程序以前的比赛记录m条（形如“A曾经战胜B”），判断哪些程序有可能获得冠军。 程序作为点，然后如果a战胜b那么a -> b有边。然后b的入度加1，最后如果没入度的点就可能是冠军了吧？ 排除输了的，剩下的都可能赢 首先扫描所有比赛记录，接着用这个记录判断所有比赛的胜负结果
如果比赛结果无法确定，则记下记号，先选其中一种结果
这样就能得到第二轮比赛名单， 接下来再照些方法继续，最终得到冠军程序，记录下来
对做过记号的比赛选择另一种结果，按前面的方法重新比赛获得新的冠军，同样记录下来
这样循环到最后就能知道哪些有可能获得冠军了 能否考虑N行N-1列的表格的方式记录相互之间的胜负关系.这样在比之前先扫描比赛记录,把胜负关系记录在表格中,然后每次比赛就扫描表格,根据相互关系来决定谁将被淘汰.并把结果记录到表格.... 原帖由 DieIng 于 2009-3-1 19:57 发表 https://www.gdutbbs.com/images/common/back.gif
程序作为点，然后如果a战胜b那么a -> b有边。然后b的入度加1，最后如果没入度的点就可能是冠军了吧？
假如有a和b 没比过赛 ，就存在a->b和b->a
那样就有两种情况，
加上没有入度的点，这些都可能是源点
枚举所有可能源点 ，容许邻接无向边，能做做类似 拓扑分治排序，没有回边（剔除邻接无向边），则为可能源点（即冠军）
and 大家继续 无向边很容易判。
路过、、、、、 膜拜，楼下继续 我是来膜拜楼上的 今天想了一下。
假如有 a->bb->a
可以抽象成c={a,b} 变成一点删除 a，b c邻接的a，b以前的邻接点
这样形成新的图
就可以直接判点的入度为0即为可能的冠军
这样就编程简单sb问题了 原帖由 DieIng 于 2009-3-1 19:57 发表 https://www.gdutbbs.com/images/common/back.gif
程序作为点，然后如果a战胜b那么a -> b有边。然后b的入度加1，最后如果没入度的点就可能是冠军了吧？
1、建图1：程序作为点，然后如果a战胜b那么a -> b有边。然后b的入度加1。
2、建邻接表：对于点a，如果图1有没有b->a的变（即有a->b的边，或者a、b之间没有边)，则把b添加到a的链接上。
3、判断：例如判断点a，
k = (n - log2 n)
1)如果a的入度 >= k，则不可能赢。
2)如果a的入度 < k，则取邻接表中链接在a上的入度最多的点(假设为b1)，然后取第二多的(b2)....bm (m = n-k-1 (即log2 n - 1) )
类似a，递归判断b1的入度（除去a->b1的入度) 是否小于k+1，
b2的入度（除去a->b2的入度) 是否小于k+2....
如果递归判断成功，则有可能。 以上思路是基于，
如果点a的入度大于等于(n - log2 n)时，即不可能与 log2 n 个点比赛最后成为冠军。
而如果小于(n - log2 n)，则在a可能胜的点中存在b1能在n/2的点中胜出，b2能在n/4点中胜出。
递归判断。
但正确性还没得到具体证明.... 我又来膜拜楼上了
回复 10楼 kids 的帖子
其实你想说的是强连通缩点吧， 膜拜，楼下继续 其实你想说的是强连通缩点吧，DieIng 发表于 2009-3-11 12:08 https://www.gdutbbs.com/images/common/back.gif
dp也行。
强连通缩点也行。
飞过。。。。。 如何dp。。状态是啥，求教 m i与j的可能
i赢j m =1
i输给j m=0
i与j没有记录 两种可能性 m=2
i<k<j 枚举所有
m m两个都为1即m=1表示i能够打赢j
m m前一个1后一个3 也为 m=1
前一个3后一个1 也为m=1
3 3 m=3
存在0 m=0
O(n^3) 不知道有没漏洞 不对吧？他没说胜负存在递推性
页:
[1]
2