Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Re:Dfs水题……

Posted by whybert at 2012-11-16 00:11:42 on Problem 2132
In Reply To:Re:Dfs水题…… Posted by:whybert at 2012-11-16 00:11:25
```#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 30;
#define LL long long
int n,a[N][N];
LL ans;
bool vis[N];
LL gcd(LL a,LL b) {
return a?gcd(b%a,a):b;
}
LL lcm(LL a,LL b) {
return a*b/(gcd(a,b));
}
void dfs(int k,LL v) {
if (~ans && ~v && ans%v==0) return;
if (k==2) {
ans = lcm(ans,v);
return;
}
for (int i=1;i<=n;i++) {
if (!vis[i] && a[k][i]) {
vis[i] = 1;
dfs(i,~v?gcd(v,a[k][i]):a[k][i]);
vis[i] = 0;
}
}
}
int main() {
while (~scanf("%d",&n)) {
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
scanf("%d",&a[i][j]);
}
}
ans = -1;
memset(vis,0,sizeof vis);
vis[1] = 1;
dfs(1,-1);
cout<<ans<<endl;
}
return 0;
}
```

Followed by: