#15017: 主體思路


dimitryl (dimitryl)

School : 湖南省长沙市第一中学
ID : 83046
IP address : [183.215.79.234]
Last Login :
2018-12-28 21:30:43
d998. WC2011 1.最大XOR和路径 -- WC2011第一题 | From: [183.215.79.234] | Post Date : 2018-08-31 22:20

考慮到對於壹條從1到n的路徑壹定是由壹條從1到n的簡單路徑加上若幹個環組成,所以可以預處理處圖中的環(不壹定要將所有環處理,因為兩個相交的小環異或起來可以替代這兩個環合起來的大環),可以利用圖上的dfs樹在O(n+m)
的時間處理

將所有的環的權值異或和放進線性基裏
將從1到n的任意壹條路徑權值異或和作為初始值(因為若有另壹條更優的路徑,則這兩條路徑構成壹個環,而這個環已經在線性基裏了)
求這個初始值在這個線性基裏能取到的最大值

 
ZeroJudge Forum