I - Indoorienteering Gym - 101482I（双向搜索）

本文主要是介绍I - Indoorienteering Gym - 101482I（双向搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Lukáš really likes orienteering, a sport that requires locating control points in rough terrain. To entertain the NWERC participants Lukáš wants to organize an orienteering race. However, it would be too harsh for the participants to be outdoors in this cold Swedish November weather, so he decided to jump on the new trend of indoor races, and set the race inside the B building of Linköping University.
Lukáš has already decided on the locations of the control points. He has also decided on the exact length of the race, so the only thing remaining is to decide in which order the control points should be visited such that the length of the total race is as he wishes. Because this is not always possible, he asks you to write a program to help him.
Note from the organizer: the NWERC indoorienteering race for this year has been cancelled since we neglected to apply for an orienteering permit in time from the university administration. (We still need you to solve the problem so that we can organize it for next year.)
Input
The input consists of:
Fredrik and Tommy lost in the B building. Photo by Tommy Olsson. cc-by-sa
• onelinewithtwointegersn(2≤n≤14)andL(1≤L≤1015),thenumberofcontrol points and the desired length of the race, respectively;
• n lines with n integers each. The jth integer on the ith line, dij, denotes the distance betweencontrolpointiandj(1≤dij ≤Lfori̸=j,anddii =0).Forall1≤i,j,k≤N itisthecasethatdij =dji anddij ≤dik +dkj.
Output
Output one line with “possible” if it is possible to visit all control points once in some order and directly return to the first one such that the total distance is exactly L, and “impossible” otherwise.
Sample Input 1 Sample Output 1
4 10 0321 3013 2102 1320
possible
NWERC 2014 Problem I: Indoorienteering
17
Sample Input 2 Sample Output 2
35 012 103 230
impossible

题意：
n个点，点间最短距离给出来了。
求遍历n个点，最后回到起点，其他点只走一次的。
求距离和是否能达到L。

思路：
看了题解，类似双向搜索，拆成一半分别搜。
最后会形成一个环，以0为拆点将环拆成两半，那么0是其中一个环的起点，再分别枚举全排列。

ACNEW

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
#include <queue>
#include <cmath>
#include <vector>
#include <map>
#include <ctime>using namespace std;typedef long long ll;
const int maxn = 20 + 7;ll d[maxn][maxn];
int l[maxn],r[maxn],vis[maxn],l_tmp[maxn],a[maxn];
int cnt,cnt2,cnt3;
vector<ll>R;
ll n,L;void init(int ed) {R.clear();do {ll num2 = 0;for(int i = 2;i <= cnt2;i++) {num2 += d[r[i - 1]][r[i]];}num2 += d[0][r[1]] + d[r[cnt2]][ed];R.push_back(num2);}while(next_permutation(r + 1, r + cnt2 + 1));sort(R.begin(),R.end());
}int Bin(ll x) {return lower_bound(R.begin(),R.end(),x) - R.begin();
}bool Find(ll num) {int pos = Bin(L - num);if(pos < R.size() && R[pos] == L - num) {return true;}return false;
}bool check2(int ed) {do {ll num = d[0][l_tmp[1]] + d[l_tmp[cnt3]][ed];for(int i = 2;i <= cnt3;i++) {num += d[l_tmp[i - 1]][l_tmp[i]];}if(Find(num)) return true;} while(next_permutation(l_tmp + 1,l_tmp + 1 + cnt3));return false;
}bool check() {for(int i = 2;i <= cnt;i++) {cnt3 = 0;init(l[i]);for(int j = 2;j <= cnt;j++) {if(j == i) continue;l_tmp[++cnt3] = l[j];}if(cnt >= 3) {if(check2(l[i])) return true;} else {ll num = d[0][l[i]];if(Find(num)) return true;}}return false;
}int main() {clock_t start_time=clock();scanf("%lld%lld",&n,&L);for(int i = 0;i < n;i++) {for(int j = 0;j < n;j++) {scanf("%lld",&d[i][j]);}}if(n == 2) {if(d[0][1] * 2 != L) {printf("impossible\n");} else {printf("possible\n");}return 0;}int num = (n + 1) / 2;for(int i = 0;i < (1 << n);i++) {cnt = cnt2 = 0;for(int j = 0;j < n;j++) {if(i & (1 << j)) {l[++cnt] = j;} else {r[++cnt2] = j;}}if(cnt == num && l[1] == 0) {if(check()) {printf("possible\n");return 0;}}}printf("impossible\n");clock_t end_time=clock();//    cout<< "Running time is: "<<static_cast<double>(end_time-start_time)/CLOCKS_PER_SEC*1000<<"ms"<<endl;//输出运行时间return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>using namespace std;typedef long double ld;typedef long long ll;const int maxn = 1e5 + 7;
ll d[20][20];
int l[20],r[20];
int num[20];
int lsiz,rsiz;
int n;
ll v[maxn];
int tot;
ll L;bool check(ll val) {if(val <= 0) return false;int pos = lower_bound(v + 1,v + 1 + tot,val) - v;if(v[pos] == val) return true;return false;
}void cal(int s,int e) {tot = 0;do {ll cnt = 0;cnt += d[e][r[1]] + d[r[rsiz]][s];for(int i = 2;i <= rsiz;i++) {cnt += d[r[i - 1]][r[i]];}v[++tot] = cnt;}while(next_permutation(r + 1, r + 1 + rsiz));sort(v + 1,v + 1 + tot);tot = unique(v + 1,v + 1 + tot) - (v + 1);
}bool cal2(int s,int e) {cal(s,e);ll cnt = L;int cur = 0;for(int i = 1;i <= lsiz;i++) {if(l[i] == e || l[i] == s) continue;num[++cur] = l[i];}if(cur) {do {cnt = L;cnt -= d[s][num[1]] + d[num[cur]][e];for(int i = 2;i <= cur;i++) {cnt -= d[num[i - 1]][num[i]];}if(check(cnt)) {return true;}}while(next_permutation(num + 1,num + cur + 1));}else {cnt -= d[e][s];if(check(cnt)) {return true;}}return false;
}bool solve() {for(int i = 2;i <= lsiz;i++) {if(cal2(0,l[i])) return true;}if(lsiz == 1) {if(cal2(0,0)) return true;}return false;
}int main() {scanf("%d%lld",&n,&L);for(int i = 0;i < n;i++) {for(int j = 0;j < n;j++) {scanf("%lld",&d[i][j]);}}if(n == 2) {if(d[0][1] * 2 == L) {printf("possible\n");}else printf("impossible\n");return 0;}int cnt = (1 << n);int flag = 0;for(int i = 1;i < cnt;i++) {lsiz = 0;rsiz = 0;for(int j = 0;j < n;j++) {if(i & (1 << j)) {l[++lsiz] = j;}else {r[++rsiz] = j;}}if(lsiz == n / 2 && l[1] == 0) {if(solve()) {printf("possible\n");flag = 1;break;}}}if(flag == 0) printf("impossible\n");return 0;
}
//4 10
//0 3 2 1
//3 0 1 3
//2 1 0 2
//1 3 2 0