http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4109

題意：n個(gè)人參加會(huì)議，如果當(dāng)參與者進(jìn)入大廳時(shí)，如果他或她發(fā)現(xiàn)他或她的朋友都不在大廳中，那么即使他或她的朋友稍后將進(jìn)入大廳，該參與者也會(huì)感到不快樂(lè)。求最小化不滿意參與者數(shù)量，并給出一個(gè)入場(chǎng)順序，如果存在多個(gè)答案，輸出字典序最小的順序

題解：并查集+優(yōu)先隊(duì)列

不要用memset，TLE警告

C++版本一

鏈?zhǔn)较蚯靶沁叴?/p>

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=1000000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans[N],cnt,flag,temp,sum; int vis[N],pre[N],head[N]; char str; struct node{}; struct Edge {int to;int next; } edge[N * 2]; int cnt_edge = 0; void add_edge(int from, int to) {edge[cnt_edge].to = to;edge[cnt_edge].next = head[from];head[from] = cnt_edge++; } int find(int x){return pre[x]==x?x:pre[x]=find(pre[x]);} priority_queue<int,vector<int>,greater<int> >q; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){vis[i]=0;head[i]=-1;pre[i]=i;//G[i].clear();}cnt=0;sum=0;while(!q.empty()){q.pop();}//memset(vis,0,sizeof(vis));//memset(head, -1, sizeof(head));cnt_edge = 0;//memset(pre,0,sizeof(pre));while(m--){scanf("%d%d",&u,&v);//G[u].push_back(v);//G[v].push_back(u);add_edge(u,v);add_edge(v,u);int tu=find(u);int tv=find(v);if(tu!=tv){if(tu<tv)pre[tv]=tu;elsepre[tu]=tv;}}for(int i=1;i<=n;i++){if(pre[i]==i){sum++;q.push(i);vis[i]=1;}}while(!q.empty()){int u=q.top();q.pop();ans[++cnt]=u;for(int i=head[u];~i;i=edge[i].next){int v=edge[i].to;if(vis[v]==0){vis[v]=1;q.push(v);}}}cout<<sum<<endl;for(int i=1;i<=n;i++)printf("%d%c",ans[i]," \n"[i==n]);}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

?C++版本二

vector邊存

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=1000000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans[N],cnt,flag,temp,sum; int vis[N],pre[N]; char str; struct node{}; vector<int>G[N]; int find(int x){return pre[x]==x?x:pre[x]=find(pre[x]);} priority_queue<int,vector<int>,greater<int> >q; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){vis[i]=0;pre[i]=i;G[i].clear();}cnt=0;sum=0;while(!q.empty()){q.pop();}while(m--){scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);int tu=find(u);int tv=find(v);if(tu!=tv){if(tu<tv)pre[tv]=tu;elsepre[tu]=tv;}}for(int i=1;i<=n;i++){if(pre[i]==i){sum++;q.push(i);vis[i]=1;}}while(!q.empty()){int u=q.top();q.pop();ans[++cnt]=u;for(int i=0,j=G[u].size();i<j;i++){int v=G[u][i];if(vis[v]==0){vis[v]=1;q.push(v);}}}cout<<sum<<endl;for(int i=1;i<=n;i++)printf("%d%c",ans[i]," \n"[i==n]);}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的Welcome Party的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。