【HDU 5305】Friends 多校第二场（双向DFS）

分类：DFS、DFS暴力

根据题意的话最多32条边，，直接暴力的话 2 ^ 32肯定超时了，我们可以分两次搜索时间复杂度减少为 2 * 2 ^ 16

唯一需要注意的就是对目前状态的哈希处理，

我采用的是十进制表示法

跑的还是比较快的，可能是用STL函数的原因增加了一些常数复杂度。

#include<map>#include<vector>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;typedef pair<int,int> pill;const int maxn = 55;struct Edge{int a,b;}edge[maxn];int n,m;LL cnt,base[15];int _count[15];map<pill,int>vis;void init(){base[1] = 1;for(int i = 2; i < 10; i++)base[i] = base[i – 1] * 10;}void calc(int state1,int state2,int &a,int &b){int base = 1;for(int i = 1; i <= n; i++){int d1 = state1 % 10, d2 = state2 % 10;int v1 = _count[i] – d1, v2 = _count[i] – d2;a += base * v1;b += base * v2;base *= 10;state1 /= 10;state2 /= 10;}}void dfs1(int now,int finish,int state1,int state2){if(now == finish){vis[make_pair(state1,state2)] ++;return;}int a = edge[now].a, b = edge[now].b;dfs1(now + 1,finish,state1 + base[a] + base[b],state2);dfs1(now + 1,finish,state1,state2 + base[a] + base[b]);}void dfs2(int now,int finish,int state1,int state2){if(now == finish){int x = 0,y = 0;calc(state1,state2,x,y);if(x >= 0 && y >= 0)cnt += vis[make_pair(x,y)];return;}int a = edge[now].a, b = edge[now].b;dfs2(now + 1,finish,state1 + base[a] + base[b],state2);dfs2(now + 1,finish,state1,state2 + base[a] + base[b]);}int main(){int T;init();scanf("%d",&T);while(T–){vis.clear();memset(_count,0,sizeof(_count));scanf("%d%d",&n,&m);for(int i = 0; i < m; i++){scanf("%d%d",&edge[i].a,&edge[i].b);_count[edge[i].a] ++;_count[edge[i].b] ++;}int ok = 1;for(int i = 1; i <= n; i++){if(_count[i] % 2 != 0){ok = 0;break;}_count[i] /= 2;}cnt = 0;if(ok){dfs1(0,m / 2,0,0);dfs2(m / 2,m,0,0);}printf("%d\n",cnt);}return 0;}

上一篇Linux远程登陆以及免密码登陆下一篇【HDU 5312】Sequence（数学问题）

顶0踩0

宁愿停歇在你门前的那棵树上，看着你，守护你。

相关文章：

你感兴趣的文章：

标签云：