记录编号	124304	评测结果	AAAAAAAAAA
题目名称	考验	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2014-10-03 08:08:45	内存使用	0.28 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <iterator>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x7ffffff;
//==============struct declaration==============
struct adj{
  int to;
  LL dist;
  adj(int to=0,LL dist=0):to(to),dist(dist){}
};
//==============var declaration=================
const int MAXN=30;
int n;
vector <adj> Edge[MAXN];
LL res=1;
bool vis[MAXN];
//==============function declaration============
inline LL gcd(LL a,LL b){if(a<b) swap(a,b);return a%b==0?b:gcd(b,a%b);}
inline LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
void search(int x,LL GCD);
//==============main code=======================
int main()
{  
  string FileName="testz";//程序名 
  string FloderName="COGS";//文件夹名 
  freopen((FileName+".in").c_str(),"r",stdin);
  freopen((FileName+".out").c_str(),"w",stdout);
  ios::sync_with_stdio(false);
  cin>>n;
  For(i,1,n)
    For(j,1,n){
      LL w;
      cin>>w;
      if (w)
        Edge[i].push_back(adj(j,w)); 
    }
  memset(vis,false,sizeof(vis));
  vis[1]=true;
  search(1,0);
  cout<<res<<endl;  
  return 0;
}
//================fuction code====================
void search(int x,LL GCD)
{
  if (x==2||(GCD!=0&&res%GCD==0)){
    res=lcm(res,GCD);
    return ;
  }
  int siz=Edge[x].size()-1;
  For(i,0,siz){
   adj &e=Edge[x][i];
   if (vis[e.to]||e.dist==1) continue;
   vis[e.to]=true;
   if (GCD)
     search(e.to,gcd(GCD,e.dist));
   else 
     search(e.to,e.dist);
   vis[e.to]=false; 
  }
  return ;
}