Cod sursa(job #59184)

Utilizator dominoMircea Pasoi domino Data 8 mai 2007 15:50:10
Problema Salvare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

#define MAX_N 1024
#define FIN "salvare.in"
#define FOUT "salvare.out"
#define INF 0x3f3f3f3f
#define mp make_pair
#define f first
#define s second

int N, K, G[MAX_N][MAX_N], deg[MAX_N], up[MAX_N], nv;
pair<int, int> V[MAX_N]; char U[MAX_N], sol[MAX_N];

void DFS(int n, int lev)
{
    int *p;

    V[nv++] = mp(lev, n);
    for (p = G[n]; *p; p++)
        if (*p != up[n]) { up[*p] = n; DFS(*p, lev-1); }
}

void DFS2(int n, int up, int d)
{
    int *p;

    U[n] = 1;
    if (d == 0) return;
    for (p = G[n]; *p; p++)
        if (*p != up) DFS2(*p, n, d-1);
}

int works(int D)
{
    int i, j, d, ret = 0;

    memset(U, 0, sizeof(U));
    memset(sol, 0, sizeof(sol));
    for (i = 0; i < nv; i++)
    {
        if (U[j = V[i].s]) continue;
        for (d = D; up[j] && d; j = up[j], d--);
        sol[j] = 1; ret++;
        DFS2(j, 0, D);
    }
    return ret;
}

int main(void)
{
    int i, j, inc;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d %d", &N, &K);
    for (inc = 1; inc < N; inc++)
    {
        scanf("%d %d", &i, &j);
        G[i][deg[i]++] = j;
        G[j][deg[j]++] = i;
    }

    DFS(1, 0);
    sort(V, V+nv);

    for (inc = 1; inc < N; inc <<= 1);
    for (i = N; inc; inc >>= 1)
        if (i-inc >= 0 && works(i-inc) <= K) i -= inc;

    K -= works(i);
    for (j = 1; j <= N && K; j++)
        if (!sol[j]){ sol[j] = 1; K--; }

    printf("%d\n", i);
    for (j = 1; j <= N; j++)
        if (sol[j]) printf("%d ", j);
    printf("\n");

    return 0;
}