狀態(tài)壓縮求哈密頓回路

#include<bits/stdc++.h>
using namespace std;
bool dp[23][1<<21];
char s[22][22];
bool vis[35];
int ans[25];
int n,f=0;
bool dfs(int now,int cur,int cnt)
{ans[cnt]=now;if(cnt==n){if(s[now][1]=='W'||s[1][now]=='L'){f=1;for(int i=1;i<n;i++){cout<<ans[i]<<' ';}cout<<ans[n]<<endl;return 1;}return 0;}int x=1;for(int i=2;i<=n;i++){x<<=1;int st=cur|x;if(!vis[i]&&(s[now][i]=='W'||s[i][now]=='L')&&!dp[i][st]){vis[i]=1;if(dfs(i,st,cnt+1))return 1;vis[i]=0;}dp[i][st]=1;}return 0;
}
int main()
{//int n;cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cin>>s[i][j];}vis[1]=1;dfs(1,1,1);if(f==0)cout<<"No Solution"<<endl;
}

總結(jié)

以上是生活随笔為你收集整理的pat 食物链（状态压缩求哈密顿回路）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。