首页 > 代码库 > P1726 上白泽慧音(0分)
P1726 上白泽慧音(0分)
题目描述
在幻想乡，上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞，使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由N个村庄（编号为1..N）和M条道路组成，道路分为两种一种为单向通行的，一种为双向通行的，分别用1和2来标记。如果存在由村庄A到达村庄B的通路，那么我们认为可以从村庄A到达村庄B，记为(A,B)。当(A,B)和(B,A)同时满足时，我们认为A,B是绝对连通的，记为<A,B>。绝对连通区域是指一个村庄的集合，在这个集合中任意两个村庄X,Y都满足<X,Y>。现在你的任务是，找出最大的绝对连通区域，并将这个绝对连通区域的村庄按编号依次输出。若存在两个最大的，输出字典序最小的，比如当存在1,3,4和2,5,6这两个最大连通区域时，输出的是1,3,4。
输入输出格式
输入格式：
第1行：两个正整数N,M
第2..M+1行：每行三个正整数a,b,t, t = 1表示存在从村庄a到b的单向道路，t = 2表示村庄a,b之间存在双向通行的道路。保证每条道路只出现一次。
输出格式：
第1行： 1个整数，表示最大的绝对连通区域包含的村庄个数。
第2行：若干个整数，依次输出最大的绝对连通区域所包含的村庄编号。
输入输出样例
输入样例#1：
5 51 2 11 3 22 4 25 1 23 5 1
输出样例#1：
31 3 5
说明
对于60%的数据：N <= 200且M <= 10,000
对于100%的数据：N <= 5,000且M <= 50,000
不会tarjan于是除了第一个点WA其他都超时，，
不做了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 #include<algorithm> 7 using namespace std; 8 const int MAXN=5001; 9 void read(int &n) 10 { 11 char c=‘+‘;int x=0;bool flag=0; 12 while(c<‘0‘||c>‘9‘) 13 {c=getchar();if(c==‘-‘)flag=1;} 14 while(c>=‘0‘&&c<=‘9‘) 15 {x=x*10+c-48;c=getchar();} 16 flag==1?n=-x:n=x; 17 } 18 struct node 19 { 20 int u,v,w,nxt; 21 }edge[MAXN*4]; 22 int head[MAXN]; 23 int num=1; 24 void add_edge(int x,int y,int z) 25 { 26 edge[num].u=x; 27 edge[num].v=y; 28 edge[num].w=z; 29 edge[num].nxt=head[x]; 30 head[x]=num++; 31 } 32 bool have[MAXN][MAXN]; 33 int pre[MAXN]; 34 int nex[MAXN]; 35 int out[MAXN]; 36 void cler() 37 { 38 memset(have,0,sizeof(have)); 39 memset(pre,-1,sizeof(pre)); 40 memset(nex,-1,sizeof(nex)); 41 } 42 int ans=0; 43 int ansbg=0; 44 int n,m; 45 void calc_ans(int bg,int ed) 46 { 47 int num=0; 48 int hh=ed; 49 while(pre[ed]!=-1) 50 { 51 num++; 52 ed=pre[ed]; 53 } 54 num+=1; 55 if(num>ans) 56 { 57 ans=num; 58 ansbg=bg; 59 for(int i=0;i<=n;i++) 60 out[i]=nex[i]; 61 } 62 } 63 void dfs(int bg,int now) 64 { 65 for(int i=head[now];i!=-1;i=edge[i].nxt) 66 { 67 if(!have[now][edge[i].v]) 68 { 69 if(edge[i].v==bg) 70 { 71 calc_ans(bg,now); 72 return ; 73 } 74 have[now][edge[i].v]=1; 75 have[edge[i].v][now]=1; 76 pre[edge[i].v]=now; 77 nex[now]=edge[i].v; 78 dfs(bg,edge[i].v); 79 have[now][edge[i].v]=0; 80 have[edge[i].v][now]=0; 81 pre[edge[i].v]=-1; 82 nex[now]=-1; 83 } 84 } 85 } 86 int main() 87 { 88 89 read(n);read(m); 90 for(int i=1;i<=n;i++) 91 head[i]=-1; 92 for(int i=1;i<=m;i++) 93 { 94 int x,y,how; 95 read(x);read(y);read(how); 96 if(how==1) add_edge(x,y,1); 97 else {add_edge(x,y,1);add_edge(y,x,1);} 98 } 99 for(int i=1;i<=n;i++)100 {101 cler();102 dfs(i,i);103 }104 printf("%d\n",ans);105 if(ansbg)106 printf("%d ",ansbg);107 while(out[ansbg]!=-1)108 {109 ansbg=out[ansbg];110 printf("%d ",ansbg);111 }112 return 0;113 }
P1726 上白泽慧音(0分)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。