为啥邻接矩阵存图能过,邻接表就 wa2,3 呢??
查看原帖
为啥邻接矩阵存图能过,邻接表就 wa2,3 呢??
400969
yxy_楼主2022/4/22 11:02

数据的锅还是我写法有问题?? 还是什么情况没有考虑到??


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;
} 
2022/4/22 11:02
加载中...