首先可以想到,如果整張圖裡面有一個可以走遍所有點的圈的話,那麼只要把邊定向成繞一圈的,就可以達到最大值 n^2 了。因此由這件事可以想到,考慮這張圖的邊雙連通分量,那麼可以先把每個邊雙連通分量內部都先弄成一個強連通分量,把他們都先整個縮起來,這樣就可以得到一棵帶權的樹,所以之後只要處理樹的情況就可以了。
接下來我猜測了一件事,但我證不太出來他為什麼是對的,就是在最佳解中,如果沿著任意一條樹上的路徑走的話,路上經過的邊的方向至多只會改變一次,或是說不存在點列 A_1 , A_2 , ... , A_k ,滿足 A_1 -> A_2 , A_( k-1 ) -> A_k ,且 A_( i+1 ) -> A_i ,其中 2 <= i <= k - 2 (X -> Y 代表有一條有向邊從 X 連向 Y)。而由這件事就可以推到用來解決這個問題的關鍵性質;存在一個點 X ,使得對於其他的所有點 Y ,X 到 Y 路徑上的所有邊要嘛全部指向 X ,要嘛全部指向 Y (證明補在最後面)。因此考慮枚舉每個點當作 X ,記他的子樹們為 T_1 ~ T_k ,還有其大小分別為 S_1 ~ S_k ,那麼不管 T_i 內部的所有邊是全部都指向 X 的還是全部都指 X 的反方向的,他內部的「可以從 A 走到 B 的 ( A , B ) 點對數」都是固定的了,因此可以先算出來。還有要加上 X 可以走到其他所有的點。最後要決定的東西是形如 A 在 T_i 裡,B 在 T_j 裡( i != j ),且 A 可以走到 B 的 ( A , B ) 點對數,也就是我們要決定每個 T_i 的類型。不妨設 T_1 ~ T_r 都是指向 X 的,而 T_( r+1 ) ~ T_k 都是指向 X 的反向的,那麼在這個部份所得到的點對數就會是 ( S_1 + ... + S_r ) * ( S_( r+1 ) + ... + S_k ) ,因為他們的和是固定的,而我們希望他們乘起來的值越大越好,所以我們必須要把 S_1 ~ S_k 分成總和最接近的兩堆,而這就是經典的可以用 DP 解的問題了。
最後補上我猜測的那個性質和另外一個性質的等價證明。首先從右推到左是顯然的,所以只需處理從左推到右的情形,也就是接下來要證明「一條路徑上至多改變一次方向」可以推到「存在一個點 X 滿足那件事」。隨便取一個點 P,如果他已經滿足 X 的條件的話那就證完了,因此我們可以假設存在兩個點 A 和 B ,使得 P 走到 A 的路上的邊都是指向 A 的,且 B -> A (反過來的話不影響證明)。此時如果有另一個點 C 使得 C->A ,那麼 C 所在的不包含 A 的那一整個子樹裡的邊的方向就都確定了,全部都會是指往 C 的方向,否則就會違反先前假設的性質。再考慮其他由 A 指出去的邊,如果這時候找不到另一個點 D ,使得 A 走到 D 的路徑上全部都是指向 D 的邊,但存在另一個點 E 使得 E->D ,那麼取 A 為 X 就證完了。否則新找到的 D 和 E 的地位就等同於剛才的 A 和 B ,因此可以一直重複這樣的過程下去。但這個過程不可能進行無限次,否則整棵樹的大小為無限大,矛盾。因此總有一天會停下來,也就是我們一定找的到滿足那個條件的 X 。
對了,官方解裡面是直接寫了那個我等價之後的性質,然後說很多人都猜這件事是對的,也沒證明為什麼,就只有說這是一個 magic XDDD
code :
#include<bits/stdc++.h> using namespace std; const int maxn=2000+10 ; vector<int> v0[maxn],v[maxn] ; int lev[maxn],bcc[maxn],w[maxn],bcnt=0 ; stack<int> st ; int dfs(int x,int f,int l) { int low ; low=lev[x]=l ; st.push(x) ; for(auto i : v0[x]) if(i!=f) { if(lev[i]!=-1) {low=min(low,lev[i]) ; continue ;} int tmp=dfs(i,x,l+1) ; low=min(low,tmp) ; if(tmp>l) { bcnt++ ; while(1) { int top=st.top() ; st.pop() ; bcc[top]=bcnt ; w[bcnt]++ ; if(top==i) break ; } } } if(x==1) { bcnt++ ; while(!st.empty()) bcc[st.top()]=bcnt , w[bcnt]++ , st.pop() ; } return low ; } int n ; void find_BCC() { memset(lev,-1,sizeof(lev)) ; dfs(1,-1,0) ; for(int i=1;i<=n;i++) for(auto j : v0[i]) if(bcc[i]!=bcc[j]) v[bcc[i]].push_back(bcc[j]) ; } int ans ; int dfs2(int x,int f,int s) { int ret=w[x] ; ans+=s*w[x] ; for(auto i : v[x]) if(f!=i) ret+=dfs2(i,x,s+w[i]) ; return ret ; } int tmp[maxn] ; bool dp[maxn] ; main() { int m ; scanf("%d%d",&n,&m) ; while(m--) { int x,y ; scanf("%d%d",&x,&y) ; v0[x].push_back(y) ; v0[y].push_back(x) ; } find_BCC() ; int sum=n ; n=bcnt ; int ANS=0 ; for(int i=1;i<=n;i++) { ans=w[i]*sum ; fill(dp,dp+sum-w[i]+1,0) ; dp[0]=1 ; for(auto j : v[i]) { int x=dfs2(j,i,w[j]) ; for(int k=sum-w[i];k>=x;k--) if(dp[k-x]) dp[k]=1 ; } int x=(sum-w[i])/2 ; while(!dp[x]) x-- ; ans+=x*(sum-w[i]-x) ; ANS=max(ANS,ans) ; } printf("%d\n",ANS) ; }
沒有留言:
張貼留言