Billchenchina 标签 联系 友链

HDU 3001 Travelling

Posted by Billchenchina on September 18, 2017
标签: 题解 HDOJ

题意是给你一个图,每个节点最多走两次,求将图联通的最小路径的总长度值。

传送门

怎么做?

每个节点最多走两次,那么可以化成“三进制”。

“三进制?三进制电脑怎么表示?”

不说话,看代码

// pow3[i] 代表3^i
int pow3[11];

// inch3[i][j] 代表数字 i 在三进制表示下的第 j 位是几
int inch3[60000][11];

void init()
{
    pow3[0]=1;
    for(int i=1;i<11;++i)
    {
    	// 递推求幂
        pow3[i]=pow3[i-1]*3;
    }
    for(int i=0;i<pow3[10];++i)
    {
    	// 模拟求三进制
        int k=i;
        int pos=0;
        while(k)
        {
            inch3[i][pos]=k%3;
            k/=3;
            pos++;
        }
    }
}

然后呢?

枚举每种状态,进行动态规划。这 TM 好像 Flyod

for(int i=0;i<pow3[n];++i)
{
	bool have_not_visited=0;
	for(int j=0;j<n;++j)
	{
		if(inch3[i][j]==0)
		{
			have_not_visited=1;
        }
        if(dp_map[i][j]!=INT_MAX)
        {
        	for(int k=0;k<n;++k)
        	{
        		if(mapn[j][k]!=INT_MAX&&inch3[i][k]!=2)
        		{
        			dp_map[i+pow3[k]][k]=min(dp_map[i+pow3[k]][k],dp_map[i][j]+mapn[j][k]);
        		}
        	}
        }
    }

然后就 A 了