|
|
并查集或者DFS的題，大概是說有N個學生去訂房間，只有朋友可以住一個房間。朋友關系具有傳遞性，如果A和B是朋友,B和C是朋友，那么A和C是朋友。問最后最少定多少個房間。 我用并查集做，卻在最后犯了一個很不容易發覺的錯誤，最后還是找一個學姐才發現。看來以后一定得小心啊，太大意會很可怕的~ Code：
1 #include<stdio.h>
2 #include<string.h>
3 struct student
4 {
5 int father,rank;
6 }a[250];
7 bool flag[250];
8 void initial(int n)
9 {
10 int i;
11 for(i=1;i<=n;i++){
12 a[i].father=i;
13 a[i].rank=1;
14 }
15 }
16 int find(int n)
17 {
18 while(a[n].father!=n)
19 n=a[n].father;
20 return n;
21 }
22 void Union(int root1,int root2)
23 {
24 int t1,t2;
25 t1=find(root1);
26 t2=find(root2);
27 if(t1==t2) return ;
28 else{
29 if(a[t1].rank>a[t2].rank){
30 a[t2].father=t1;
31 a[t1].rank+=a[t2].rank;
32 }
33 else{
34 a[t1].father=t2;
35 a[t2].rank+=a[t1].rank;
36 }
37 }
38 }
39 int main()
40 {
41 int i,j,k,m,n,cas;
42 scanf("%d",&cas);
43 while(cas--){
44 scanf("%d%d",&n,&m);
45 initial(n);
46 for(i=1;i<=m;i++){
47 scanf("%d%d",&j,&k);
48 Union(j,k);
49 }
50 memset(flag,false,sizeof(flag));
51 k=0;
52 for(i=1;i<=n;i++){
53 if(!flag[find(i)]){
54 k++;
55 flag[find(i)]=true;
56 }
57 }
58 printf("%d\n",k);
59 }
60 }
61
兩個算法具有相當大的相似性，而且都用到了貪心思想，所以把他們放到一起。最短路常用的算法有dijkstra，bellman-ford，floyd。而最小生成樹則是prim和kruskal。下面是各個算法的模板。
Dijkstra:
1 #include<stdio.h>
2 #include<string.h>
3 #define INF 0x1f1f1f1f
4 #define M 1001
5 int map[M][M],dis[M];
6 bool flag[M];
7 void dijkstra(int s,int n,int t) //s是源點，n是點的個數，t是目的點
8 {
9 int i,j,k,md,temp;
10 for(i=1;i<=n;i++)
11 dis[i]=INF; //初始化將所有dis置為無窮大，源點為0
12 dis[s]=0;
13 memset(flag,false,sizeof(flag)); //開始flag全部為false，表示集合為空
14 for(i=1;i<n;i++){ //進行n-1次迭代，每次找出不在集合中的最小邊
15 md=INF;
16 for(j=1;j<=n;j++){
17 if(!flag[j]&&dis[j]<md){
18 md=dis[j];
19 temp=j;
20 }
21 }
22 if(temp==t) break; //如果遇到目的點，可以跳出了
23 flag[temp]=true; //將這個最小邊的點加入集合
24 for(j=1;j<=n;j++){
25 if(!flag[j]&&md+map[temp][j]<dis[j]) //對所有出邊進行松弛操作
26 dis[j]=md+map[temp][j];
27 }
28 }
29 }
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 相應的最小生成樹的prim模板：
1 #include<iostream>
2 #define INF 0x1f1f1f1f
3 #define M 1000
4 using namespace std;
5 double dis[M],map[M][M];
6 bool flag[M];
7 int prim(int s,int n) //s為起點，n為點的個數
8 {
9 int i,j,k,temp,md,total=0;
10 for(i=1;i<=n;i++)
11 dis[i]=map[s][i]; //與最短路不同，而是將dis置為map[s][i]
12 memset(flag,false,sizeof(flag));
13 flag[s]=true; //將起點加入集合
14 for(i=1;i<n;i++){ //依舊進行n-1次迭代，每次找到不在集合的最小邊
15 md=INF;
16 for(j=1;j<=n;j++){
17 if(!flag[j]&&dis[j]<md){
18 md=dis[j];
19 temp=j;
20 }
21 }
22 flag[temp]=true; //將找到的最小邊的點加入集合
23 total+=md; //并將這個邊的權值加到total中
24 for(j=1;j<=n;j++) //松弛操作，注意與最短路不同
25 if(!flag[j]&&dis[j]>map[temp][j])
26 dis[j]=map[temp][j];
27 }
28 return total;
29 }
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 下面是最短路的bellmen-ford算法，與dijkstra不同，bellman-ford可以運用于有負權值的圖，不過復雜度很高，O(VE )... 慎用~（可以用SPFA，但是那個算法我掌握的不是很好：D） Bellman-ford算法同樣是對每條邊進行N-1次松弛，當有權值為負時，對所有邊進行N-1次松弛，如果dis還能更新，說明有負環。 Bellman-ford模板：
1 #include<stdio.h>
2 #include<string.h>
3 #define INF 0x1f1f1f1f
4 #define MAX 102
5 #define MAXM 20008
6
7 int dist[MAX];
8
9 struct Edge{ //邊結構體定義
10 int u, v, w;
11 Edge(){}
12 Edge(int a, int b, int c):u(a), v(b), w(c){}
13 }edge[MAXM];
14
15 int bellman_ford(int n, int m, int s) //n個點、m條邊、s為起點
16 {
17 memset(dist, 0x1f, sizeof(dist)); //初始化距離很大
18 dist[s] = 0;
19 int i, j, u, v, f;
20 for (i = 1; i < n; ++i) //迭代 n - 1 次，對每條邊進行n-1次松弛
21 {
22 f = 0;
23 for (j = 0; j < m; ++j)
24 {
25 u = edge[j].u;
26 v = edge[j].v;
27 if (dist[v] > dist[u] + edge[j].w) // 松弛操作
28 {
29 dist[v] = dist[u] + edge[j].w;
30 f = 1;
31 }
32 }
33 if (!f) return 1; //如果其中一次迭代沒改變，停止
34 }
35 for(j = 0; j < m; ++j) //再進行一次迭代
36 {
37 u = edge[j].u;
38 v = edge[j].v;
39 if (dist[v] > dist[u] + edge[j].w) //若還能松弛, 則存在負環
40 return -1; //存在負環返回 -1
41 }
42 return 1; //沒有負環返回 1
43 }
算法結束后dist數組已經是最短路徑。
先來最基本的線性篩素數，以后的算法其實都是基于這個最基本的算法：
1 #include<stdio.h>
2 #include<string.h>
3 #define M 10000000
4 int prime[M/3];
5 bool flag[M];
6 void get_prime()
7 {
8 int i,j,k;
9 memset(flag,false,sizeof(flag));
10 k=0;
11 for(i=2;i<M;i++){
12 if(!flag[i])
13 prime[k++]=i;
14 for(j=0;j<k&&i*prime[j]<M;j++){
15 flag[i*prime[j]]=true;
16 if(i%prime[j]==0)
17 break;
18 }
19 }
20 }
21 int main()
22 {}
利用了每個合數必有一個最小素因子，每個合數僅被它的最小素因子篩去正好一次，所以是線性時間。
代碼中體現在： if(i%prime[j]==0) break;
-----------------------------------------------------------------------我是低調的分割線------------------------------------------------------------------------------------------
然后可以利用這種線性篩法求歐拉函數，需要用到以下幾個性質：
//(1) 若(N%a==0 && (N/a)%a==0) 則有:E(N)=E(N/a)*a;
//(2) 若(N%a==0 && (N/a)%a!=0) 則有:E(N)=E(N/a)*(a-1);
其中a是N的質因數。
關于歐拉函數還有以下性質：
(1) phi[p]=p-1; (p為素數);
(2)若N=p^n(p為素數)，則 phi[N]=(p-1)*p^(n-1);
關于歐拉函數，Wiki有很詳細的介紹。
1 #include<stdio.h>
2 #include<string.h>
3 #define M 10000000
4 int prime[M/3],phi[M];
5 bool flag[M];
6 void get_prime()
7 {
8 int i,j,k;
9 memset(flag,false,sizeof(flag));
10 k=0;
11 for(i=2;i<M;i++){
12 if(!flag[i]){
13 prime[k++]=i;
14 phi[i]=i-1;
15 }
16 for(j=0;j<k&&i*prime[j]<M;j++){
17 flag[i*prime[j]]=true;
18 if(i%prime[j]==0){
19 phi[i*prime[j]]=phi[i]*prime[j];
20 break;
21 }
22 else
23 phi[i*prime[j]]=phi[i]*(prime[j]-1);
24 }
25 }
26 }
27 int main()
28 {}
-----------------------------------------------------------------------我是低調的分割線----------------------------------------------------------------------------------------- 求約數個數略微復雜一點，但大體還是那個意思。 約數個數的性質，對于一個數N，N=p1^a1 + p2^a2 + ... + pn^an。其中p1 ,p2, p3... pn是N的質因數，a1 ,a2, a2,...an為相應的指數，則 div_num[N]=(p1+1)*(p2+1)*(p3+1)* ... *(pn+1); 結合這個算法的特點，在程序中如下運用： 對于div_num： (1)如果i|prime[j] 那么 div_num[i*prime[j]]=div_sum[i]/(e[i]+1)*(e[i]+2) //最小素因子次數加1 (2)否則 div_num[i*prime[j]]=div_num[i]*div_num[prime[j]] //滿足積性函數條件 對于e： (1)如果i|pr[j] e[i*pr[j]]=e[i]+1; //最小素因子次數加1 (2)否則 e[i*pr[j]]=1; //pr[j]為1次
1 #include<stdio.h>
2 #include<string.h>
3 #define M 10000000
4 int prime[M/3],e[M/3],div_num[M]; // e[i]表示第i個素數因子的個數
5 bool flag[M];
6 void get_prime()
7 {
8 int i,j,k;
9 memset(flag,false,sizeof(flag));
10 k=0;
11 for(i=2;i<M;i++){
12 if(!flag[i]){
13 prime[k++]=i;
14 e[i]=1;
15 div_num[i]=2; //素數的約數個數為2
16 }
17 for(j=0;j<k&&i*prime[j]<M;j++){
18 flag[i*prime[j]]=true;
19 if(i%prime[j]==0){
20 div_num[i*prime[j]]=div_num[i]/(e[i]+1)*(e[i]+2);
21 e[i*prime[j]]=e[i]+1;
22 break;
23 }
24 else{
25 div_num[i*prime[j]]=div_num[i]*div_num[prime[j]];
26 e[i]=1;
27 }
28 }
29 }
30 }
31 int main()
32 {}
33
34
35
希望大家有所收獲~~ Made by M.J
設dis[ ][ ]是圖的鄰接矩陣，其中不存在的邊權值為正無窮大。
for(k = 0; k < n; k++）
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
if(dis[i][j] > dis[i][k] + dis[k][j])
dis[i][j] = dis[i][k] + dis[k][j];
時間復雜度 O(v^3)
1 #include<iostream>
2 #include<map>
3 #include<vector>
4 #include<string>
5 #define M 0
6 double ma[50][50],bi;
7 using namespace std;
8 bool floyd(int n)
9 {
10 int i,j,k,m;
11
12 for(i=1;i<=n;i++)
13 for(j=1;j<=n;j++)
14 for(k=1;k<=n;k++)
15 if(ma[j][k]<ma[j][i]*ma[i][k])
16 ma[j][k]=ma[j][i]*ma[i][k];
17 for(i=1;i<=n;i++)
18 if(ma[i][i]>1)
19 return true;
20 return false;
21 }
22 int main()
23 {
24 map<string,int>fuck;
25 int i,j,k,n,m,p,q,count=1;
26 string cash,cash2;
27 while(cin>>n&&n)
28 {
29 for(i=1;i<=n;i++)
30 {
31 cin>>cash;
32 fuck[cash]=i;
33 }
34 for(i=1;i<=n;i++)
35 for(j=1;j<=n;j++)
36 ma[i][j]=ma[j][i]=M;
37 cin>>m;
38 for(i=1;i<=m;i++)
39 {
40 cin>>cash;
41 p=fuck[cash];
42 cin>>bi;
43 cin>>cash2;
44 q=fuck[cash2];
45 ma[p][q]=bi;
46 }
47 if(floyd(n))
48 cout<<"Case "<<count<<": Yes"<<endl;
49 else
50 cout<<"Case "<<count<<": No"<<endl;
51 count++;
52 }
53 }
54
啥也不說了，sparsetable算法的高效性，我真佩服那個發明它的人。Orz...
以下是關于這個算法的講解（我也沒理解透，回頭細細品味吧）
RMQ(Range Minimum/Maximum Query)問題是求區間最值問題。你當然可以寫個O(n)的（怎么寫都可以吧=_=),但是萬一要詢問最值1000000遍，估計你就要掛了。這時候你可以放心地寫一個線段樹（前提是不寫錯）O（logn)的復雜度應該不會掛。但是，這里有更牛的算法，就是ST算法，它可以做到O(nlogn)的預處理，O(1)！！！地回答每個詢問。
來看一下ST算法是怎么實現的(以最大值為例）：
首先是預處理，用一個DP解決。設a[i]是要求區間最值的數列，f[i, j]表示從第i個數起連續2^j個數中的最大值。例如數列3 2 4 5 6 8 1 2 9 7 ,f[1，0]表示第1個數起，長度為2^0=1的最大值，其實就是3這個數。f[1，2]=5，f[1，3]=8，f[2，0]=2，f[2，1]=4……從這里可以看出f[i,0]其實就等于a[i]。這樣，Dp的狀態、初值都已經有了，剩下的就是狀態轉移方程。我們把f[i，j]平均分成兩段（因為f[i，j]一定是偶數個數字），從i到i+2^(j-1)-1為一段，i+2^(j-1)到i+2^j-1為一段(長度都為2^（j-1）)。用上例說明，當i=1，j=3時就是3,2,4,5 和 6,8,1,2這兩段。f[i，j]就是這兩段的最大值中的最大值。于是我們得到了動規方程F[i, j]=max（F[i，j-1], F[i + 2^(j-1)，j-1]）.
接下來是得出最值，也許你想不到計算出f[i，j]有什么用處，一般毛想想計算max還是要O(logn)，甚至O(n)。但有一個很好的辦法，做到了O（1）。還是分開來。如在上例中我們要求區間[2，8]的最大值，就要把它分成[2,5]和[5,8]兩個區間，因為這兩個區間的最大值我們可以直接由f[2，2]和f[5，2]得到。擴展到一般情況，就是把區間[L，R]分成兩個長度為2^n的區間（保證有f[i，j]對應）。直接給出表達式：
k := ln(R-L+1) / ln(2);
ans := max(F[L，k], F[R - 2^k+1, k]);
這樣就計算了從i開始，長度為2^t次的區間和從r-2^i+1開始長度為2^t的區間的最大值（表達式比較煩瑣，細節問題如加1減1需要仔細考慮.
Code：
1 #include<iostream>
2 #include<cmath>
3 #define M 100005
4 int rmq1[M][30];
5 int rmq2[M][30];
6 int a[M];
7 int N,Q,R,L;
8 using namespace std;
9 int max(int a,int b)
10 {
11 if(a>b) return a;
12 else return b;
13 }
14 int min(int a,int b)
15 {
16 if(a<b) return a;
17 else return b;
18 }
19 void DP(int N)
20 {
21 int i,j,k;
22 for(i=1;i<=int(log(double(N))/log(2.0));i++)
23 for(j=1;j<=N;j++)
24 {
25 rmq1[j][i]=max(rmq1[j][i-1],rmq1[j+int(pow(2.0,i-1))][i-1]);
26 rmq2[j][i]=min(rmq2[j][i-1],rmq2[j+int(pow(2.0,i-1))][i-1]);
27 }
28 }
29 int search(int i,int j)
30 {
31 int k=(int)(log((double)(j-i+1))/log(2.0));
32 return max(rmq1[i][k],rmq1[j-(1<<k)+1][k])-min(rmq2[i][k],rmq2[j-(1<<k)+1][k]);
33 }
34 int main()
35 {
36 int i,j,k;
37 scanf("%d%d",&N,&Q);
38 for(i=1;i<=N;i++)
39 {
40 scanf("%d",&a[i]);
41 rmq1[i][0]=a[i];
42 rmq2[i][0]=a[i]; //初始化
43 }
44 DP(N);
45 while(Q--)
46 {
47 scanf("%d%d",&i,&j);
48 printf("%d\n",search(i,j));
49 }
50 }
51
求距離一個city第k近的city。根據dijkstra的特點，循環K+1次即找到了距源點距離第K近的。 Code：
1 #include<iostream>
2 #define M 1000000000
3 #define MAX 202
4 int map[MAX][MAX],dis[MAX];
5 bool flag[MAX];
6 void dijkstra(int n,int s,int key) // n is the number of point,and start from s ,key is the key-city
7 {
8 int i,j,k,temp,md;
9 memset(flag,false,sizeof(flag));
10 for(i=0;i<MAX;i++)
11 dis[i]=M;
12 dis[s]=0;
13 for(i=1;i<=key+1;i++)
14 {
15 md=M;
16 for(j=0;j<n;j++) //找到距離當前最近的
17 {
18 if(!flag[j]&&dis[j]<md)
19 {
20 md=dis[j];
21 temp=j;
22 }
23 }
24 flag[temp]=true; //將這個點加進來
25 for(j=0;j<n;j++) //松弛操作
26 {
27 if(!flag[j]&&md+map[temp][j]<dis[j])
28 dis[j]=md+map[temp][j];
29 }
30 }
31 printf("%d\n",temp);
32 }
33 int main()
34 {
35 int i,j,k,m,n,p;
36 while(scanf("%d",&n)!=EOF)
37 {
38 if(n==0) break;
39 scanf("%d",&m);
40 for(i=0;i<MAX-1;i++)
41 for(j=i+1;j<MAX;j++)
42 map[i][j]=map[j][i]=M;
43 for(i=1;i<=m;i++)
44 {
45 scanf("%d%d%d",&j,&k,&p);
46 map[j][k]=map[k][j]=p;
47 }
48 scanf("%d",&k);
49 dijkstra(n,0,k);
50 }
51 return 0;
52 }
53
題意是有n個農場，農場有N塊地，其中M條路是雙向的，S條路是單向的。雙向的路權值為正，單向的路權值為負。需要判斷有沒有負環。
以下是bellman_ford算法，需要注意的地方在注釋里邊。
1 #include<stdio.h>
2 #include<string.h>
3 #define INF 0x1f1f1f1f
4 #define MAX 5500
5 int dist[MAX/10];
6 struct edge
7 {
8 int u,v,w; //u為起點 v為終點 w是權值
9 }edge[MAX];
10 int bellman_ford2(int n,int m,int s) //n個點，m條邊，起點是s
11 {
12 memset(dist,0x1f1f,sizeof(dist));
13 dist[s]=0;
14 int i,j,k,p,u,v;
15 bool flag;
16 for(i=1;i<n;i++) //n-1次迭代
17 {
18 flag=false; //用來標記某一次是否是更新
19 for(j=0;j<m;j++) //對每條邊進行松弛，即迭代一次
20 {
21 u=edge[j].u;
22 v=edge[j].v;
23 if(dist[v]>dist[u]+edge[j].w)
24 {
25 dist[v]=dist[u]+edge[j].w;
26 flag=true; //如果這一次有某條邊可以松弛
27 }
28 }
29 if(!flag) //如果某一次所有邊都沒有松弛，
30 return 1; // 可以確定沒有負環，返回 1
31 }
32 flag=false;
33 for(i=0;i<m;i++) //對所有邊進行第n次松弛
34 {
35 u=edge[i].u;
36 v=edge[i].v;
37 if(dist[v]>dist[u]+edge[i].w)
38 {
39 dist[v]=dist[u]+edge[i].w;
40 flag=true;
41 }
42 if(flag) return -1; //如果還有更新，有負環 返回 -1
43 }
44 return 1; //否則返回 1
45 }
46 int main()
47 {
48 int i,j,k,m,n,p,q,N,M;
49 int S;
50 scanf("%d",&n);
51 for(i=1;i<=n;i++)
52 {
53 scanf("%d%d%d",&N,&M,&S);
54 int t=0;
55 for(j=1;j<=M;j++)
56 {
57 scanf("%d%d%d",&p,&q,&k);
58 edge[t].u=p; //由于邊是雙向的，需要是兩條
59 edge[t].v=q;
60 edge[t].w=k; t++;
61 edge[t].u=q;
62 edge[t].v=p;
63 edge[t].w=k; t++;
64 }
65 for(j=1;j<=S;j++)
66 {
67 scanf("%d%d%d",&p,&q,&k);
68 edge[t].u=p;
69 edge[t].v=q;
70 edge[t].w=-1*k; t++; //單向的邊權值為負
71 }
72 if(bellman_ford2(N,S+2*M,1)==-1) //如果有負環 YES
73 printf("YES\n");
74 else
75 printf("NO\n");
76 }
77 }
78
題意大概是給一組數M,N，求出第M個末位有N個0的Fibonacci數列是第幾項。 乍一看，嚇我一跳，結果在2^31內，大的驚人。后來拿一個程序（正好是TOJ的一道題，求1000位內的Fibonacci數列）暴力了下，好家伙，有規律的。 第一個末位有1個0的是第15項，第二項第30…然后看末位有2個0的，第一個是150項，第二個第300項。然后很高興了寫了個程序，WA... 有點暈，又暴力了下，加大范圍，發現第一個末位3個0的不是1500項，而是750項。無奈了，好奇怪。于是猜只有這一個特例，依然WA。最后請教了個 學長，他說他也是猜的，不過后邊的確實都是10倍了，就那一個特例。 接下來其實過程異常艱辛，不過最終思路很清晰，也AC了。 --------------------------------------------------------我是低調的分割線------------------------------------------------------------------------------------- 大概是這樣分布的： 15 30 45 ... 150 165 180 195 ... 300 ... 750 ... 1500 ... 7500 第1個0 第2個0 第3個0 第1個00 第10個0 第11個0 第12個0 第2個00 第1個000 第1個0000
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
所以可以看到，不能直接按間隔算，因為比如150.，它算2個0，而不是第10個1個0。 又不能枚舉，一定會超時（確實超了） 所以可以先按照沒有重疊算，然后加上重疊的，重疊的只算下一個就好，因為再后邊的也就都包括了。 算重疊的部分要把特殊的2拿出來。倍數是5就是 4 1 4 1 4 1這樣分布，10的話就是 9 1 9 1 9 1 9 1 9 1，所以按照這樣算， 比如要求第14個末位有2個0的，14%4！=0 ，14/4=3，所以重疊了3次。又比如20, 20%4==0，20/4-1=4，重疊4次。 Code：
1 #include<stdio.h>
2 int main(void)
3 {
4 int a[18]={0,15,150,750,7500,75000,750000,7500000,75000000,750000000}; //保存第一個連續1個0，2個0 的第一個
5 int i,j,k,m,n,cas,key;
6 scanf("%d",&cas);
7 while(cas--){
8 scanf("%d%d",&n,&m);
9 key=m*a[n];
10 if(n==2){
11 if(m%4!=0) key+=(m/4)*a[n];
12 else key+=(m/4-1)*a[n];
13 }
14 else{
15 if(m%9!=0) key+=(m/9)*a[n];
16 else key+=(m/9-1)*a[n];
17 }
18 printf("%d\n",key);
19 }
20 }
一個不是很難但是很麻煩的字符串處理問題。我記得在上學期就看過這個題，覺得太麻煩就沒做。 今天終于搞定它了，而且我覺得代碼在AC里也算短的了。 大意是給一個域名，然后找到它的什么協議，一級域名之類的。 Samble Input :
3
ftp://acm.baylor.edu:1234/pub/staff/mr-p
http://www.informatik.uni-ulm.de/acm
gopher://veryold.edu
Sample Output:
URL #1
Protocol = ftp
Host = acm.baylor.edu
Port = 1234
Path = pub/staff/mr-p
URL #2
Protocol = http
Host = www.informatik.uni-ulm.de
Port = <default>
Path = acm
URL #3
Protocol = gopher
Host = veryold.edu
Port = <default>
Path = <default>
下面是代碼：
1 #include<iostream>
2 #include<string>
3 using namespace std;
4 int main()
5 {
6 int i,j,k,m,n,len,key;
7 string a,a1,a2,a3,a4;
8 cin>>n;
9 for(j=1;j<=n;j++){
10 cin>>a;
11 a1=a2=a3=a4="<default>"; //事先將所有字符串標記為" default "
12 len=a.length();
13 for(i=0;i<len;i++)
14 if(a[i]==':'){ //一旦遇到':'就跳出
15 key=i;
16 a1=a.substr(0,key); // a1是協議名稱
17 break;
18 }
19 for(i=key+3;i<len;i++){
20 if(a[i]==':'||a[i]=='/') //二級域名遇到':' 或者'/' 就停止
21 break;
22 else
23 continue;
24 }
25 if(key+3<len)
26 a2=a.substr(key+3,i-key-3);
27 key=i; m=1;
28 for(i=key;i<len;i++){ //k 用來表示起始的位置
29 if(isdigit(a[i])){
30 if(m){ k=i;m=0; }
31 continue;
32 }
33 else if(a[i]=='/') //遇到'/'跳出
34 break;
35 } // 如果存在三級域名，則賦值
36 if(i!=key)
37 a3=a.substr(k,i-k);
38 key=i+1;
39 if(key<len)a4=a.substr(key,len-key); //剩下的是a4
40 cout<<"URL #"<<j<<endl;
41 cout<<"Protocol = "<<a1<<endl<<"Host = "<<a2<<endl<<"Port = "<<a3<<endl<<"Path = "<<a4<<endl;
42 cout<<endl;
43 }
44
45 }
又是一個并查集，題意大概是N個學生，學生0是SARS疑似，學生分為M組，一個學生可以屬于不同組，只要和疑似學生在一組，自己也就成了疑似，問最后又多少學生是疑似病例。
Code：
1 #include<stdio.h>
2 #define MAX 30002
3 int m,n;
4 struct type
5 {
6 int father,v;
7 }a[MAX];
8 void initial(int n)
9 {
10 int i;
11 for(i=0;i<n;i++){
12 a[i].father=i;
13 a[i].v=1;
14 }
15 }
16 int find(int n)
17 {
18 if(a[n].father!=n)
19 return find(a[n].father);
20 return n;
21 }
22 void Union(int root1,int root2)
23 {
24 int t1,t2;
25 t1=find(root1);
26 t2=find(root2);
27 if(t1==t2) return ;
28 if(t1!=t2){
29 if(a[t1].v<a[t2].v){
30 a[t1].father=t2;
31 a[t2].v+=a[t1].v;
32 }
33 else{
34 a[t2].father=t1;
35 a[t1].v+=a[t2].v;
36 }
37 }
38 }
39 int main()
40 {
41 int cas,i,j,k,p,q,N,M;
42 while(scanf("%d%d",&N,&M)!=EOF){
43 if(N==0&&M==0) break;
44 initial(N);
45 for(i=1;i<=M;i++){
46 scanf("%d",&k);
47 scanf("%d",&p);
48 for(j=2;j<=k;j++){
49 scanf("%d",&q);
50 Union(p,q);
51 }
52 }
53 k=find(0);
54 printf("%d\n",a[k].v);
55 }
56
57
58 }
|