最大xor和路徑解題報(bào)告

XORXOR（異或）是一種二元邏輯運(yùn)算，當(dāng)A和B不相等時為真，反之為位進(jìn)行XOR運(yùn)算。譬如12XOR9=(1100)2XOR(1001)2=(101)2=5.考慮一個邊權(quán)為非負(fù)整數(shù)的無向連通圖，節(jié)點(diǎn)為1~N，試求出一條從1號節(jié)點(diǎn)到N號節(jié)點(diǎn)的路徑，使得路徑上經(jīng)過的邊的權(quán)值的XOR和最大512353436路徑12435245對應(yīng)的XOR2XOR1XOR2XOR4XOR1XOR1XOR3=當(dāng)然，一條邊數(shù)更少的路徑135對應(yīng)的XOR和也是2XOR4對于20%N100,M1000,Di

對于100%N50000,M100000,Di定的從起點(diǎn)到終點(diǎn)的路徑P，加到原來的路徑上面，會形成一個環(huán)C，這樣所有點(diǎn)的度都是偶數(shù)?，F(xiàn)在對于每條邊設(shè)立一個變量i，如果這條邊在環(huán)C中出現(xiàn)了奇數(shù)次，則變量值為1，否則為.這樣對于每個點(diǎn)，由于它的度為偶數(shù)，故與它關(guān)聯(lián)的出現(xiàn)奇數(shù)次的邊有偶數(shù)個，于是與該點(diǎn)關(guān)聯(lián)的邊的i的OR和為0（*）.而一旦滿足每個點(diǎn)的度都是偶數(shù)，就一定能拆成若干個環(huán)，這樣就容易構(gòu)造出路徑來，因?yàn)閷τ诿總€環(huán)，都可以任選一點(diǎn)v，和點(diǎn)1之間連一條路徑，然后我從1到v，再從v到v把環(huán)遍歷一遍，然后再從v到1走與從1到v同一條路徑，這樣實(shí)際上就OR上了環(huán)上的邊，以此類推并上所有的環(huán)，最后再走路徑P到點(diǎn)N即可。所以（*）是充要的。不難建立關(guān)于點(diǎn)的度數(shù)奇偶的方程，共N個，然后從到低位枚舉答案，首先把最上的數(shù)設(shè)成1，然后加入一個新的方程，如果最后不產(chǎn)生1這種方程，那么這位就可以是1，否則只能是0；接著再考慮下一位，以此類推 有M個變量，一開始有N個方程，后來增加換一種思路，取原圖的一棵fs樹，則對于不在樹中的邊，其兩端點(diǎn)在樹中的路徑加上這條邊會形成一個環(huán)，共得到MN1個基本環(huán)；可以歸納證明圖中任意一個環(huán)的OR和都等于若干個基本環(huán)的OR和。則圖中任意一條路徑的XOR和都等于若干基本環(huán)的OR和與1到N的路徑P的X和的異或。此時的變量有-N1個，一開始沒有方程，同理從