哈密顿图的利用

题目链接

对于题意我是真的理解错了。难受，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)种答案。

#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;
}

最后

以上就是花痴信封为你收集整理的哈密顿图的利用的全部内容，希望文章能够帮你解决哈密顿图的利用所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。