查看: 684|回復: 2

[解決] toj 144

[複製鏈接]
  • TA的每日心情
    開心
    2015-4-12 10:09
  • 簽到天數: 137 天

    [LV.7]常住居民III

    142

    主題

    686

    帖子

    3559

    積分

    邁向天堂

    蘇多門

    Rank: 8Rank: 8

    積分
    3559

    新手達陣台南一中資訊社程式設計達人 - 2014

    發表於 2014-9-26 22:12:15 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    x
    本帖最後由 domen111 於 2014-10-5 12:29 編輯

    為什麼第一筆測資就是會WA啊?

    [C++] 純文本查看 復制代碼
    #include<iostream>
    #include<cstring>
    #include<vector>
    using namespace std;
    vector<int> g[100010];
    int dis[100010];
    int dfs(int s)
    {
        memset(dis,-1,sizeof dis);
        vector<int> stk;
        stk.push_back(s);
        dis[s]=0;
        int farthest=s;
        while(!stk.empty())
        {
            int now=stk.back();
            stk.pop_back();
            for(int i=0;i<g[now].size();i++)
                if(dis[g[now][i]]==-1)
                {
                    dis[g[now][i]]=dis[now]+1;
                    stk.push_back(g[now][i]);
                    if(dis[g[now][i]]>dis[farthest])
                        farthest=g[now][i];
                }
        }
        return farthest;
    }
    int main()
    {
        ios::sync_with_stdio(0);
        int n,m;
        while(cin>>n>>m)
        {
            for(int i=0;i<n;i++)
                g[i].clear();
            for(int i=0;i<m;i++)
            {
                int a,b;
                cin>>a>>b;
                g[a].push_back(b);
                g[b].push_back(a);
    }
            int a=dfs(0);
            int b=dfs(a);
            cout<<dis[b]<<endl;
        }
    }
    

    蘇多門 domen111
    My Web: https://sites.google.com/site/domenprg/
    回復

    使用道具 檢舉

  • TA的每日心情
    慵懶
    2015-4-10 14:18
  • 簽到天數: 78 天

    [LV.6]常住居民II

    176

    主題

    612

    帖子

    3959

    積分

    管理員

    Rank: 9Rank: 9Rank: 9

    積分
    3959

    台南一中資訊社新手達陣程式設計達人 - 2014

    發表於 2014-9-26 23:09:10 | 顯示全部樓層
    只有一筆測資,多讀會讀到怪怪的東西歐
    回復 支持 反對

    使用道具 檢舉

  • TA的每日心情
    開心
    2017-8-20 13:10
  • 簽到天數: 319 天

    [LV.8]以壇為家I

    194

    主題

    363

    帖子

    1589

    積分

    金牌會員

    Rank: 6Rank: 6

    積分
    1589

    台南一中資訊社新手達陣

    發表於 2014-10-5 09:48:14 | 顯示全部樓層
    那如果第一筆RE勒==
    [C++] 純文本查看 復制代碼
    #include <cstdio> //c¿é¤J¿é¥X
    #include <iostream>
    using namespace std;
    struct V{
        int a;
        int b;
        bool x;
    };
    V v1[100001],v2[100001];
    int main(){
    	int n,m;
        while(~scanf("%d",&n)){
        	scanf("%d",&m);
        	for(int q=0;q<m;q++){
                scanf("%d%d",&v1[q].a,&v1[q].b);
                v1[q].x=0;
                v2[q].a=v1[q].a;
                v2[q].b=v1[q].b;
                v2[q].x=0;
            }
            int tree[n];
            for(int q=0;q<n;q++)tree[q]=-1;
            tree[v1[0].a]=0;
    	    tree[v1[0].b]=1;
    	    v1[0].x=1;
    	    bool empty=1;
            while(empty){
                empty=0;
                for(int q=0;q<m;q++){
                    if(v1[q].x==0&&tree[v1[q].a]!=-1){
                        tree[v1[q].b]=tree[v1[q].a]+1;
                        v1[q].x=1;
                        empty=1;
                    }
                    else if(v1[q].x==0&&tree[v1[q].b]!=-1){
                        tree[v1[q].a]=tree[v1[q].b]+1;
                        v1[q].x=1;
                        empty=1;
                    }
                }
            }
            int maxd=-1,maxn=-1;
            for(int q=0;q<n;q++){
                if(tree[q]>maxd){
                    maxd=tree[q];
                    maxn=q;
                }
                tree[q]=-1;
            }
            tree[maxn]=0;
            empty=1;
            while(empty){
                empty=0;
                for(int q=0;q<m;q++){
                    if(v2[q].x==0&&tree[v2[q].a]!=-1){
                        tree[v2[q].b]=tree[v2[q].a]+1;
                        v2[q].x=1;
                        empty=1;
                    }
                    else if(v2[q].x==0&&tree[v2[q].b]!=-1){
                        tree[v2[q].a]=tree[v2[q].b]+1;
                        v2[q].x=1;
                        empty=1;
                    }
                }
            }
    //        for(int q=0;q<n;q++)cout<<tree[q]<<" ";
            maxd=-1,maxn=-1;
            for(int q=0;q<n;q++){
                if(tree[q]>maxd){
                    maxd=tree[q];
                    maxn=q;
                }
            }
            printf("%d\n",maxd);
    		
        }
    }
    
    回復 支持 反對

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表