The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

Topcoder SRM 452 ,DIV 2 1000 HamiltonPath

Problem Statement

     There are N cities in a country, numbered 0 to N-1. Each pair of cities is connected by a bidirectional road.
John plans to travel through the country using the following rules:
  • He must start in one city and end in another city after travelling exactly N-1 roads.
  • He must visit each city exactly once.
  • You are given a String[] roads. If the j-th character of the i-th element of roads is 'Y', he must travel the road that connects city i and city j.
For example, if there are three cities, and he wants to travel the road between city 0 and city 1, there are 4 possible paths: 0->1->2, 1->0->2, 2->0->1, 2->1->0. Paths 0->2->1 and 1->2->0 are not allowed because they do not allow him to travel the road between city 0 and city 1.
Return the number of paths he can choose, modulo 1,000,000,007.

Definition

    
Class: HamiltonPath
Method: countPaths
Parameters: String[]
Returns: int
Method signature: int countPaths(String[] roads)
(be sure your method is public)
    

Constraints

- roads will contain between 2 and 50 elements, inclusive.
- Each element of roads will contain n characters, where n is the number of elements in roads.
- Each character in roads will be 'Y' or 'N'.
- The i-th character in the i-th element of roads will be 'N'.
- The j-th character in the i-th element of roads and the i-th character in the j-th element of roads will be equal.

Examples

0)
    
                                    {"NYN",
                                    "YNN",
                                    "NNN"}
Returns: 4
The example from the problem statement.
1)
    
                                    {"NYYY",
                                    "YNNN",
                                    "YNNN",
                                    "YNNN"}
Returns: 0
It's impossible to travel all these roads while obeying the other rules.
2)
    
                                    {"NYY",
                                    "YNY",
                                    "YYN"}
Returns: 0
This is also impossible.
3)
    
                                    {"NNNNNY",
                                    "NNNNYN",
                                    "NNNNYN",
                                    "NNNNNN",
                                    "NYYNNN",
                                    "YNNNNN"}
Returns: 24

 





求哈密顿通路的数目,题目中指定了一些道路必须经过。
1。做法是求连通分支,缩点,并判断有没有出现环或者非正常情况,若出现直接返回0。
2。求连通分支数的全排列;
3。遍历所有连通分支
4。如果该连通分支拥有的点数>=2,则结果乘以2,即可得到答案.
求的时候要注意mod操作,要用long long 保存中间数据,(a*b)mod c中 a*b可能溢出32位整数。

#include<iostream>
#include
<cmath>
#include
<cstdio>
#include
<cstring>
#include
<vector>
#include
<string>
using namespace std;

int graph[51][51];
int n;
int v[51];
int ID[51];
int num[51];
int gcc=0;
int flag=0;
void dfs(int f,int k)
{
    
if(flag==1)
        
return;
    ID[k]
=gcc;
    num[gcc]
++;
    
int i;
    
for(i=1;i<=n;i++)
    
{
        
if(graph[k][i]&&(v[i]==1)&&(i!=f))
        
{
            flag
=1;
            
return;
        }

        
if(graph[k][i]&&(v[i]==0))
        
{

            v[i]
=1;
            dfs(k,i);
        }



    }

}



class HamiltonPath
{
    
int i,j;
public:
    
int countPaths(vector <string> roads)
    
{
        n
=roads[0].length();
        
for(i=0;i<n;i++)
        
{

            
for(j=0;j<=n;j++)
            
{

                
if(roads[i][j]=='Y')
                    graph[i
+1][j+1]=1;
            }

        }

        
for(i=1;i<=n;i++)
        
{
            
if(!v[i])
            
{
                v[i]
=1;
                gcc
++;
                dfs(
-1,i);
            }

        }

        
if(flag==1)
            
return 0;
        
int cnt=0;
        
for(i=1;i<=n;i++)
        
{
            cnt
=0;
            
for(j=1;j<=n;j++)
            
{

                
if(graph[i][j]==1)
                    cnt
++;
            }

            
if(cnt>2)
                
return 0;
        }

        
long long res=1;
        
for(i=1;i<=gcc;i++)
        
{

            res
*=i;
            res
%=1000000007;
            
if(num[i]>=2)
            
{
                res
*=2;
                res
%=1000000007;
            }


        }

        
return  res;
    }

}
;
第一次写tc,写的不好还请大家多多指点 :-)

posted on 2009-11-06 14:35 abilitytao 阅读(1208) 评论(1)  编辑 收藏 引用

评论

# re: Topcoder SRM 452 ,DIV 2 1000 HamiltonPath 2009-11-08 14:46 expter

good...
可以用公式过滤一些。。  回复  更多评论   


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