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 }
