노드 제거

Question

장난감은 n 개의 부품과 m 개의 로프로 구성됩니다. 각 로프는 두 부분을 연결하지만 모든 부품 쌍은 하나의 로프로 연결됩니다. 장난감을 분리하려면 어린이가 모든 부품을 제거해야합니다. 아이는 한 번에 하나의 부분을 제거 할 수 있으며, 각 제거는 에너지를 소비합니다. 파트 i의 에너지 값을 vi로 정의합시다. 아이는 파트 i를 제거하기 위해 vf1 + vf2 + ... + vfk 에너지를 소비합니다. 여기서 f1, f2, ..., fk는 i 번째에 직접 연결되어 제거되지 않은 파트입니다.

솔루션 제안 : 모든 노드를 삭제하는 가장 좋은 방법은 값의 내림차순으로 삭제하는 것입니다.

코드 :

int n = in.nextInt(); 
int m = in.nextInt(); 
int[] w = new int[n]; 
for(int i=0;i<n;i++) {w[i]=in.nextInt(); 
} 

int[] c = new int[n]; 
int ans =0; 
for(int i=0;i<m;i++){ 
    int xx = in.nextInt(); 
    int yy = in.nextInt(); 
    ans+= Math.min(w[--xx],w[--yy]); 
} 
System.out.println(ans); 

} 
} 

모든 n 개의 노드를 삭제하는 문 최선의 방법을 설명해주십시오 내림차순을 삭제합니다. 왜 우리는 한 노드의 코트에만 추가할까요? Problem LInk

Answer 1

정확성의 증거입니다 (필자의 증명에서 '부품', '로프'및 '에너지 소비'대신 '정점', '가장자리'및 '지불'을 사용합니다).

1. 이 솔루션으로 생성 된 답변은 최적의 답변보다 크지 않습니다. 하나의 가장자리를 살펴 보겠습니다. 하나의 정점은 다른 정점 다음에 삭제됩니다. 우리는 나중에 삭제 된 것을 지불해야합니다. 그렇기 때문에 각 가장자리에 적어도 min(cost[v], cost[u])을 지불해야합니다.

2. 최적의 답은이 알고리즘에 의해 생성 된 답보다 크지 않습니다. 정점을 제거하는 순서로 정점을 제거합시다. 각 가장자리에 대해 더 저렴한 정점이 마지막으로 제거됩니다. 그래서 우리는 정확히 min(cost[v], cost[u])을 지불 할 것입니다.

그래서 우리는 최적의 해답이 더 클 수없고이 알고리즘에 의해 생성 된 답보다 작을 수 없음을 증명했습니다. 따라서 최적 (a >= b and a <= b은 a = b을 의미 함).

Answer 2

아니 공식적인 증거는, 당신이 이해하는 데 도움이 :

가 장난감을 분할하려면 각 로프는 '차단'해야합니다. 그리고 각각의 로프는 두 부분을 연결하여 총 에너지를 최소화하고 '낮은 에너지'부분에서 로프를 자르도록 선택합니다.

한 번에 하나의 부품을 제거하여이를 수행하는 방법은 무엇입니까? 부품을 내림차순으로 제거합니다 (각 로프에 대해 항상 작은 에너지를 소비합니다).

그러나 최소한의 에너지를 계산하려면 각 로프에 대해 더 작은 에너지를 추가하십시오 (이것은 코드가하는 것과 정확히 같습니다).