Pagini recente » Cod sursa (job #2214163) | Cod sursa (job #1418807) | Cod sursa (job #1627673) | Cod sursa (job #3233863) | Cod sursa (job #92468)
Cod sursa(job #92468)
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define minim(a, b) ((a < b) ? a : b)
#define pb push_back
#define INF 2000000001
#define NMax 1005
int N, K, q[NMax], uz[NMax], t[NMax], dist[NMax], up[NMax], bst;
vector<int> G[NMax];
void compute(int X, int n)
{
int i, x;
dist[n] = INF; up[n] = X;
for (i = 0; i < G[n].size(); i++)
{
x = G[n][i];
if (x == t[n]) continue;
dist[n] = minim(dist[n], dist[x]+1);
up[n] = minim(up[n], up[x]-1);
}
if (dist[n] <= up[n])
up[n] = INF;
else
{
if (n == 1 || !up[n])
dist[n] = 0, up[n] = INF;
}
}
int check(int X)
/* cate check-pointuri sa puna minim a. i. distanta pana la cel
mai apropiat check-point sa fie <= X */
{
int i, cnt = 0;
memset(dist, 0, sizeof(dist));
memset(up, 0, sizeof(up));
for (i = N; i >= 1; i--)
compute(X, q[i]);
for (i = 1; i <= N; i++)
if (!dist[i])
cnt++;
return cnt;
}
int main(void)
{
int i, u, v, qr, ql, st, dr, m, ok;
freopen("salvare.in", "r", stdin);
freopen("salvare.out", "w", stdout);
scanf("%d %d", &N, &K);
for (i = 1; i < N; i++)
{
scanf("%d %d", &u, &v);
G[u].pb(v); G[v].pb(u);
}
for (q[qr=ql=1]=1, uz[1] = 1; qr <= ql; qr++)
for (i = 0; i < G[q[qr]].size(); i++)
{
u = G[q[qr]][i];
if (!uz[u])
{
uz[u] = 1;
q[++ql] = u;
t[u] = q[qr];
}
}
st = 0; dr = N-1;
while (st <= dr)
{
m = (st + dr) / 2;
ok = check(m);
if (ok <= K) bst = m, dr = m-1;
else st = m+1;
}
ok = check(bst); ok = K-ok;
for (i = 1; i <= N; i++)
if (!dist[i] && ok)
dist[i] = 0, ok--;
printf("%d\n", bst);
for (i = 1; i <= N; i++)
if (!dist[i])
printf("%d ", i);
printf("\n");
return 0;
}