AK 2011-08-18 19:26 发表评论

AK 2011-08-17 09:55 发表评论

AK 2011-08-16 17:10 发表评论

AK 2011-08-16 16:40 发表评论

 1 #include<stdio.h>   
 2 #include<string.h>   
 3 #include<math.h>   
 4 #define N 30   
 5 /*
 6 欧拉回路，所有点连通，并且所有点的入度等于出度。 
 7 欧拉通路。从原点 S出发，经过所有点，从终点 t出去。 
 8 所有点除起点终点外的度都是偶数，且出度等于入度
 9 起点的出度比入度大 1 
10 终点的入度比出度大 1 
11 */ 
12 
13 int father[N],vis[N];  
14 //father[i] 表示节点 i 的 BOSS ！ vis[i]表示节点 i 出现过！ 
15 int findx(int x)  
16 {  //找节点  x 的 BOSS ！ 
17     if(father[x]!=x)  
18         father[x]=findx(father[x]);  
19     return father[x];  
20 }  
21 void merge(int a,int b)  
22 {  // 合并 节点 a 和节点 b ！ 
23     int x,y;  
24     x=findx(a);  
25     y=findx(b);  
26     if(x!=y) father[x]=y;  
27 }  
28 int main()  
29 {  
30     int text,cnt,i,j,n,out[N],in[N],p[30],a,b;  
31     char str[1001];  
32     scanf("%d",&text);  
33     while(text--)  
34     {  
35         scanf("%d",&n);  
36         memset(out,0,sizeof(out));  
37         memset(in,0,sizeof(in));  
38         memset(vis,0,sizeof(vis));  
39         for(i=0;i<26;i++)  
40             father[i]=i;  //初始化数组 
41         while(n--)  
42         {  // 处理所给信息 ！ 
43             scanf("%s",str);  
44             a=str[0]-'a';  
45             b=str[strlen(str)-1]-'a';  
46             merge(a,b);  
47             out[a]++;  
48             in[b]++;  // 记录节点 a 和 b的入度和出度 
49             vis[a]=1;  
50             vis[b]=1; //标记节点 a 和 b的出现 
51         }  
52         for(i=0;i<26;i++)  
53             father[i]=findx(i);  //找出每个节点的 BOSS  
54         for(cnt=0,i=0;i<26;i++)  
55             if(vis[i] && father[i]==i)  
56                 cnt++;  // 统计最终 BOSS 即根节点的个数 。 
57         if(cnt>1)  //图不连通   
58         {  
59             printf("The door cannot be opened.\n");  
60             continue;  
61         }  
62           
63         for(j=0,i=0;i<26;i++)  
64             if(vis[i] && out[i]!=in[i])  
65                 p[j++]=i;  //统计入度和出度不相等的点的信息 
66         if(j==0)   
67         {//欧拉回路，即环   
68             printf("Ordering is possible.\n");  
69             continue;  
70         }  
71         if(j==2 && ( out[p[0]]-in[p[0]]==1 && in[p[1]]-out[p[1]]==1  
72             || out[p[1]]-in[p[1]]==1 && in[p[0]]-out[p[0]]==1 ) )  
73         {//欧拉通路   
74             printf("Ordering is possible.\n");  
75             continue;  
76         }  
77         printf("The door cannot be opened.\n");  
78     }  
79     return 0;  
80 }  
81 

AK 2011-07-18 10:57 发表评论

AK 2011-07-18 09:31 发表评论

AK 2011-07-18 09:20 发表评论

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 int father[1001], tot;//father[i] 记录 i 的 BOSS ！  
 5 //tot 统计最初至少需要添加的路径数目 ！ 
 6 
 7 int find(int x)
 8 {//找 到  x 的 BOSS ！ 
 9     int r = x;
10     while (r != father[r]) r = father[r];
11     return r;// 
12 }
13 
14 void join(int a, int b)
15 {//将 a 和  b 的 BOSS 统一！ 
16      int fa = find(a), fb = find(b);
17      if (fa != fb)
18      {
19         father[fa] = fb;
20         tot --; // 统一了一次两个阵营的  BOSS ，所以需要添加的路径的数目减一！ 
21      }
22 }
23 
24 int main()
25 {
26     int n, m, x, y;
27     while (scanf("%d", &n), n)
28     {
29           scanf("%d", &m);
30           tot = n-1; // 初始化 tot 等于 n 个点联通所需要的最少边的数目 ！ 
31           father[n+1];
32           for (int i=1; i<=n; i++)father[i] = i;//初始化自己是自己的 BOSS ！ 
33           
34           for (int i=1; i<=m; i++)
35           {
36               scanf("%d %d",&x, &y);
37               join(x, y);  
38           }
39           printf("%d\n",tot); //输出在已有基础上还需要的边的数目！ 
40     }
41     return 0;
42 }
43 

AK 2011-07-18 08:59 发表评论

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<math.h>
 4 #include<string.h>
 5 const double MAX = 1000000000.0; 
 6 struct Point
 7 {
 8        double x, y;
 9 }point[101];
10 
11 double map[101][101];
12 int v[101], n;
13 
14 double Dis(Point a, Point b)
15 {
16        return sqrt((a.x - b.x) * (a.x - b.x) +(a.y - b.y) * (a.y - b.y)); 
17 } 
18 
19 void Build()
20 {
21      memset(map, 0, sizeof(map));
22      for (int i=0; i<n; i++)
23      {
24          for (int j=i; j<n; j++)
25          {
26              if (i == j) map[i][j] = MAX;
27              else 
28              {
29                    map[j][i] = map[i][j] = Dis(point[i], point[j]);
30              }
31          }
32      }
33 }
34 
35 void MinTree()
36 {
37      double sum = 0.0, min;
38      memset(v, 0, sizeof(v));
39      v[0] = 1;
40      int flag;
41      for (int i=1; i<n; i++)
42      {
43          min = MAX;
44          for (int j=0; j<n; j++)
45          {
46              if (!v[j] && map[0][j] < min)
47              {
48                 min = map[0][j];
49                 flag = j;
50              }
51          }
52          sum += min;
53          v[flag] = 1;
54          for (int j=0; j<n; j++)
55          {
56              if (!v[j] && map[0][j] > map[flag][j])
57              {
58                 map[0][j] = map[flag][j];
59              }
60          }
61      }
62      printf("%.2lf\n",sum);
63 }
64 int main()
65 {
66     while (scanf("%d", &n)!= EOF)
67     {
68           map[n][n];
69           point[n];
70           for (int i=0; i<n; i++)
71           {
72               scanf("%lf %lf", &point[i].x, &point[i].y);
73           }
74           Build();
75           MinTree();
76     }
77     return 0;
78 }
79 

AK 2011-07-18 08:42 发表评论

AK 2011-07-18 08:34 发表评论