ZOJ 4109 Welcome Party
俩小圈 人气:1题目链接：(https://zoj.pintia.cn/problem-sets/91827364500/problems/91827370504)(https://vjudge.net/problem/ZOJ-4109)
题面复制不过来。
题意：n个人，编号为1~n，m个朋友关系（a和b是朋友，a和c是朋友不代表b和c是朋友），将n个人按照顺序排好，如果一个人前面没有他的朋友那么不满意度加一，让你给出一个排序使得不满意度最小化，有相同结果的排序输出字典序最小的那个。
有关系存在，考虑画图。画完图后发现不满意度的最小值即是图的连通分量的个数，因为每当选定一个连通分量的的人进入序列，与他连接的人就可以都顺着连接加入序列，从而不会增加不满意度。求连通分量个数可用并查集实现。
要求输出字典序最小的，想到了用优先队列实现的bfs，优先选择队列中编号最小的点。
因为用memset导致超时好几次，初始化时最好用多少初始化多少。
代码：
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <cstring>
5 #include <queue>
6 typedef long long ll;
7 using namespace std;
8
9 const int N=1e6+5;
10
11 struct cmp {
12 bool operator()(int a,int b) {
13 return a>b;
14 }
15 };
16
17 priority_queue <int,vector <int>,cmp> Q;
18
19 int E[N<<1],fir[N],nex[N<<1],tot;
20 int per[N];
21 bool vis[N];
22 bool book[N];
23 int n,m,cnt;
24
25 void init() {
26 for(int i=1;i<=n;i++) {
27 per[i]=i;fir[i]=-1;vis[i]=false;book[i]=false;
28 }
29 cnt=tot=0;
30 }
31
32 void connect(int from,int to) {
33 E[tot]=to;
34 nex[tot]=fir[from];
35 fir[from]=tot++;
36 E[tot]=from;
37 nex[tot]=fir[to];
38 fir[to]=tot++;
39 }
40
41 int root(int x) {
42 int tempa,tempb;
43 tempa=x;
44 while(x!=per[x]) x=per[x];
45 while(per[tempa]!=x) {
46 tempb=per[tempa];
47 per[tempa]=x;
48 tempa=tempb;
49 }
50 return x;
51 }
52
53 void merge(int x,int y) {
54 int t1=root(x);
55 int t2=root(y);
56 if(t1!=t2) {
57 per[t1]=t2;cnt++;
58 }
59 }
60
61 void solve() {
62 int cnt=0;
63 while(!Q.empty()) {
64 int q=Q.top();Q.pop();
65 if(vis[q]) continue;
66 vis[q]=true;
67 cnt++;
68 printf("%d",q);
69 if(cnt!=n) printf(" ");
70 for(int i=fir[q];i!=-1;i=nex[i]) {
71 int to=E[i];
72 if(!vis[to]) Q.push(to);
73 }
74 }
75 printf("\n");
76 }
77
78 int main() {
79 int t;
80 scanf("%d",&t);
81 while(t--) {
82 scanf("%d%d",&n,&m);
83 init();
84 for(int i=1;i<=m;i++) {
85 int x,y;
86 scanf("%d%d",&x,&y);
87 connect(x,y);
88 merge(x,y);
89 }
90 printf("%d\n",n-cnt);
91 for(int i=1;i<=n;i++) {
92 if(!book[root(i)]) {
93 book[root(i)]=true;
94 Q.push(i);
95 }
96 }
97 solve();
98 }
99 return 0;
100 }
加载全部内容