2016年2月11日 星期四

[Codeforces 100365I][ASC 34]Tour

這題目不好找,附個題目連結

此題轉換成圖論模型就是,給你一棵樹,求最少要加幾條邊才有一條路徑,經過每個點恰好一次並回到原點?

仔細思考,可以發現,這題等價求這棵樹最少可以分解成多少條鏈
舉幾個例子,就會發現分解成幾條鏈,就是要多建幾條路,把這些鏈連接成一個經過每個點恰好一次的環

因此,要怎麼求一棵樹最少分解成幾條鏈呢?

可以考慮樹形$DP$
$DP_{0}[u]$代表以$u$為根結點的這棵子樹至少分解成幾條鏈
$DP_{1}[u]$代表「根結點為某條鏈的自由端」的情況下,以$u$為根結點的這棵子樹至少分解成幾條鏈

要計算$DP_{0}[u]$時,有以下三種情況,取最佳解即可:
要計算$DP_{1}[u]$時,有以下兩種情況,取最佳解即可:
如果圖解還是看不懂怎麼遞迴計算$DP_{0}[u]$和$DP_{1}[u]$,請留言問問題或參考code吧~

時間複雜度:$O(N\log N+M)$ (使用$O(1)$取前2小值的算法可以去掉那個$\log$)

p.s. 這題不是直接讀標準輸入輸出,要使用讀寫檔案的方式,所以code裡面的freopen不是忘記註解掉,請特別注意!第一次遇到不是標準輸入輸出的題目,莫名WA半天找不到bug...... Orz

code:
#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
using namespace std;
int N,DP[100000][2];
vector<int>ET[100000];
bool VIS[100000];
void Dfs(const int u,const int fa)
{
    assert(!VIS[u]);
    VIS[u]=true;
    DP[u][0]=DP[u][1]=0;
    vector<int>s;
    for(const int nxt:ET[u])if(nxt!=fa)
    {
        Dfs(nxt,u);
        s.push_back(DP[nxt][1]-DP[nxt][0]);
        DP[u][0]+=DP[nxt][0],DP[u][1]+=DP[nxt][0];
    }
    sort(s.begin(),s.end());
    if(s.empty())DP[u][0]++;
    else if((int)s.size()==1)DP[u][0]+=min(s[0]+1,1);
    else if((int)s.size()>=2)DP[u][0]+=min(min(s[0]+1,(s[0]+s[1])+1),1);
    else assert(0);
    if(!s.empty())DP[u][1]+=min(s[0],0);
}
int main()
{
    freopen("tour.in","r",stdin);
    freopen("tour.out","w",stdout);
    while(scanf("%d",&N)==1)
    {
        for(int i=0;i<N;i++)ET[i].clear(),VIS[i]=false;
        for(int i=0,a,b;i<N-1;i++)scanf("%d%d",&a,&b),a--,b--,ET[a].push_back(b),ET[b].push_back(a);
        Dfs(0,-1);
        for(int i=0;i<N;i++)assert(VIS[i]); 
        printf("%d\n",DP[0][0]);
        break;
    }
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原