涓鏈功鐨勯〉鏁頒負N錛岄〉鐮佷粠1寮濮嬬紪璧鳳紝璇蜂綘姹傚嚭鍏ㄩ儴欏電爜涓紝鐢ㄤ簡澶氬皯涓?錛?錛?錛屸︼紝9銆傚叾涓斾釜欏電爜涓嶅惈澶氫綑鐨?錛屽N錛?234鏃剁5欏典笉鏄?005錛屽彧鏄?銆?
銆愯緭鍏ャ?
涓涓鏁存暟N(N鈮?09)錛岃〃紺烘葷殑欏電爜銆?
銆愯緭鍑恒?
鍏卞崄琛岋細絎琸琛屼負鏁板瓧k-1鐨勪釜鏁般?
銆愭牱渚嬨?
count.in count.out
11 1
4
1
1
闃呰鍏ㄦ枃
]]>
璁╀綘鍒ゆ柇鏄惁瀛樺湪緇忚繃鑻ュ共嬈¤揣甯佺殑鍏戞崲浣垮緱鏌愮璐у竵鐨?
浠峰煎ぇ浜庡師鏉ユ湰韜殑浠峰鹼紝姣斿鎵錛氱編鍏冿細緹庡厓 = 1 錛?1錛?
棰樻剰灝辨槸璁╀綘鍒ゆ柇錛屽湪褰撳墠鐨勮揣甯佸厬鎹㈢巼鐨勫熀紜涓婏紝鑳戒笉鑳?
浣?緹庡厓 錛?緹庡厓 > 1 : 1; 鍒╃敤Floyd綆楁硶鍗沖彲鎼炲畾錛屼唬鐮佸涓嬶細 闃呰鍏ㄦ枃
]]>
]]>
榪欎釜棰樼洰瑕佽繍鐢ㄥ埌嬈ф媺璺緱鐩稿叧鐭ヨ瘑錛屽茍涓斾篃瑕佸茍鏌ラ泦錛岄鐩鐨勬槸錛氱粰浣爊涓崟璇嶏紝瑕佷綘鍒ゆ柇榪欎簺鍗曡瘝鑳戒笉鑳介灝劇浉榪炪?br />鐞嗚В棰樼洰鎰忔濆悗錛岃繘琛岃漿鍖栵紝杈撳叆瀛楃涓詫紝鎻愬彇棣栦綅瀛楁瘝浣滀負涓嬫爣鏉ヨ〃紺轟袱鑺傜偣鐨勫嚭鐜幫紝浠ュ強鐩稿搴旇妭鐐瑰叆搴﹀拰鍑哄害鐨勫鍔狅紝
杞寲涓哄茍鏌ラ泦鐨勫簲鐢ㄥ嵆鍙傞偅涔堜粠鍙互鎯寵薄涓騫呯敱棣栦綅瀛楁瘝鑺傜偣鏋勬垚鐨勫浘錛屽綋涓斾粎褰撳浘鏄竴鏉℃鎷夊洖璺垨鑰呮鎷夐氳礬鐨勬椂鍊欙紝
鎵嶈兘婊¤凍棰樼洰鐨勮姹傦紝鑷充簬嬈ф媺鍥炶礬鍜屾鎷夐氳礬鐨勫垽瀹氬彲浠ユ葷粨涓哄涓嬶細
1錛夋墍鏈夌殑鐐硅仈閫?br />2錛夋鎷夊洖璺腑鎵鏈夌偣鐨勫叆搴﹀拰鍑哄害涓鏍楓?br />3錛夋鎷夐氳礬涓搗鐐圭殑鍏ュ害 - 鍑哄害 = 1錛岀粓鐐圭殑 鍒濆害 - 鍏ュ害 = 1錛?鍏朵粬鐨勬墍鏈夌偣鍏ュ害 = 鍑哄害錛?br />
鏈変簡涓婇潰榪欎簺鐭ヨ瘑鐐瑰仛閾哄灚錛岀浉淇＄悊瑙ｈ搗鏉ュ氨姣旇緝瀹規槗浜嗭紝涓嬮潰鎴戠殑浠ｇ爜錛?
1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 #define N 30
5 /*
6 嬈ф媺鍥炶礬錛屾墍鏈夌偣榪為氾紝騫朵笖鎵鏈夌偣鐨勫叆搴︾瓑浜庡嚭搴︺?nbsp;
7 嬈ф媺閫氳礬銆備粠鍘熺偣 S鍑哄彂錛岀粡榪囨墍鏈夌偣錛屼粠緇堢偣 t鍑哄幓銆?nbsp;
8 鎵鏈夌偣闄よ搗鐐圭粓鐐瑰鐨勫害閮芥槸鍋舵暟錛屼笖鍑哄害絳変簬鍏ュ害
9 璧風偣鐨勫嚭搴︽瘮鍏ュ害澶?nbsp;1
10 緇堢偣鐨勫叆搴︽瘮鍑哄害澶?nbsp;1
11 */
12
13 int father[N],vis[N];
14 //father[i] 琛ㄧず鑺傜偣 i 鐨?nbsp;BOSS 錛?nbsp;vis[i]琛ㄧず鑺傜偣 i 鍑虹幇榪囷紒
15 int findx(int x)
16 { //鎵捐妭鐐?nbsp; x 鐨?nbsp;BOSS 錛?nbsp;
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 鍜岃妭鐐?nbsp;b 錛?nbsp;
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; //鍒濆鍖栨暟緇?nbsp;
41 while(n--)
42 { // 澶勭悊鎵緇欎俊鎭?nbsp;錛?nbsp;
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 鍜?nbsp;b鐨勫叆搴﹀拰鍑哄害
49 vis[a]=1;
50 vis[b]=1; //鏍囪鑺傜偣 a 鍜?nbsp;b鐨勫嚭鐜?nbsp;
51 }
52 for(i=0;i<26;i++)
53 father[i]=findx(i); //鎵懼嚭姣忎釜鑺傜偣鐨?nbsp;BOSS
54 for(cnt=0,i=0;i<26;i++)
55 if(vis[i] && father[i]==i)
56 cnt++; // 緇熻鏈緇?nbsp;BOSS 鍗蟲牴鑺傜偣鐨勪釜鏁?nbsp;銆?nbsp;
57 if(cnt>1) //鍥句笉榪為?nbsp;
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; //緇熻鍏ュ害鍜屽嚭搴︿笉鐩哥瓑鐨勭偣鐨勪俊鎭?nbsp;
66 if(j==0)
67 {//嬈ф媺鍥炶礬錛屽嵆鐜?nbsp;
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
2 #include<string.h>
3 #include<math.h>
4 #define N 30
5 /*
6 嬈ф媺鍥炶礬錛屾墍鏈夌偣榪為氾紝騫朵笖鎵鏈夌偣鐨勫叆搴︾瓑浜庡嚭搴︺?nbsp;
7 嬈ф媺閫氳礬銆備粠鍘熺偣 S鍑哄彂錛岀粡榪囨墍鏈夌偣錛屼粠緇堢偣 t鍑哄幓銆?nbsp;
8 鎵鏈夌偣闄よ搗鐐圭粓鐐瑰鐨勫害閮芥槸鍋舵暟錛屼笖鍑哄害絳変簬鍏ュ害
9 璧風偣鐨勫嚭搴︽瘮鍏ュ害澶?nbsp;1
10 緇堢偣鐨勫叆搴︽瘮鍑哄害澶?nbsp;1
11 */
12
13 int father[N],vis[N];
14 //father[i] 琛ㄧず鑺傜偣 i 鐨?nbsp;BOSS 錛?nbsp;vis[i]琛ㄧず鑺傜偣 i 鍑虹幇榪囷紒
15 int findx(int x)
16 { //鎵捐妭鐐?nbsp; x 鐨?nbsp;BOSS 錛?nbsp;
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 鍜岃妭鐐?nbsp;b 錛?nbsp;
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; //鍒濆鍖栨暟緇?nbsp;
41 while(n--)
42 { // 澶勭悊鎵緇欎俊鎭?nbsp;錛?nbsp;
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 鍜?nbsp;b鐨勫叆搴﹀拰鍑哄害
49 vis[a]=1;
50 vis[b]=1; //鏍囪鑺傜偣 a 鍜?nbsp;b鐨勫嚭鐜?nbsp;
51 }
52 for(i=0;i<26;i++)
53 father[i]=findx(i); //鎵懼嚭姣忎釜鑺傜偣鐨?nbsp;BOSS
54 for(cnt=0,i=0;i<26;i++)
55 if(vis[i] && father[i]==i)
56 cnt++; // 緇熻鏈緇?nbsp;BOSS 鍗蟲牴鑺傜偣鐨勪釜鏁?nbsp;銆?nbsp;
57 if(cnt>1) //鍥句笉榪為?nbsp;
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; //緇熻鍏ュ害鍜屽嚭搴︿笉鐩哥瓑鐨勭偣鐨勪俊鎭?nbsp;
66 if(j==0)
67 {//嬈ф媺鍥炶礬錛屽嵆鐜?nbsp;
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
]]>
鍦ㄧ粰鍑虹殑map鐨勫熀紜涓婏紝瑕佹眰閫夋嫨閫傚綋鐨勮礬綰匡紝浣垮緱鎵鏈夌粰鍑虹殑鐐歸兘鑳藉鍒拌揪浠繪剰鍏朵粬鐐癸紝闂瑙勬ā涓嶅ぇ錛岀洿鎺ョ煩闃?
瀛樺偍錛屽埄鐢╬rim 綆楁硶鎼炲畾銆?nbsp; 闃呰鍏ㄦ枃
]]>
榪欎釜棰樼洰涔熸槸鍏稿瀷鐨勬渶灝忕敓鎴愭爲綆楁硶錛岃窡涔嬪墠鐨勯偅涓鐩?/a>鏄樊涓嶅鐨勶紝涔熷氨鏄錛氱粰浣爊涓簩緇村鉤闈㈢偣錛?br />璁╀綘娣誨姞閫傚綋鐨勮竟錛屼嬌寰楁墍鏈夌殑鐐歸兘鍦ㄥ悓涓涓仈閫氬垎鏀笂錛屼篃灝辨槸璇翠換浣曠偣涔嬮棿閮芥湁璺緞鍙互鍒拌揪銆?br />闂瑙勬ā涓嶅ぇ錛岀洿鎺ョ敤鐭╅樀瀛樻暟鎹紝鍒╃敤prim 綆楁硶灝卞彲浠ユ悶瀹氥傛鏃朵換鎰忎袱鐐逛箣闂寸殑“鏉冨?#8221;灝辨槸
涓ょ偣涔嬮棿鐨勮窛紱匯?
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
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
]]>
榪欎釜棰樼洰鐨勬剰鎬濆氨鏄錛岀粰浣犱竴涓湁n涓潙搴勭殑鍦板浘錛宮ap[i][j]琛ㄧず浠庢潙搴?i 鍒版潙搴?j 鐨勮窛紱伙紝鐒跺悗緇欎綘
m 鏉″凡鏈夐亾璺紝璁╀綘鍦ㄨ繖涓熀紜涓婃坊鍔犻傚綋鐨勯亾璺紝浣垮緱鎵鏈夋潙搴勪箣闂撮兘鏄仈閫氱殑錛屾眰娣誨姞閬撹礬鐨勬渶鐭窛
紱葷殑鍊箋? 闃呰鍏ㄦ枃
]]>