codeforce D. Shortest Cycle（floyd求最短环）

题目链接：http://codeforces.com/contest/1206/problem/D

给n个点，如果点a[ i ] &a[ j ] 不为0，则点a[ i ] 和 a[ j ] 直接可以连接双向边，如果这些点形成的图中有环，求最短路径的环，如果没有输出-1.

思路：整体是用floyd求最短环，但是数据量很大，有1e5的数据，空跑floyd直接超时，但是由于题目的特殊性，两数相与不为0才有边，那么任意的a[ i ]二进制是有63位的，那么一个数字的二进制最多有63个1，如果总体数字的二进制63位中的任意一位存在三个以上的1，说明有三个数相与都是不为0的，三个数可以互相连边，那么最短环一定是3，靠这个结论解答可以大大缩短时间复杂度，如果a[ i ]（不为0）个数多到某一个Max值时，则某一位上1的个数一定会超过3，那么这个Max值具体是多少呢？没有详细计算，但是一定不会超过63 * 2 = 126个，因为就算每一位分配2个“1”，第127个必定使得一位有3个“1”，那么可以将Max可以暂定为126，也就是说1e5的计算数据大大减少到了126，这样跑floyd就不会超时了。注意如果a[ i ] = 0，直接可以不会加入cnt计数中，因为0与任意数相与都是0.

AC代码：

#include<iostream>

#include<algorithm>

#include<vector>

#include<queue>

#include<cstring>

#define maxn 100005

#define inf 0x3f3f3f3f

using namespace std;

long long int a[maxn];

long long int dist[200][200];

long long int g[200][200];

int n;

int cnt = 1;

long long int ans = 0x3f3f3f3f;

void floyd(){

	for(long long int k = 1;k<=cnt;k++){

		for(long long int i = 1;i<k;i++){

			for(long long int j = i+1;j<k;j++){

				if(dist[i][j] == inf || g[j][k] == inf || g[i][k] == inf){

					continue;

				}

				ans = min(ans,dist[i][j]+g[j][k]+g[k][i]);

			}

		}

		for(long long int i = 1;i<=cnt;i++){

			for(long long int j = 1;j<=cnt;j++){

				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

			}

		}

	}

}

int main(){

	cin>>n;

	for(long long int i = 1;i<=n;i++){

		long long int t;

		cin>>t;

		if(t){

			a[cnt] = t;

			cnt++;

		}

	}

	if(cnt > 126){

		cout<<3;

		return 0;

	}

	for(long long int i = 1;i<=cnt;i++){

		for(long long int j = i+1;j<=cnt;j++){

			if((a[i] & a[j]) ){

				dist[i][j] = 1,dist[j][i] = 1;

				g[i][j] = 1,g[j][i] = 1;

			}

			else{

				dist[i][j] = inf,dist[j][i] = inf;

				g[i][j] = inf,g[j][i] = inf;

			}

		}

	}

	floyd();

	if(ans == inf ){

		cout<<-1;

		return 0;

	}

	cout<<ans;

	return 0;

}

巴特西

codeforce D. Shortest Cycle（floyd求最短环）

最新文章

热门文章