社区讨论

状压dp WA on#^求调

CF906C Party参与者 3已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@lys36u34
此快照首次捕获于
2024/07/19 10:34
2 年前
此快照最后确认于
2024/07/19 11:18
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
#define mmt(a,b) memset(a,b,sizeof(a))
#define test(x) cout<<#x<<" = "<<x<<endl
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
#define endl '\n'
#define enter putchar(endl)
//#define int long long
using namespace std;
inline void read(int &x);
inline void ffout(int x);
inline void ffout(string b);
inline void ffout(int x,char b);
inline void ffout(int x,string b);
inline void print(string name,int a[],int r);
const int inf=0x3f3f3f3f,N=22;
int n,m;
int a[N+1],dp[1<<N],ans[N+1],fa[1<<N];
void find(int x)
{
	if(fa[x])find(fa[x]);
	if(ans[x])cout<<ans[x]<<' ';
}
signed main()
{
	int i,j,k;
	mmt(dp,0x3f);
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		int x,y;
		cin>>x>>y;
		a[x]|=(1<<y-1);
		a[y]|=(1<<x-1);
	}
	for(i=1;i<=n;i++)
	{
		a[i]|=(1<<i-1);
		dp[1<<i-1]=0;
	}
	if(m==n*(n-1)/2)
	{
		cout<<0;
		return 0;
	}
	for(k=1;k<(1<<n);k++)
	{
		for(i=1;i<=n;i++)
		{
			if( k&(1<<i-1) && dp[k|a[i]]>dp[k]+1)
			{
				dp[k|a[i]]=dp[k]+1;
				fa[k|a[i]]=k;
				ans[k|a[i]]=i;
			}
		}
	}
	cout<<dp[(1<<n)-1]<<endl;
	find((1<<n)-1);
	return 0;
}









inline void ffout(string b)
{
	int len=b.size();
    for(int i=0;i<len;++i)putchar(b[i]);
}
inline void read(int &x)
{
	int f=1;x=0;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	x=x*f;
}
inline void ffout(int x)
{
    if(x<0){x=-x; putchar('-'); }
    short sta[63],top=0;
    do{ sta[top++]=x%10; x/=10; }while(x);
    while(top) putchar(sta[--top]+'0');
}
inline void ffout(int x,char b)
{
    if(x<0){x=-x; putchar('-'); }
    short sta[63],top=0;
    do{ sta[top++]=x%10; x/=10; }while(x);
    while(top) putchar(sta[--top]+'0');
    putchar(b);
}
inline void ffout(int x,string b)
{
    if(x<0){x=-x; putchar('-'); }
    short sta[63],top=0;
    do{ sta[top++]=x%10; x/=10; }while(x);
    while(top) putchar(sta[--top]+'0');
    ffout(b);
}
inline void print(string name,int a[],int r)
{
	ffout(name);
	putchar(':');
	for(int i=1;i<=r;i++)
		ffout(a[i],' ');
	putchar(endl);
}





回复

7 条回复,欢迎继续交流。

正在加载回复...