首页 > ACM题库 > HDU-杭电 > HDU 3538-A sample Hamilton path[解题报告]HOJ
2014
11-05

HDU 3538-A sample Hamilton path[解题报告]HOJ

A sample Hamilton path

问题描述 :

Give you a Graph,you have to start at the city with ID zero.

输入:

The first line is n(1<=n<=21) m(0<=m<=3)
The next n line show you the graph, each line has n integers.
The jth integers means the length to city j.if the number is -1 means there is no way. If i==j the number must be -1.You can assume that the length will not larger than 10000
Next m lines,each line has two integers a,b (0<=a,b<n) means the path must visit city a first.
The input end with EOF.

输出:

The first line is n(1<=n<=21) m(0<=m<=3)
The next n line show you the graph, each line has n integers.
The jth integers means the length to city j.if the number is -1 means there is no way. If i==j the number must be -1.You can assume that the length will not larger than 10000
Next m lines,each line has two integers a,b (0<=a,b<n) means the path must visit city a first.
The input end with EOF.

样例输入:

3 0
-1 2 4
-1 -1 2
1 3 -1
4 3
-1 2 -1 1
2 -1 2 1
4 3 -1 1
3 2 3 -1
1 3
0 1
2 3

样例输出:

4
5

Hint
I think that all of you know that a!=b and b!=0 =。=

#include<stdio.h>
#include<string.h>
const int INFI=999999999;

int pre[30][10],pow[30];
int map[30][30];
int f[1<<20][21];
int n,m;

bool check(int s,int v)
{
	for (int i=1;i<=pre[v][0];i++)
	if ( (s&pow[pre[v][i]])==0 ) 
		return 0;
	return 1;
}

int main()
{
	int a,b;
	
	for (int i=0;i<22;i++) pow[i] = 1<<i;
	
	while ( scanf("%d%d",&n,&m)!=EOF )
	{
		for (int i=0;i<n;i++)
			for (int j=0;j<n;j++)
				scanf("%d",&map[i][j]);
		
		memset(pre,0,sizeof(pre));
		for (int i=1;i<=m;i++)
		{
			scanf("%d%d",&a,&b);
			pre[b][ ++pre[b][0] ]=a;
		}
		int maxs = (1<<n)-1;
		for (int s=0;s<=maxs;s++)
		for (int i=0;i<n;i++) 
			f[s][i]=INFI;
			
		f[1][0]=0;
		
		for (int s=1;s<=maxs;s++)
		for (int i=0;i<n;i++)
		if ( (s & pow[i])>0 && f[s][i]<INFI )
		{
			for (int j=1;j<n;j++)
			if ( map[i][j]!=-1 && (s&pow[j])==0 && check(s,j) )
			{
				if ( f[s][i]+map[i][j] < f[ s+pow[j] ][j] )
				{
					f[s+pow[j]][j] = f[s][i]+map[i][j];
					//printf("updata[%d][%d] is %d\n",s+pow[j],j,f[s+pow[j]][j]);
				}
			}	
			//printf("f[%d][%d] is %d\n",s,i,f[s][i]);
		}
				
		int ans=INFI;
		for (int i=0;i<n;i++)
		if ( f[maxs][i]<ans )
			ans=f[maxs][i];
		if ( ans==INFI )
			printf("-1\n");
		else
			printf("%d\n",ans);
	}
}

  1. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count