misschuer

常用链接

统计

积分与排名

百事通

最新评论

竞赛图

这是一个全新的概念,省赛上出现了这种题目,zoj 3332
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3332
图中任意两点,至少存在一条有向边,构成一个哈密顿(好像和 哈密尔顿 不同)路;
对于一条以构建的哈密顿路的n个点(第1个点到第n个点,注意 第i个点 不一定是 点i ,eg,1 - 4 - 2 - 3,第2个点为4,第3个点为2,第4个点为3),
插入第n+1个点,肯定找到一条有向路与之相连
这里分3种情况
1>         第n + 1个点 与第一个点相连,使第n + 1个点成为第一个点
2>         最后一个点与第n+1个点相连,使第n + 1个点成为最后一个点
3>         能在原哈密顿路中找到一个相连的点 ,第i个点 和 第i+1个点  使得   (第i个点与第n+1个点  且  第n+1个点与第i+1个点)相连,所以在第i个点与第i+1个点中插入第n+1个点,这是典型的链式操作;

因此,用STL里的list即可完成如上3步骤;
我只是略懂略懂,不足之处,请指教,并附上代码


#include <iostream>
#define M 101
#include 
<list>
using namespace std;
bool f[ M ][ M ];
bool flag;
list 
<int> L;
list 
<int>::iterator it , pre;

void init (int n){
    
for (int i = 1;i <= n;++ i)
        
for (int j = 1;j <= n;++ j)
            f[ i ][ j ] 
= false;
}


void solve (int n){
    
int i;
    L.push_back(
1);
    
for (i = 2;i <= n;++ i){
        it 
= L.begin ();

        
if (f[ i ][ *it ]){
            L.push_front(i);
            
continue;
        }


        it 
= L.end();
        
-- it;

        
if (f[ *it ][ i ]){
            L.push_back(i);
            
continue;
        }


        it 
= pre = L.begin();
        
++ it;
        
while (it != L.end()){
            
if (f[ *pre ][ i ] && f[ i ][ *it ]){
                L.insert(it , i);
                
break;
            }

            pre 
++;
            it 
++;
        }

    }

}


int main(){
    
int t , n , i , k , g;
    
int a , b;
    scanf (
"%d" , &t);
    
while (t --){
        L.clear();
        scanf (
"%d" , &n);
        k 
= n * (n - 1/ 2;
        init (n);
        flag 
= true;
        
for (i = 1;i <= k;++ i){
            scanf (
"%d %d" , &a , &b);
            f[ a ][ b ] 
= true;
        }

        solve (n);

        
if (L.size() != n){
            puts (
"Impossible");
            
continue;
        }


        
for (it = L.begin(); it != L.end();++ it){
            
if (it != L.begin()) printf (" ");
            printf (
"%d" , * it);
        }

        printf (
"\n");
    }

    
return 0;
}

posted on 2010-04-21 17:25 此最相思 阅读(269) 评论(2)  编辑 收藏 引用

评论

# re: 竞赛图 2011-03-27 10:45 速度

按找这个题目的数据,它的任意两个点有且仅有一条有向边,那么最后的答案是一定存在这样的路的。不可能是impossible的。所以impossible不用判断了吧?  回复  更多评论   

# re: 竞赛图 2011-08-28 16:18 此最相思

怎么感觉理论就有问题,太坑爹了  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理