|
|
并查集或者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 }
|