[UVa1218] 완벽한 서비스

A network is composed of N computers connected by N − 1 communication links such that any twocomputers can be communicated via a unique route. Two computers are said to be adjacent if there isa communication link between them. The neighbors of a computer is the set of computers which areadjacent to it. In order to quickly access and retrieve large amounts of information, we need to selectsome computers acting as servers to provide resources to their neighbors. Note that a server can serveall its neighbors. A set of servers in the network forms a perfect service if every client (non-server) isserved by exactly one server. The problem is to find a minimum number of servers which forms aperfect service, and we call this number perfect service number.
We assume that N (≤ 10000) is a positive integer and these N computers are numbered from 1 toN. For example, Figure 1 illustrates a network comprised of six computers, where black nodes representservers and white nodes represent clients. In Figure 1(a), servers 3 and 5 do not form a perfect servicebecause client 4 is adjacent to both servers 3 and 5 and thus it is served by two servers which contradictsthe assumption. Conversely, servers 3 and 4 form a perfect service as shown in Figure 1(b). This setalso has the minimum cardinality. Therefore, the perfect service number of this example equals two.
Your task is to write a program to compute the perfect service number.
Input
The input consists of a number of test cases. The format of each test case is as follows: The first linecontains one positive integer, N, which represents the number of computers in the network. The next N − 1 lines contain all of the communication links and one line for each link. Each line is representedby two positive integers separated by a single space. Finally, a ‘0’ at the (N + 1)-th line indicates theend of the first test case.
The next test case starts after the previous ending symbol ‘0’. A ‘-1’ indicates the end of the wholeinputs.
Output
The output contains one line for each test case. Each line contains a positive integer, which is theperfect service number.
Sample Input
6
1 3
2 3
3 4
4 5
4 6
0
2
1 2
-1
Sample Output
2
1
제목:
n(n≤10000)대의 기계가 나무 구조를 형성한다.그 중 일부 기계에 서버를 설치해서 서버가 아닌 모든 컴퓨터가 한 대의 서버 컴퓨터와 꼭 인접하도록 하고 서버의 최소 수량을 구하도록 요구한다.
문제풀이1:dp
정의:
dp[i][0]: i는 서버이고 i의 하위 결점은 서버일 수도 있고 그렇지 않을 수도 있다.
dp[i][1]: i는 서버가 아니지만 i의 아버지는 서버입니다.
dp[i][2]: i와 i의 아버지는 모두 서버가 아닙니다
상태 전환 방정식:
dp[i][0]=sum{ min(dp[son][0], dp[son][1]) }+1;
dp[i][1]=sum{ dp[son][2] };
dp[i][2]=min( dp[i][2], dp[son][0]+dp[i][1]-dp[son][2] );
분석:
pp[i][0]: i는 이미 서버이기 때문에 서브 결점은 될 수도 있고 아닐 수도 있다. 작은 것을 선택하고 +1은 i 자체의 서버를 대표한다.
p[i][1]: i는 서버가 아니지만 i의 아버지가 서버라면 i의 모든 하위 결점이 서버일 수 없다. 그렇지 않으면 i는 두 개의 서버를 연결하고 가장 좋은 것이 아니다.
dp[i][2]: i와 i의 아버지가 모두 서버가 아니면 i가 있고 단지 하나의 하위 결점만 서버이다. 그렇지 않으면 i는 서버에 연결되지 않거나 여러 서버에 연결되지 않는다.
dp[i][2]=min(dp[i][2], dp[son][0]+sum{dp[otherson][2]}), 상태2는 dp[son][2]의 합을 계산하여 간소화할 수 있습니다.

#include
#include
#include
#include
#include
#include
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1e4+10;
int n, fir[N], ecnt, sum;
struct node{ int e, next; }edge[N<<1];
long long dp[N][3];

void Link( int s, int e ) {
	edge[++ecnt].e=e; edge[ecnt].next=fir[s]; fir[s]=ecnt;
	edge[++ecnt].e=s; edge[ecnt].next=fir[e]; fir[e]=ecnt;
}

void DFS( int r, int fa ) {
	bool flg=0;
	dp[r][0]=1;
	dp[r][1]=0;
	dp[r][2]=INF;
	for( int i=fir[r]; i; i=edge[i].next )
		if( edge[i].e!=fa ) {
			DFS( edge[i].e, r );
			flg=1;
			dp[r][0]+=min( dp[edge[i].e][0], dp[edge[i].e][1] );
			dp[r][1]+=dp[edge[i].e][2];
		}
	if( !flg ) return;
	for( int i=fir[r]; i; i=edge[i].next )
		if( edge[i].e!=fa )
			dp[r][2]=min( dp[r][2], dp[edge[i].e][0]+dp[r][1]-dp[edge[i].e][2] );
}

void Reset() {
	ecnt=0;
	memset( fir, 0, sizeof fir );
}

int main() {
	while( ~scanf( "%d", &n ) ) {
		if( !n ) continue;
		if( n==-1 ) break;
		Reset();
		for( int i=1; i

욕심
만약 한 점의 모든 아들과 그 자신이 서버가 아니라면, 그의 아버지 노드를 서버로

#include
#include
#include
#include
#include
#include
using namespace std;
const int N=1e4+10;
int n, fir[N], ecnt, sum;
struct node{ int e, next; }edge[N<<1];
bool vis[N];

void Link( int s, int e ) {
	edge[++ecnt].e=e; edge[ecnt].next=fir[s]; fir[s]=ecnt;
	edge[++ecnt].e=s; edge[ecnt].next=fir[e]; fir[e]=ecnt;
}

void DFS( int r, int fa ) {
	bool flg=0;
	for( int i=fir[r]; i; i=edge[i].next )
		if( edge[i].e!=fa ) {
			DFS( edge[i].e, r );
			if( vis[edge[i].e] ) flg=1;
		}
	if( !flg && !vis[r] && !vis[fa] ) sum++, vis[fa]=1;
}

void Reset() {
	sum=ecnt=0;
	memset( vis, 0, sizeof vis );
	memset( fir, 0, sizeof fir );
}

int main() {
	while( ~scanf( "%d", &n ) ) {
		if( !n ) continue;
		if( n==-1 ) break;
		Reset();
		for( int i=1; i