数据的锅还是我写法有问题?? 还是什么情况没有考虑到??
vector邻接表存图:
//https://www.luogu.com.cn/problem/P4906
#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof a)
#define pb push_back
const int N = 2010, mod = 1e9+7;
int T, n, m;
int a[N][N];
vector<int> v[N];
int f[(1<<21) + 10];
int endd, ans = 1e9;
void bfs()
{
queue<int> que;
que.push(0);
f[0] = 1;
while(que.size())
{
int x = que.front();
que.pop();
for(int i=1;i<=n;i++)
{
int state = x ^ (1<<i);
for(auto tx : v[i])
{
state ^= (1<<tx);
for(auto txx : v[tx])
{
state ^= (1<<txx);
}
}
if(!f[state]){
f[state] = f[x] + 1, que.push(state);
if(state == endd) {ans = f[x]; return;}
}
}
}
}
signed main(){
Ios;
cin >> n;
for(int i=1;i<=n;i++)
{
int cnt;cin >> cnt;
while(cnt--)
{
int x;cin>>x;
if(x == i) continue;
if(find(v[i].begin(), v[i].end(), x) != v[i].end()) continue;
v[i].pb(x);
}
}
for(int i=1;i<=n;i++) endd += (1<<i);
bfs();
if(ans != 1e9) cout<<ans;
else cout << "Change an alarm clock,please!";
return 0;
}
临界矩阵:
//https://www.luogu.com.cn/problem/P4906
#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof a)
const int N = 2010, mod = 1e9+7;
int T, n, m;
int a[N][N];
vector<int> v[N];
int f[(1<<21) + 10];
int endd, ans = 1e9;
void bfs()
{
queue<int> que;
que.push(0);
f[0] = 1;
while(que.size())
{
int x = que.front();
que.pop();
for(int i=1;i<=n;i++)
{
int state = x ^ (1<<i);
for(int tx=1;tx<=n;tx++)
{
if(!a[i][tx] || tx == i) continue;
state ^= (1<<tx);
for(int txx=1;txx<=n;txx++)
{
if(!a[tx][txx] || txx == tx) continue;
state ^= (1<<txx);
}
}
if(!f[state]){
f[state] = f[x] + 1, que.push(state);
if(state == endd) {ans = f[x]; return;}
}
}
}
}
signed main(){
Ios;
cin >> n;
for(int i=1;i<=n;i++)
{
int cnt;cin >> cnt;
while(cnt--)
{
int x;cin>>x;
a[i][x] = 1;
}
}
for(int i=1;i<=n;i++) endd += (1<<i);
bfs();
if(ans != 1e9) cout<<ans;
else cout << "Change an alarm clock,please!";
return 0;
}