╰(￣▽￣)╭
Description
故事發生在1486 年的意大利，Ezio 原本只是一個文藝復興時期的貴族，后來因為家族成員受到圣殿騎士的殺害，決心成為一名刺客。最終，憑借著他的努力和出眾的天賦，成為了杰出的刺客大師，他不僅是個身手敏捷的武林高手，飛檐走壁擅長各種暗殺術。刺客組織在他的帶領下，為被剝削的平民聲張正義，趕跑了原本統治意大利的圣殿騎士首領-教皇亞歷山大六世。在他的一生中，經歷了無數次驚心動魄、扣人心弦的探險和刺殺。
曾經有一次，為了尋找Altair 留下的線索和裝備，Ezio 在佛羅倫薩中的刺客墓穴進行探索。這個刺客墓穴中有許多密室，且任何兩個密室之間只存在一條唯一的路徑。這些密室里都有一個刺客標記，他可以啟動或者關閉該刺客標記。為了打開儲存著線索和裝備的儲藏室，Ezio 必須操作刺客標記來揭開古老的封印。要想解開這個封印，他需要通過改變某些刺客標記的啟動情況，使得所有刺客標記與封印密碼“看起來一樣”。
在這里，“看起來一樣”的定義是：存在一種“標記”密室與“密碼”密室之間一一對應的關系，使得密室間的連接情況和啟動情況相同（提示中有更詳細解釋）。幸運的是，在Ezio 來到刺客墓穴之前，在Da Vinci 的幫助下，Ezio 已經得知了打開儲藏室所需要的密碼。
而你的任務則是幫助Ezio 找出達成目標所需要最少的改動標記次數。
對于100%的數據，n<=700，且每個密室至多與11個密室相通。
第一行給出一個整數n，表示密室的個數。 第二行至第n 行，每行給出兩個整數a 和b，表示第a 個密室和第b 個密室之間存在一條通道。 第n+1 行，給出n 個整數，分別表示當時每個密室的啟動情況（0 表示關閉，1 表示啟動）。 第n+2 行，給出n 個整數，分別表示密碼中每個密室的啟動情況。
Output
輸出只有一行，即輸出最少改動標記次數。
4 1 2 2 3 3 4 0 0 1 1 1 0 0 0
Sample Output
1
樣例解釋
密室的編號是可以變的！將第三個密室關閉后，在當前標記和密碼之間，存在1->4,2->3,3->2,4->1 的對應關系，重新編號后連接情況沒有改變，且標記與密碼對應。對于更一般的情況，存在一個1 到n 的置換P，使得對于任意密室之間的道路u-v，都一定有密碼密室中的道路P(u)-P(v)；如果不存在密室之間的道路u-v，則一定沒有密碼密室中的道路P(u)-P(v)。
(⊙ ▽ ⊙)
簡化題意
給出一棵樹，找出另一棵同構的樹，使得結點權值差異最小。
做法
先把無根樹轉化為有根樹，關鍵就在于我們如何選擇根： 首先我們選重心做為樹的根，如果重心在邊上，就新建一個結點。 選了重心作為根的好處是： 同構的子樹之間可以互相調換。
如何判斷兩棵子樹同構呢？先給每個結點及其兒子構成的子樹預處理出hash值。深度相同并且hash值也相同的兩個結點所構成的子樹就是同構的兩棵子樹。hash值可以利用double hash現在先對所有結點按其深度從大到小排序，hash值為第二關鍵字排序。 設f[i][j]表示結點i與結點j調換的最小費用， 前面說過，只有同構并且深度相同的子樹才能調換。 通過這個條件，并且利用排序后的序列，可以簡單地進行轉移。
那么轉移方程怎么寫呢？即f[i][j]=? 由于f[son(i)][]已經求出來了，因為son(i)的深度比i大， 那么通過i和j的兒子相互調換，從而達到最小值，使我們的目的。 實際上，這個過程是帶費用的二分圖匹配， 可以利用最小費用最大流或者KM算法完成這個過程，設答案為flow。 那么f[i][j]=flow+(a[i] xor b[j])，其中a,b是輸入中的兩組權值。
由于每個密室至多與11 個密室相通， 所以時間復雜度不會太大。
(￣～￣)
#include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<string.h>#define ll long long#define p1(x) (x+1)#define p2(x) (x+tmd+1)using namespace std;const char* fin="ex3296.in";const char* fout="ex3296.out";const int inf=0x7fffffff;const int maxn=707,maxm=maxn*20,maxN=370,maxM=maxN*2,maxh=99997,maxH=57494,hh=137,HH=97;int n,m,i,j,k,rt;int fi[maxn],ne[maxm],la[maxm],tot,A[maxn],B[maxn];int si[maxn],fa[maxn],ce[3],f[maxn][maxn];int w[maxn],W[maxn];struct node{ int de,h,H,id;}a[maxn];bool cmp(node a,node b){ return a.de>b.de || (a.de==b.de && a.h<b.h) || (a.de==b.de && a.h==b.h && a.H<b.H);}struct network{ int fi[maxN],ne[maxM],la[maxM],va[maxM],co[maxM],tot,num,last[maxN],Last[maxN]; int b[maxN*10],f[maxN],head,tail; bool bz[maxN]; void init(int v){ tot=1; memset(fi,0,sizeof(fi)); num=v; } void add_line(int a,int b,int c,int d){ tot++; ne[tot]=fi[a]; la[tot]=b; va[tot]=c; co[tot]=d; fi[a]=tot; } void add(int a,int b,int c,int d){ add_line(a,b,c,d); add_line(b,a,0,-d); } void add(int v,int dis){ f[v]=dis; if (!bz[v]){ b[++tail]=v; bz[v]=true; } } int spfa(){ int i,j,k,cost=0; head=tail=0; memset(bz,0,sizeof(bz)); memset(f,127,sizeof(f)); add(1,0); while (head++<tail){ for (k=fi[b[head]];k;k=ne[k]) if (va[k] && f[b[head]]+co[k]<f[la[k]]){ Last[la[k]]=k; last[la[k]]=b[head]; add(la[k],f[b[head]]+co[k]); } bz[b[head]]=false; } if (f[num]>2000000000) return -1; for (k=num;k!=1;k=last[k]){ va[Last[k]]--; va[Last[k]^1]++; cost+=co[Last[k]]; } return cost; } int flow(){ int j,k=0; while (1){ j=spfa(); if (j==-1) break; else k+=j; } return k; }}N;void add_line(int a,int b){ tot++; ne[tot]=fi[a]; la[tot]=b; fi[a]=tot;}void dfs(int v,int from){ int i=1,j,k; fa[v]=from; si[v]=1; for (k=fi[v];k;k=ne[k]) if (la[k]!=from){ dfs(la[k],v); si[v]+=si[la[k]]; i&=si[la[k]]<=n/2; } if (i && (n-si[v])<=n/2) ce[++ce[0]]=v;}int t[maxn],T[maxn];void geth(int v,int from){ int i,j,k; fa[v]=from; si[v]=0; a[v].id=v; a[v].de=a[from].de+1; for (k=fi[v];k;k=ne[k]) if (la[k]!=from){ geth(la[k],v); si[v]++; } t[0]=T[0]=0; for (k=fi[v];k;k=ne[k]) if (la[k]!=from) t[++t[0]]=a[la[k]].h,T[++T[0]]=a[la[k]].H; if (!t[0]){ a[v].h=23; a[v].H=89; return ; } sort(t+1,t+t[0]+1),sort(T+1,T+T[0]+1); for (i=1;i<=t[0];i++){ a[v].h=(a[v].h*hh+t[i]*(hh^11))%maxh; a[v].H=(a[v].H*HH+T[i]*(HH^29))%maxH; }}int main(){ scanf("%d",&n); for (i=1;i<n;i++){ scanf("%d%d",&A[i],&B[i]); add_line(A[i],B[i]); add_line(B[i],A[i]); } for (i=1;i<=n;i++) scanf("%d",&w[i]); for (i=1;i<=n;i++) scanf("%d",&W[i]); dfs(1,0); if (ce[0]>1){ memset(fi,0,sizeof(fi)); tot=0; for (i=1;i<n;i++){ if (!(A[i]==ce[1] && B[i]==ce[2] || A[i]==ce[2] && B[i]==ce[1])){ add_line(A[i],B[i]); add_line(B[i],A[i]); } } n++; add_line(n,ce[1]); add_line(ce[1],n); add_line(n,ce[2]); add_line(ce[2],n); rt=n; }else rt=ce[1]; geth(rt,0); sort(a+1,a+n+1,cmp); j=1; memset(f,255,sizeof(f)); for (i=2;i<=n+1;i++) if (i==n+1 || a[i].de!=a[i-1].de || a[i].h!=a[i-1].h || a[i].H!=a[i-1].H){ int tmp=j; for (;j<i;j++) for (k=tmp;k<i;k++){ N.init(si[a[j].id]+si[a[k].id]+2); int l,o,L,O,tmd=si[a[j].id]; for (l=fi[a[j].id],L=1;l;l=ne[l]) if (la[l]!=fa[a[j].id]){ for (o=fi[a[k].id],O=1;o;o=ne[o]) if (la[o]!=fa[a[k].id]){ if (f[la[l]][la[o]]!=-1) N.add(p1(L),p2(O),1,f[la[l]][la[o]]); O++; } L++; } for (l=fi[a[j].id],L=1;l;l=ne[l]) if (la[l]!=fa[a[j].id]) { N.add(1,p1(L),1,0); L++; } for (o=fi[a[k].id],O=1;o;o=ne[o]) if (la[o]!=fa[a[k].id]){ N.add(p2(O),N.num,1,0); O++; } f[a[j].id][a[k].id]= N.flow()+ (w[a[j].id]^W[a[k].id]); (⊙v⊙)Key Points 1.hash的計算 新加的常數項要乘個系數。
