ZOJ 4109 Welcome Party
- 2020 年 3 月 5 日
- 筆記
题目链接：(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("%dn",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 }
