poj 2404 floyd+状態圧縮(中国郵便配達員問題)

标题:定番中国郵便配達員問題.1つの連通図を指定すると、頂点の間にいくつかのエッジがあり、任意の点からすべてのエッジを遍歴し、各エッジに少なくとも1回アクセスし、起点に戻る必要があります.要求を満たすシナリオで歩いた距離の和の最小値を求める.
考え方(http://www.cnblogs.com/wuminye/archive/2013/05/06/3063902.html):
まず考えたのは、これがオーラ図であれば、必ず各エッジを通過することができ、一度しかないという案が最小(すべてのエッジ距離の和)に違いない.オーラ図でなければ連通図であるため,握手定理によれば偶数点の度は奇数である必要がある.1点から少なくとも1つの辺を歩くには、1つのオーラの戻り道を構成しなければならないので、いくつかの辺は何度も歩かなければならない.1回多く歩くたびに等価に1つの辺が接続されている.このようにオーラ図を構成し、元の辺と新しく追加された仮想辺はオーラ図の中にあり、1回しか通らない.今は距離の和を最短にしなければならない.元のエッジの距離の和は固定されており、結果を最小限に抑えるには、新しく追加した仮想エッジの和を最小限に抑えるしかありません.解析により,オーラ図を構成するには,追加した仮想エッジの2つの端点の元の度数が奇数であるに違いないが,そのうち偶数度の点があれば,追加しながら度数が奇数になり,オーラ図になるか,あるいはこれ以上の一挙手一投足になることは不可能であることが分かった.そこで現在の問題は,偶数個の奇度頂点のうち2個の連線をどのようにして,これらの連線の距離の和を最小にするかであり,2個の頂点の連線長はこの2点間の最短距離(欲張り)であるべきであると考えやすい.この問題を解決するには,最適マッチングアルゴリズムを用いてもよいし,動的プランニングを用いてもよい.ここではダイナミックプランニングの方法を使用します.状態表示:一連のバイナリ数で、i番目のビット数はi番目の点が奇度点であるかどうかを表し、0はいいえ、1ははいを表す.例えば、0010101は、1、3、5、6点の度数が奇数であることを示す.各ステータスは1つのフェーズに分割されます.フェーズステータス遷移:各ステータスは、現在のステータスから任意に2つの1を0にするステータス遷移、すなわち、1つのエッジを削除して現在のステータスにするステータス遷移から遷移することができる.例えば、0010101は、6つの状態から遷移することができる:000001、0011000、00010001、00100001、00010100、00100100無後効果:現在の状態が前の遷移経路を介して遷移した場合、その後の遷移の状態が遷移できないことはない.例えば、現在は0010101であり、以前にどのように移行しても、その後は必ず0011111の最適サブ構造に移行することができる:現在の状態が格納されている値は現在の状態の場合に必要とされる最小距離であり、この値の移行方程式は、f[cur]=min{f[pre]+dis[pre][cur]}(要求:pre状態はcur状態に移行することができ、dis[pre][cur]は削除された仮想エッジの距離である

#include 
#include 
#define INF 0x3fffffff
#define min(a,b) ((a)=1;i--){
			a <<= 1;
			if(d[i]&1)
				a++;
		}
		sum += test(a);
		printf("%d
",sum);
	}
	return 0;
}