社区讨论
状压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 条回复,欢迎继续交流。
正在加载回复...