轉站通知

本站已停止更新!!想繼續收看我的新文章的話,請前往我的新Blog - Chino's

2015年3月18日 星期三

IOI::HOJ-288::TIOJ-1838::作夢中 Dreaming

http://tioj.ck.tp.edu.tw/problems/1838
IOI 2013。



這題WA了好幾次QQ。
題目是你有一堆樹,還有一堆長度是L的邊,你要把這些樹連結成一棵,並且讓最遠的兩個點最近,求他們之間的距離。

先觀察一下題目,會發現最遠的兩個點的距離就是最長鍊的長度。最長鍊可以透過先亂DFS到最遠的點再從那個點DFS到最遠的點,這兩個點之間的鍊就是最長鍊。
不太嚴謹的證明:第一次DFS,起點可能不在最長鍊上,但是最遠的點一定是最長鍊的端點,不然你一定可以找到一條鍊比最長鍊更長,但那是矛盾的。然後從端點DFS最遠點也一定是另外一個端點。

所以,答案有可能是那堆樹裡的最長鍊,不然,就是把這些樹接起來之後的最長鍊

找最長鍊時,順便找每棵樹的「圓心」(以這個點當根,最深的子樹最淺),利用他找出「半徑」(以圓心當根,最深的子樹的深度),用題目給的L長度的邊把他們接在一起(把圓心接在一起最好),然後我們就可以發現,最好的接法就是把所有的樹接到半徑最長的樹上

於是最長鍊除了在樹裡之外,還有可能是最長半徑跟次長半徑加上一條L邊,不然就是次長半徑的樹和第3長半徑加上兩條L邊(全部都接到最長半徑樹上,如果L很長就會是第2種狀況。)不用考慮其他狀況,因為都不會比這幾種狀況長。

找半徑要好好思考,只要差一點就WA了XDD。


#include <cstdio>
#include <vector>
#include <cstring>
#define F(n) Fi(i,n)
#define Fi(i,n) for(int i=0;i<n;i++)
#define N 100010
using namespace std;
struct MP{
    int t,c;
}F[N];
int ans,ST[5];
bool wed[N];
bool gin(int &a){
    char c;
    while(c=getchar(),c<'0'||c>'9')if(c==-1)return 0;
    a=c-'0';
    while(c=getchar(),c>='0'&&c<='9')a=a*10+c-'0';
    return 1;
}
MP DFS(vector<MP>*G,int now,int no){
    wed[now]=1;
    MP drv=(MP){now,0};
    F[now]=drv;
    for(MP p:G[now])if(p.t!=no){
        MP tmp=DFS(G,p.t,now);
        tmp.c+=p.c;
        if(tmp.c>drv.c)drv=tmp,F[now]=p;
    }
    return drv;
}
int main(){
    int n,m,l,a,b,c;
    // while(~scanf("%d%d%d",&n,&m,&l)){
    while(gin(n),gin(m),gin(l)){
        vector<MP>G[N];
        ans=0;
        memset(ST,0,sizeof(ST));
        memset(wed,0,sizeof(wed));
        F(m){
            // scanf("%d%d%d",&a,&b,&c);
            gin(a);gin(b);gin(c);
            G[a].push_back((MP){b,c});
            G[b].push_back((MP){a,c});
        }
        F(n)if(!wed[i]){
            int str=DFS(G,i,-1).t;
            int tmp=DFS(G,str,-1).c;
            ans=max(tmp,ans);
            int sum=0,st=3;
            if(tmp)while(sum+F[str].c<=tmp/2)sum+=F[str].c,str=F[str].t;
            tmp=min(sum+F[str].c,tmp-sum);
            while(st&&tmp>ST[st-1])ST[st]=ST[st-1],st--;
            ST[st]=tmp;
        }
        if(n-m>2)ans=max(ans,max(ST[0]+l+ST[1],ST[1]+ST[2]+l*2));
        else if(n-m>1)ans=max(ans,ST[0]+l+ST[1]);
        printf("%d\n",ans);
    }
}