Codeforces1206D Shortest Cycle

http://codeforces.com/contest/1206/problem/D
思路：先把所有的0除去，然后，因为元素最多 2 60 2^{60} 260，最坏情况下60+60+1就一定能构成环，所以，大于120个非0元素直接输出3.
否则floyd找最小环。
floyd的dp(k,i,j)中，我们假设环中最大的下标为k，即$i!=j且i<k且j<k$，此时这个环分为经过k的和不经过k的。不经过的就是dp(k-1,i,j)，经过的看邻边即可。
为什么必须邻边，而不能直接dp(k-1,i,k)+dp(k-1,k,j)？
比如1-3，1-4，那么dp(3,1,3)=1,dp(3,1,4)=1,dp(3,3,4)=2,推出1，3，4成环，环的大小为4，这显然大错特错！

#include 
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;ll ai[100000+100];
vector<ll> a;
int n,d[200][200],dist[200][200];
int main()
{//freopen("input.in","r",stdin);cin>>n;a.push_back(0);for(int i=1;i<=n;i++){cin>>ai[i];if(ai[i])a.push_back(ai[i]);}n=a.size()-1;memset(d,INF,sizeof(d));memset(dist,INF,sizeof(d));if(n>120){cout<<3<<endl;exit(0);}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(i==j)dist[i][j]=d[i][j]=0;else if(a[i]&a[j])dist[i][j]=d[i][j]=1;}int ans=INF;for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(k>i&&k>j && i!=j){ans=min((ll)ans,(ll)d[i][j]+dist[i][k]+dist[k][j]);}d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}if(ans==INF)ans=-1;cout<<ans<<endl;exit(0);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！