Atcoder Beginner Contest 244 F

曹恩
2023-12-01

F - Shortest Good Path

题意:

给你n个点,m条边,无重边,无自环

一个数列如果满足,所有的都在1-N并且两点之间有边连就可以

还有1 0表示路径经过i点的次数是奇数还是偶数

题解:

1.如何表示?

(1)输入时用一个vector表示,后续用auto得到对应的值。

(2)dis[i][j]表示现在状态是i「用二进制来表示」,数为j。

2.如何做?

(1)为什么一开始要u-1,v-1?因为要使用二进制的操作,比如0001,是(1<<0)而不是(1<<1)

(2)BFS,从一个数开始往后搜索,如果没搜过,就继续搜,然后+1,如果搜过了,那就不要了

//
#include <iostream>
#include <vector>
#include <queue>
#define int long long
using namespace std;
const int N = (1 << 17);
const int INF = 0x3f3f3f3f3f3f3f3f;
int dis[N][17];
vector<int> G[20];
queue<pair<int, int>> Q;
int n,m;
signed main() {
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		u--,v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	int M = 1<<n;
	for(int i=0;i<M;i++)
		for(int j=0;j<n;j++)
			dis[i][j]=INF;
//		这里为啥要一开始初始化为1呢?
//		因为我一个数,length为1!
	for(int i=0;i<n;i++){
		dis[1<<i][i]=1;
		Q.push({1<<i,i});
	}
	//		BFS
	while(Q.size()){
		int s = Q.front().first;
		int v = Q.front().second;
		Q.pop();
		for(auto u : G[v]){
			int ns = s ^ (1<<u);
			if(dis[ns][u]<INF) continue;
			dis[ns][u] = dis[s][v] + 1;
//			这就是挑出来的那一个
			Q.push({ns,u});
		}
	}
	int ans = 0;
//	最后是对所有情况进行加总
	for(int i=1;i<M;i++){
		int mm = INF;
		for(int j=0;j<n;j++){
			mm = min(mm,dis[i][j]);
		}
		ans += mm;
	}
	cout<<ans<<endl;
}

 类似资料:

相关阅读

相关文章

相关问答