哈密顿图的利用

81 阅读 0 评论 54 点赞

我是靠谱客的博主花痴信封，这篇文章主要介绍哈密顿图的利用，现在分享给大家，希望可以做个参考。

题目链接

对于题意我是真的理解错了。难受，wa无数发

题意：其实是任意两个人都有鄙视关系，你鄙视我或者我鄙视你，就是n个点一个完全图，每条边带方向。

求最长链分别是1～n是的个数。

官方题解是说可以证明不论怎么画最长链都是n（都存在哈密顿路径），所以不是n的长度答案都是0只有n的时候

有答案，需要计算。这要怎么证明呢？

反正法，假设不能。

下面点用数字表示。

当只有一个点的时候，自己一个，有哈密顿路径。加上一个点，要么这个点指向起点，让自己变成起点，要不

自己被指向，作为终点，显然都成立。

1->2

2->1

当再加入一个点3时，3对起点，终点都有两种方向选择，如果指向起点，马上得到一条哈密顿路径，所以只能起点指

向新加入点，这时如果指向终点，那1->3->2就是一条哈密顿路径，如果终点指向它，3就是新的终点，1->2->3是新

的哈密顿路径。所以3个点怎么指都有一条哈密顿路径。

再加入一个新点，如上所说，不能指向起点，不能被终点指向，否则马上就有一条哈密顿路径。

那就是起点指向它，它指向终点。那起点的下一个点（下图点2），如果指向点4，有哈密顿路径，如果4指向2

还是有。在加一个点也是一样的。所以证明一直存在。

1->2->3

v ^

4 -> |

总条数可以这样想：每个点跟其他点都有连线，n*(n-1)，但有重复，再除2，共有n*(n-1)/2条线，每条线有一个方向，

一条线可以两个方向任选一个，每条线互不影响，乘法原理，所以有2^(n*(n-1)/2)种答案。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<string>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<n;i++)
printf("0n");
printf("%dn",1<<((n-1)*n/2));
}
return 0;
}