2017icpc beijing-I题-Colored Nodes

题意：给出n个点m条边 然后每个时间点，与这个位置相连的所有点就会变成这个点的颜色 比如时间1的时候就是以这个位置相连的点2 变成1的颜色同理如下，通过2个循环之后除了第一次循环的时候看不出来循环节 在第二次循环的时候就已经有了循环节 然后把一个循环内的d[i][1]+d[i][2]+…+d[i][无穷] 其实找到一个循环节之后就把这个循环节中的所有节点之和相加/n就可以得到一个值直接暴力出来循环节就行

#include<iostream> //找出循环节把循环节中的元素第二个n次的都加起来除以n 
#include<cstring> 
#include<algorithm>
using namespace std;
struct node{
	int next,to;
}start[200005];   //用前向星记录
int cnt;
int head[100005];  //前向星记录每个节点的下一个节点
int jl[100005];    //
int jxys[100005];  //记录下每个节点的颜色数
int ans[100005];   //记录下每个颜色在一个循环节之后的所有的总数
bool pd[100005]; //记录下哪个颜色循环节中存在
int jx[100005];  //记录下在循环节中可以存在颜色便于之后循环
bool cmp (int x,int y){  //用于sort升序
	return x>y;
}
void add(int u,int v){ //记录双向因为是无向的链接   增加
	start[cnt].to =v;  
	start[cnt].next = head[u];
	head[u] = cnt++；
	start[cnt].to = u;
	start[cnt].next = head[v];
	head[v] = cnt++;
}
int main()
{
	int n,m;
	while(~scanf("%d %d",&n,&m)){
		cnt=0;
		for(int i=1;i<=n;i++) jl[i]=i;
		memset(head,-1,sizeof(head));  //初始化为-1 
		memset(jxys,0,sizeof(jxys));   //初始的时候都初始化为0便于后边计算 
		memset(ans,0,sizeof(ans));     //ans是记录每个的最后的数 
		memset(pd,0,sizeof(pd)); 
		memset(jx,0,sizeof(jx));
		int a,b;
		for(int i=0;i<m;i++){
			scanf("%d %d",&a,&b);
			add(a,b); 
		}
		for(int i=1;i<=n;i++){
			int cnt;
			for(int j=head[i];j!=-1;j=start[j].next){
				cnt = start[j].to;
				jl[cnt] = jl[i];
			}
		}

		
		for(int i=1;i<=n;i++){
			pd[jl[i]]=1;  //判断每个节点  jl[i]是记录下在一个循环节中的n个点中的颜色然后pd记录每个颜色的是否存在
		}
		int cnt=1;
		for(int i=1;i<=n;i++){
			if(pd[i]) jx[cnt++]=i;  //jx记录记下存在的颜色
		}
		


		for(int i=1;i<=n;i++){ //在n次之后的颜色变化 
			jxys[jl[i]]++;        //记录下啊所有的颜色数
		}
		
//		for(int i=1;i<=n;i++){
//			printf("%d\n",jxys[i]);
//		}
//		system("pause");

		for(int i=1;i<=n;i++){
			int cnt1;
			for(int j=head[i];j!=-1;j=start[j].next){
				cnt1 = start[j].to;
				jxys[jl[cnt1]]--;    //把和i相连的点的颜色减去1
				jl[cnt1] = jl[i];
				jxys[jl[i]]++;     //把i的节点的颜色加上1
			}
			for(int j=1;j<cnt;j++){    //这里的时候不能每次都到n容易超时
//				printf("%d ",jxys[jx[j]]);
				ans[jx[j]]+=jxys[jx[j]];   //ans把每种颜色都加下来
			}
//			system("pause");
		}
		sort(ans+1,ans+n+1,cmp);
		
		for(int i=1;i<=n;i++){
			if(ans[i]){
				printf("%.6lf\n",(ans[i]*1.0)/(n*1.0)); 
			}
			else break;
		}
//		for(int i=1;i<cnt;i++){
//			printf("%d\n",ans[jx[i]]);
//		}
	}
} 

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
 

文章来源: englishcode.blog.csdn.net，作者：知识浅谈，版权归原作者所有，如需转载，请联系作者。

原文链接：englishcode.blog.csdn.net/article/details/83244519