[NOIP 2012] 전염병 상황 통제

[제목 링크]
         https://www.luogu.org/problemnew/show/P1084
[알고리즘]
        세 심하게 관찰 한 결과 이 문제 의 답 은 단조 로 운 것 으로 나 타 났 다. 즉, p 시간 에 전염병 상황 을 통제 할 수 있다 면 q 시간 에 도 전염병 상황 (q > p) 을 통제 할 수 있 기 때문에 우 리 는 2 분 의 답 을 얻 을 수 있다. 이것 은 이 문제 의 돌파구 이다.
        문 제 는 '미 드 타임 이 전염병 상황 을 통제 할 수 있 는 지' 를 점검 하 는 것 으로 바 뀌 었 다.
        우 리 는 모든 잎 노드 가 관할 을 받 도록 요구 하 는 이상 군대 가 있 는 노드 의 깊이 가 얕 을 수록 관할 할 수 있 는 노드 수가 많다 는 것 을 알 게 되 었 다. 우 리 는 모든 군대 가 이동 할 수 있 는 최 정상 (뿌리 노드 로 이동 할 수 없 음) 으로 먼저 이동 하 게 하 는 것 이 좋 습 니 다. 구체 적 으로 실현 할 때 우 리 는 각 노드 를 배로 늘 려 서 위로 2 ^ j 개의 변 권 을 총화 할 수 있 습 니 다.
        이때 우 리 는 군 대 를 두 종류 로 나 눌 수 있다.
        첫 번 째 유형: 뿌리 노드 에 있 는 아들 노드
        두 번 째 유형: 비 근 노드 에 있 는 아들 노드
        두 번 째 군대 에 대해 우 리 는 그것 을 움 직 이지 않 으 면 된다. 첫 번 째 군대 에 대해 우 리 는 그것 으로 하여 금 자신 이 있 는 나무의 잎 노드 를 관할 하 게 할 수 있다. 물론 우 리 는 그것 으로 하여 금 뿌리 노드 를 넘 게 하고 그들 이 도착 할 수 있 는 (시간 제한 을 초과 하지 않 는), 다른 나무의 잎 노드 를 관할 하 게 할 수 있다.
        여기 서 결론 이 하나 있다. 첫 번 째 군대 에 대해 만약 에 이 군대 가 뿌리 노드 를 넘 지 못 하고 이 노드 로 돌아 갈 수 없다 면 이 노드 는 반드시 현재 이 노드 에 머 물 러 있 고 뿌리 노드 를 넘 지 못 하고 이 노드 로 돌아 갈 수 없다. 남 은 시간 이 가장 적은 군대 가 관할한다.
        이 결론 에 따 르 면 우 리 는 모든 관할 되 지 않 은 뿌리 노드 의 하위 노드 에 대해 현재 이 노드 에서 뿌리 노드 를 넘 지 못 하고 이 노드 로 돌아 갈 수 없 는 첫 번 째 군대 가 있 는 지 찾 아 보 자. 이런 군대 에서 남 은 시간 이 가장 적은 관할 노드 를 찾 아 이 군 대 를 삭제 했다.
        남 은 첫 번 째 군대 에 대해 우 리 는 먼저 관할 되 지 않 은 뿌리 노드 의 하위 노드 를 구 할 수 있다. 그 다음 에 군 대 를 남 은 시간 - 뿌리 노드 에 도착 하 는 시간 에 따라 오름차 순 으로 배열 하고 노드 를 뿌리 노드 의 거리 에 따라 오름차 순 으로 배열 하 며 욕심 을 내 어 한 번 스 캔 하면 된다.   
[코드]
        

#include
using namespace std;
#define MAXN 50010
#define MAXLOG 20
const long long INF = 1e15;

struct edge
{
        int to,w,nxt;
} e[MAXN << 2];
struct info
{
        int s;
        long long rest;
        bool used;
} a[MAXN],b[MAXN];
int i,n,m,u,v,w,tot;
int head[MAXN],pos[MAXN],depth[MAXN];
long long min_rest[MAXN];
int f[MAXN][MAXLOG];
long long dist[MAXN][MAXLOG];
long long sum,l,r,mid,ans;
bool managed[MAXN];

inline bool cmp(info a,info b)
{
        return a.rest < b.rest;
}
inline void addedge(int u,int v,int w)
{
        tot++;
        e[tot] = (edge){v,w,head[u]};
        head[u] = tot;
}
inline void dfs(int u)
{
        int i,v,w;
        for (i = 1; i < MAXLOG; i++)
        {
                f[u][i] = f[f[u][i - 1]][i - 1];
                dist[u][i] = dist[u][i - 1] + dist[f[u][i - 1]][i - 1];
        }
        for (i = head[u]; i; i = e[i].nxt)
        {
                v = e[i].to;
                w = e[i].w;
                if (v == f[u][0]) continue;
                f[v][0] = u;
                dist[v][0] = w;
                depth[v] = depth[u] + 1;
                dfs(v);    
        }
}
inline bool ok(int u)
{
        int i,v,size = 0;
        bool res = true;
        if (managed[u]) return true;
        for (i = head[u]; i; i = e[i].nxt)
        {
                v = e[i].to;
                if (v == f[u][0]) continue;
                size++;
                res &= ok(v);
        }
        res &= size;
        if (depth[u] == 1 && !res) b[++tot] = (info){u,dist[u][0]};
        return managed[u] = res;
}
inline bool check(long long mid)
{
        int i,k,rest,len = 0,cnt = 0,now;
        static int tmp[MAXN],p[MAXN];
        for (i = 1; i <= n; i++) 
        {
                managed[i] = false;
                min_rest[i] = INF;
        }
        for (i = 1; i <= m; i++) tmp[i] = pos[i];
        for (i = 1; i <= m; i++)
        {
                rest = mid;
                for (k = MAXLOG - 1; k >= 0; k--)
                {
                        if (f[tmp[i]][k] == 0 || f[tmp[i]][k] == 1) continue;
                        if (rest < dist[tmp[i]][k]) continue;
                        rest -= dist[tmp[i]][k];
                        tmp[i] = f[tmp[i]][k]; 
                }    
                if (depth[tmp[i]] == 1 && rest - dist[tmp[i]][0] > 0) a[++len] = (info){tmp[i],rest - dist[tmp[i]][0]};
                else managed[tmp[i]] = true;
        }        
        tot = 0;
        if (ok(1)) return true;
        for (i = 1; i <= len; i++)
        {
                if (!managed[a[i].s] && a[i].rest < dist[a[i].s][0]) 
                {
                        if (a[i].rest < min_rest[a[i].s])
                        {
                                min_rest[a[i].s] = a[i].rest;
                                p[a[i].s] = i;
                        }
                }
        } 
        for (i = 1; i <= n; i++) 
        {
                if (min_rest[i] != INF)
                {
                        managed[i] = true;
                        a[p[i]].used = true;
                        cnt++;
                }
        }
        tot = 0;
        if (ok(1)) return true;
        sort(a + 1,a + len + 1,cmp);
        sort(b + 1,b + tot + 1,cmp);
        now = 1;
        for (i = 1; i <= tot; i++)
        {
                while (now <= len && (a[now].rest < b[i].rest || a[now].used)) now++;
                if (now > len || a[now].rest < b[i].rest || a[now].used) return false;
                now++;
        }
        return true;
}

int main() 
{
        
        scanf("%d",&n);
        for (i = 1; i < n; i++)
        {
                scanf("%d%d%d",&u,&v,&w);
                addedge(u,v,w);
                addedge(v,u,w);
                sum += (long long)w;
        }
        scanf("%d",&m);
        for (i = 1; i <= m; i++) scanf("%d",&pos[i]);
        dfs(1);
        l = 0; r = sum;
        ans = -1;
        while (l <= r)
        {
                mid = (l + r) >> 1;
                if (check(mid))
                {
                        r = mid - 1;
                        ans = mid;
                } else l = mid + 1;
        }
        printf("%lld
",ans);
        
        return 0;
    
}

 
  
다음으로 전송:https://www.cnblogs.com/evenbao/p/9386371.html