璀璨光滑

C++14(g++5.4) 解法, 执行用时: 3411ms, 内存消耗: 134976K, 提交时间: 2020-07-16 13:18:00

#include <bits/stdc++.h>

using namespace std;

struct GG{
    bool g[270000];
}G[20];
int n,m,i,j,k;
bool cmp(GG ab,GG ac)
{
    for(i=1;i<=(1<<n);i++)
    if(ab.g[i]!=ac.g[i]) return ab.g[i]>ac.g[i];
    return 0;
}
vector<int>q[270000];
int a[270000];
bool b[270000];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
    scanf("%d%d",&n,&m);
    for(i=1;i<=(1<<n);i++) {q[i].clear();a[i]=0;b[i]=0;}
    queue<int>p;
    while(m--)
    {
        scanf("%d%d",&i,&j);
        q[i].push_back(j);
        q[j].push_back(i);
    }
     a[1]=0;b[1]=1;
    for(i=0;i<n;i++)
      {
         j=q[1][i];
         a[j]=(1<<i);
         p.push(j);
      }
    while(!p.empty())
    {
        k=p.front();p.pop();
        if(b[k]) continue;
        b[k]=1;
        for(i=0;i<n;i++)
        {
            j=q[k][i];
            if(b[j]) continue;
            a[j]|=a[k];
            p.push(j);
        }
    }
    for(i=1;i<=(1<<n);i++)
        for(j=0;j<n;j++)
            G[j].g[i]=(a[i]>>j)&1;

    sort(G,G+n,cmp);

    for(i=1;i<=(1<<n);i++){
        for(k=j=0;j<n;j++)
            if(G[j].g[i]) k|=(1<<j);
            printf("%d ",k);
    }
    printf("\n");
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 4109ms, 内存消耗: 76068K, 提交时间: 2020-07-15 13:02:43

#include<bits/stdc++.h>
#define PB push_back
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
typedef vector<int>VI;
const int N=20,M=(1<<18)+5;
int T,n,m,id[M];VI G[M];bool ban[M],vis[M];
struct data{
	int x[M];
	bool operator<(const data&k2)const{
		rep(i,1,1<<n)if(x[i]!=k2.x[i])return x[i]>k2.x[i];
		return 0;
	}
}A[N];
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		rep(i,1,1<<n)G[i].clear(),ban[i]=vis[i]=(i==1),id[i]=0;
		rep(i,1,m){
			int k1,k2;scanf("%d%d",&k1,&k2);
			G[k1].PB(k2),G[k2].PB(k1);
		}
		queue<int>q;
		rep(i,0,SZ(G[1])-1)id[G[1][i]]=1<<i,q.push(G[1][i]);
		while(SZ(q)){
			int k1=q.front();q.pop();vis[k1]=1;
			for(auto j:G[k1]){
				if(vis[j])continue;
				id[j]|=id[k1];
				if(!ban[j]){
					ban[j]=1;
					q.push(j);
				}
			}
		}
		rep(j,0,n-1)rep(i,1,1<<n)A[j].x[i]=0;
		rep(i,1,1<<n)rep(j,0,n-1)if(id[i]>>j&1)A[j].x[i]=1;
		sort(A,A+n);
		rep(i,1,1<<n){
			int ans=0;
			rep(j,0,n-1)if(A[j].x[i])ans|=1<<j;
			printf("%d ",ans);
		}
		puts("");
	}
	return 0;
}

/*
1
3
12
1 2
1 3
1 4
2 5
3 5
3 6
4 6
2 7
4 7
5 8
6 8
7 8
*/

详情