2015年4月30日 星期四

[CF 475E] Strongly Connected City 2

作法:

首先可以想到,如果整張圖裡面有一個可以走遍所有點的圈的話,那麼只要把邊定向成繞一圈的,就可以達到最大值 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) ;
}
 

沒有留言:

張貼留言