• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# 题解 y

3小时前 1次浏览

• 如果题面里有提到类似「从点1出发」的字样，特别注意点1根本就没有连边的情况

• 所以需要爆搜某些特定组合/边权和/异或和（？）的时候可以考虑meet in middle优化

Code:

``````#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 150
#define ll long long
#define ld long double
#define usd unsigned
#define ull unsigned long long
//#define int long long

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
char buf[1<<21], *p1=buf, *p2=buf;
int ans=0, f=1; char c=getchar();
while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
return ans*f;
}

int n, m, d, D;
int dis0[N][N], dis1[N][N];
bool edge0[105], edge1[105];
struct edge{int to, next, val;}e[100010];

namespace force{
bool vis[1<<21];
void dfs(int u, int s, int d) {
//cout<<"dfs "<<u<<' '<<s<<' '<<d<<endl;
if (d<=0) {vis[s]=1; return ;}
for (int i=head[u]; i; i=e[i].next) {
dfs(e[i].to, (s<<1)|e[i].val, d-1);
}
}
void solve() {
dfs(1, 0, d);
int lim=1<<d, ans=0;
for (int i=0; i<lim; ++i) if (vis[i]) ++ans; //, cout<<i<<' '; cout<<endl;
printf("%dn", ans);
exit(0);
}
}

bool vis[1<<21];
vector<int> vec[105][22];
void dfs(int u, int d) {
//if (clock()>800000) {cout<<(1<<D)<<endl; exit(0);}
//cout<<"dfs "<<u<<' '<<d<<endl;
//++cnt[u][d];
if (vec[u][d].size()) return ;
if (d<=1) {
bool t[2]={0, 0};
for (int i=head[u],v; i; i=e[i].next) {
if (!t[e[i].val]) vec[u][d].push_back(e[i].val), t[e[i].val]=1; //, cout<<1<<endl;
//cout<<i<<endl;
}
//cout<<"vec "<<u<<' '<<d<<": "; for (int i=0; i<vec[u][d].size(); ++i) cout<<vec[u][d][i]<<' '; cout<<endl;
return ;
}
for (int i=head[u],v; i; i=e[i].next) {
v = e[i].to;
dfs(v, d-1);
//cout<<"go "<<v<<' '<<d-1<<endl;
for (int j=0; j<vec[v][d-1].size(); ++j)
vec[u][d].push_back((e[i].val<<(d-1))|vec[v][d-1][j]); //, cout<<u<<' '<<d<<' '<<(e[i].val<<(d-1))<<' '<<vec[v][d-1][j]<<endl;
}
sort(vec[u][d].begin(), vec[u][d].end());
vector<int>::iterator it=unique(vec[u][d].begin(), vec[u][d].end());
while (it!=vec[u][d].end()) vec[u][d].pop_back();
//cout<<"vec "<<u<<' '<<d<<": "; for (int i=0; i<vec[u][d].size(); ++i) cout<<vec[u][d][i]<<' '; cout<<endl;
}
void solve() {
dfs(1, d);
//int lim=1<<n, ans=0;
//cout<<double(sizeof(cnt))/1024/1024<<endl;
//for (int i=0; i<lim; ++i) if (vis[i]) ++ans;
//cout<<3<<endl;
printf("%dn", vec[1][d].size());
//cout<<vec[1][d].size()<<endl;
//for (int i=0; i<vec[1][d].size(); ++i) cout<<vec[1][d][i]<<' '; cout<<endl;
//for (int i=1; i<=n; ++i) {for (int j=1; j<=d; ++j) cout<<cnt[i][j]<<' '; cout<<endl;}
exit(0);
}
}

unordered_map<int, bool> mp[105][22];
int cnt=0;
bool dfs(int u, int d, int s) {
//++cnt;
//cout<<"dfs "<<u<<' '<<d<<' '<<bitset<5>(s)<<' '<<bitset<5>(s>>(d-1))<<endl;
if (d<=0) return 1;
if (mp[u][d].find(s)!=mp[u][d].end()) return mp[u][d][s];
if (s>>(d-1)) {if (!edge1[u]) return 0;}
else {if (!edge0[u]) return 0;}
if (e[i].val==s1 && dfs(e[i].to, d-1, s2)) {mp[u][d][s]=1; return 1;}
mp[u][d][s]=0;
return 0;
}
void solve() {
int lim=1<<d, ans=0;
for (int i=0; i<lim; ++i)
if (dfs(1, d, i)) ++ans;
printf("%dn", ans);
//cout<<"cnt: "<<cnt<<endl;
exit(0);
}
}

char mp[105][105][21][1<<11];
bool dfs(int u, int to, int d, int s) {
//cout<<"dfs "<<u<<' '<<to<<' '<<d<<' '<<s<<endl;
if (d<=0) return u==to;
if (mp[u][to][d][s]) return mp[u][to][d][s]>>1;
if (s>>(d-1)) {if (!edge1[u]) return 0;}
else {if (!edge0[u]) return 0;}
if (e[i].val==s1 && dfs(e[i].to, to, d-1, s2)) {mp[u][to][d][s]=3; return 1;}
mp[u][to][d][s]=1;
return 0;
}
void solve() {
int lim=1<<d, ans=0, l1=d/2, l2=d-d/2;
//cout<<"l: "<<l1<<' '<<l2<<endl;
for (int i=0; i<lim; ++i) {
for (int j=1; j<=n; ++j)
if (dfs(1, j, l1, i>>l2))
for (int k=1; k<=n; ++k)
if (dfs(j, k, l2, i&((1<<l2)-1))) {
++ans;
//cout<<"++ans: "<<i<<endl;
goto jump;
}
jump: ;
}
printf("%dn", ans);
exit(0);
}
}

signed main()
{
#ifdef DEBUG
freopen("1.in", "r", stdin);
#endif
bool all_zero=1, all_one=1;

for (int i=1,u,v,c; i<=m; ++i) {
if (c) dis1[u][v]=dis1[v][u]=1;
else dis0[u][v]=dis0[v][u]=1;
if (c) edge1[u]=edge1[v]=1;
else edge0[u]=edge0[v]=1;
if (c) all_zero=0;
else all_one=0;
}
for (int i=1; i<=n; ++i) for (int j=i; j<=n; ++j) if (dis1[i][j]) add(i, j, 1), add(j, i, 1);
for (int i=1; i<=n; ++i) for (int j=i; j<=n; ++j) if (dis0[i][j]) add(i, j, 0), add(j, i, 0);