Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

太奇葩了,思路是很清楚的,但是感觉结构比较奇葩,思想上应该是dp树

Posted by zikunvan at 2014-09-04 10:18:20
#include <iostream>
#include <vector>
using namespace std;

#define MAX 20001
#define max(a, b) (a) > (b) ? (a) : (b)

void POJ1655();

typedef pair<int, int> Pair;
int N;
//using adjacent table to store the graph

//就是他!!!很奇葩的呢
vector<Pair> node[MAX];
/********把你围起来*******/

int minVal[MAX];

int main(int argc, const char * argv[]){
    POJ1655();
    return 0;
}
void input() {
    int a, b;
    for (int i = 1; i < N; i ++) {
        node[i].clear();
    }
    for (int i = 1; i < N; i ++) {
        cin >> a >> b;
        //construct the graph
        node[a].push_back(Pair(b,-1));
        node[b].push_back(Pair(a,-1));
    }
}
int dfs(int pre, int next) {
    int l = 0;
    for (int i = 0; i < node[next].size(); i ++) {
        if (node[next][i].first != pre) {
            if (node[next][i].second == -1) {
                node[next][i].second = dfs(next, node[next][i].first);
            }
            l += 1 + node[next][i].second;
        }
    }
    return l;
}
void dfs() {
    //core code
    int m;
    for (int i = 1; i <= N; i ++) {
        m = 0;
        for (int j = 0; j < node[i].size(); j ++) {
            node[i][j].second = dfs(i, node[i][j].first);
            m = max(m, node[i][j].second+1);
        }
        minVal[i] = m;
    }
    return ;
}
Pair maxVal() {
    int m = minVal[1], id = 1;
    for (int i = 2 ; i <= N; i ++) {
        if (m > minVal[i]) { m = minVal[i]; id = i; }
    }
    return Pair(id, m);
}
void POJ1655() {
    int num;
    cin >> num;
    while (num --) {
        cin >> N;
        input();
        dfs();
        Pair rsl = maxVal();
        cout<<rsl.first<<" "<<rsl.second<<endl;
    }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator