一道难题的程序思路

我想飞

程序思路应该怎样？

有n个智能程序将参加淘汰赛。淘汰赛赛程设置如下：每次选择两个没有被淘汰的程序进行比赛，胜利的程序留下，失败的淘汰，比赛没有平局。比赛一直进行到只剩下一个程序，这个程序就是冠军。如果在以前的历史纪录中，程序A战胜了程序B，那么在这次比赛中A便一定能战胜B。如果在以前的历史纪录中，程序A和程序B之间没有比赛，那么在这次比赛中，既有可能A战胜B，也有可能B战胜A。因此合理的安排淘汰赛程可能会使某个程序取得冠军，给出你程序以前的比赛记录m条（形如“A曾经战胜B”），判断哪些程序有可能获得冠军。

DieIng

程序作为点，然后如果a战胜b那么a -> b有边。然后b的入度加1，最后如果没入度的点就可能是冠军了吧？

R1212ST

排除输了的，剩下的都可能赢

皇家救星

首先扫描所有比赛记录，接着用这个记录判断所有比赛的胜负结果

如果比赛结果无法确定，则记下记号，先选其中一种结果

这样就能得到第二轮比赛名单，　接下来再照些方法继续，最终得到冠军程序，记录下来

对做过记号的比赛选择另一种结果，按前面的方法重新比赛获得新的冠军，同样记录下来

这样循环到最后就能知道哪些有可能获得冠军了

jinry

能否考虑N行N-1列的表格的方式记录相互之间的胜负关系.这样在比之前先扫描比赛记录,把胜负关系记录在表格中,然后每次比赛就扫描表格,根据相互关系来决定谁将被淘汰.并把结果记录到表格....

kids

原帖由 DieIng 于 2009-3-1 19:57 发表
程序作为点，然后如果a战胜b那么a -> b有边。然后b的入度加1，最后如果没入度的点就可能是冠军了吧？

假如有a和b   没比过赛 ，就存在a->b和b->a
那样就有两种情况，
加上没有入度的点，这些都可能是源点

枚举所有可能源点 ，容许邻接无向边，能做做类似 拓扑分治排序，没有回边（剔除邻接无向边），则为可能源点（即冠军）



and   大家继续

kids

无向边很容易判。
路过、、、、、

henrycui

膜拜，楼下继续

DieIng

我是来膜拜楼上的[em021]

kids

今天想了一下。
假如有 a->b  b->a
可以抽象成  c={a,b} 变成一点  删除 a，b      c邻接的a，b以前的邻接点


这样形成新的图
就可以直接  判点的入度为0  即为可能的冠军


这样就编程简单sb问题了

邪恶颖龙

原帖由 DieIng 于 2009-3-1 19:57 发表
程序作为点，然后如果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点中胜出。
递归判断。

但正确性还没得到具体证明....

DieIng

我又来膜拜楼上了

DieIng

其实你想说的是强连通缩点吧，

henrycui

膜拜，楼下继续

kids

其实你想说的是强连通缩点吧，
DieIng 发表于 2009-3-11 12:08

dp也行。
强连通缩点也行。
飞过。。。。。

DieIng

如何dp。。状态是啥，求教

kids

m[i][j]   i与j的可能
i赢j m[i][j] =1
i输给j m[i][j]=0
i与j没有记录 两种可能性 m[i][j]=2

i<k<j 枚举所有  
m[i][k] m[k][j]两个都为1即m[i][j]=1表示i能够打赢j
m[i][k] m[k][j]  前一个1后一个3 也为 m[i][j]=1
前一个3后一个1 也为m[i][j]=1
3     3   m[i][j]=3
存在0   m[i][j]=0


O(n^3)

kids

不知道有没漏洞

DieIng

不对吧？他没说胜负存在递推性