一题简单数学 + CodeForces 24A 一题简单dfs

//CodeChef RRMATRIX
//分析：(x-1)*m+y == (y-1)*n+x ==> (x-1)*(m-1) == (y-1)*(n-1) ==> (x-1) == (y-1)*(n-1)/(m-1);(n-1)/(m-1)约分后分母还剩余一个(m-1)/gcd(n-1,m-1),(y-1)是(m-1)/gcd(n-1,m-1)倍数的情况共有(m-1)/((m-1)/gcd(n-1,m-1))+1种，即gcd(n-1,m-1)+1

 1 #include"iostream"
 2 #include"cstdio"
 3 using namespace std;
 4 int main()
 5 {
 6     int T,n,m,temp;
 7     scanf("%d",&T);
 8     while(T--) {
 9         scanf("%d%d",&n,&m);
10         if(n==1) {  //n==1 || m==1为两种特殊情况，需特判
11             printf("%d
",m);
12             continue;
13         }
14         if(m==1) {
15             printf("%d
",n);
16             continue;
17         }
18         --n;
19         --m;
20         while(m) {
21             temp = n%m;
22             n = m;
23             m = temp;
24         }
25         printf("%d
",n+1);
26     }
27     return 0;
28 }

//CodeForces 24A
//分析：对整个“有向环”做一趟dfs染色即可
//因为是入栈后标记，所以访问过的点一定会被标记，由于需要回到起点，所以记录下最后一次访问过的点last_point；相对应的，入栈前标记的话，首次访问的点不会被标记，用这种方法写本题的话，由于 1 点未被标记，所以可能会在一个不希望的时机去第二次访问 1 点，就需要删除一条从 1 点出发的出边，和另一条回到 1 点的回边，而且对于只有两个点的图还需要特判，比较麻烦

 1 #include"iostream"
 2 #include"cstdio"
 3 #include"cstring"
 4 using namespace std;
 5 const int maxn = 110;
 6 int tot,first[maxn<<1],next[maxn<<1],destination[maxn<<1],weight[maxn<<1];
 7 int n,res,last_point;
 8 bool vis[maxn];
 9 void dfs(int point)
10 {
11     vis[point] = 1;
12     last_point = point;
13     int edge = first[point];
14     while(edge) {
15         if(!vis[destination[edge]]) {
16             res += weight[edge];
17             dfs(destination[edge]);
18         }
19         edge = next[edge];
20     }
21 }
22 
23 
24 int main()
25 {
26     int i,u,v,w,sum = 0;
27     res = tot = 0;
28     scanf("%d",&n);
29     for(i = 1; i<=n; i++) {
30         scanf("%d%d%d",&u,&v,&w);
31         next[++tot] = first[u];
32         first[u] = tot;
33         destination[tot] = v;
34         weight[tot] = 0;
35         next[++tot] = first[v];
36         first[v] = tot;
37         destination[tot] = u;
38         weight[tot] = w;
39         sum += w;
40     }
41     dfs(1);
42     int edge = first[last_point];
43     while(destination[edge]!=1) {
44         edge = next[edge];
45     }
46     res += weight[edge];
47     printf("%d
",res<sum-res?res:sum-res);
48     return 0;
49 }

 1 #include"iostream"
 2 #include"cstdio"
 3 #include"cstring"
 4 using namespace std;
 5 const int maxn = 110;
 6 int tot,first[maxn<<1],next[maxn<<1],destination[maxn<<1],weight[maxn<<1];
 7 int n,res,last_point;
 8 bool vis[maxn];
 9 int dfs(int point)
10 {
11     vis[point] = 1;
12     last_point = point;
13     int edge = first[point];
14     while(edge) {
15         if(!vis[destination[edge]]) {
16             return weight[edge]+dfs(destination[edge]);
17         }
18         edge = next[edge];
19     }
20     return 0;　　//注意返回0
21 }
22 
23 
24 int main()
25 {
26     int i,u,v,w,sum = 0;
27     tot = 0;
28     scanf("%d",&n);
29     for(i = 1; i<=n; i++) {
30         scanf("%d%d%d",&u,&v,&w);
31         next[++tot] = first[u];
32         first[u] = tot;
33         destination[tot] = v;
34         weight[tot] = 0;
35         next[++tot] = first[v];
36         first[v] = tot;
37         destination[tot] = u;
38         weight[tot] = w;
39         sum += w;
40     }
41     res = dfs(1);
42     int edge = first[last_point];
43     while(destination[edge]!=1) {
44         edge = next[edge];
45     }
46     res += weight[edge];
47     printf("%d
",res<sum-res?res:sum-res);
48     return 0;
49 }