當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

CodeForces - 748F Santa Clauses and a Soccer Championship

發布時間：2024/10/8 编程问答 28 如意码农

生活随笔收集整理的這篇文章主要介紹了 CodeForces - 748F Santa Clauses and a Soccer Championship 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

題意：有k對隊伍，每對隊伍之間將舉行兩次比賽，兩支隊伍各主辦一次。住宿的地方要求在兩支隊伍家鄉的最短路的結點上或者在兩支隊伍的家鄉。問在選擇住宿處最少的情況下，怎么組成這k對隊伍？

分析：

1、因為n個點，n-1條邊，且連通圖，因此所有隊伍的關系形成一棵樹。

2、樹上任意兩點之間的最短路是唯一的。

3、因此住宿處一定只有一個，它是k對隊伍到彼此家鄉的必經結點。

4、從某點出發，找一個子樹中家鄉的個數>=k的點作為住宿處，則以該點子樹中的家鄉為家鄉的k支隊伍，與其他k支隊伍配對即可。

#pragma comment(linker, "/STACK:102400000, 102400000")

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define Min(a, b) ((a < b) ? a : b)

#define Max(a, b) ((a < b) ? b : a)

const double eps = 1e-8;

inline int dcmp(double a, double b){

    if(fabs(a - b) < eps) return 0;

    return a > b ? 1 : -1;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const int MOD = 1e9 + 7;

const double pi = acos(-1.0);

const int MAXN = 200000 + 10;

const int MAXT = 1000000 + 10;

using namespace std;

int n, k, root;

vector<int> v[MAXN], l, r;

int vis[MAXN];

void init(){

    for(int i = 0; i < MAXN; ++i){

        v[i].clear();

    }

    memset(vis, 0, sizeof vis);

    l.clear();

    r.clear();

    root = 0;

}

int get_root(int x, int father){

    int sum = vis[x] ? 1 : 0;

    int len = v[x].size();

    for(int i = 0; i < len; ++i){

        int tmp = v[x][i];

        if(tmp == father) continue;

        sum += get_root(tmp, x);

        if(root) return 0;

    }

    if(sum >= k) root = x;

    return sum;

}

void dfs(int x, int father){

    if(vis[x]){

        int L = l.size();

        if(L < k)

            l.push_back(x);

        else r.push_back(x);

    }

    int len = v[x].size();

    for(int i = 0; i < len; ++i){

        int tmp = v[x][i];

        if(tmp == father) continue;

        dfs(tmp, x);

    }

}

int main(){

    while(scanf("%d%d", &n, &k) == 2){

        init();

        for(int i = 0; i < n - 1; ++i){

            int a, b;

            scanf("%d%d", &a, &b);

            v[a].push_back(b);

            v[b].push_back(a);

        }

        for(int i = 0; i < 2 * k; ++i){

            int x;

            scanf("%d", &x);

            vis[x] = 1;

        }

        get_root(1, -1);

        dfs(root, -1);

        printf("1\n%d\n", root);

        for(int i = 0; i < k; ++i){

            printf("%d %d %d\n", l[i], r[i], root);

        }

    }

    return 0;

}

總結

以上是生活随笔為你收集整理的CodeForces - 748F Santa Clauses and a Soccer Championship的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： Java动态代理的两种实现方法：JDK动
下一篇： Linux_新建用户