POJ1947 - 트리 DP(Rebuilding Roads)
5609 단어 Build
제목의 대의.
n개의 결점을 가진 나무를 정해서 최소한 몇 개의 변을 삭제해야 하는지 물어보세요. 어떤 나무의 결점 개수는 p입니다.
문제풀이
고전적인 트리 DP~~~ 직접 방정식으로 갑시다 dp[u][j]=min(dp[u][j], dp[u][j-k]+dp[v][k]-1) 방정식은 u결점을 뿌리로 j개의 결점을 보존하기 위해 삭제해야 하는 가장 적은 변의 수를 뜻합니다. 그러면 어떤 하위 결점 v에서 k개의 보존을 선택하고 다른 결점은 j-k개를 보존할 수 있습니다. 왜 -1이 필요합니까? 하위 나무 v를 결점 u에 연결하는 것과 같기 때문에 가장자리 u->v는 삭제할 필요가 없습니다. -1은 삭제할 필요가 없습니다.
코드: #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 155
#define INF 0x3f3f3f3f
struct node
{
int v,next;
};
node edge[MAXN];
int head[MAXN],dp[MAXN][MAXN],p;
void add_edge(int u,int v,int &k)
{
edge[k].v=v;
edge[k].next=head[u];
head[u]=k++;
}
void dfs(int u)
{
if(head[u]==-1)
{
dp[u][1]=0;
return;
}
int cnt=0;
for(int i=head[u]; i!=-1; i=edge[i].next)
{
int v=edge[i].v;
dfs(v);
cnt++;
}
dp[u][1]=cnt;
for(int i=head[u]; i!=-1; i=edge[i].next)
{
int v=edge[i].v;
for(int j=p; j>=2; j--)
for(int k=1; k<=j; k++)
dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]-1);
}
}
int main()
{
int n;
while(scanf("%d%d",&n,&p)!=EOF)
{
int k=1;
memset(head,-1,sizeof(head));
memset(dp,INF,sizeof(dp));
for(int i=1; i<n; i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v,k);
}
dfs(1);
int ans=dp[1][p];
for(int i=2; i<=n; i++)
ans=min(ans,dp[i][p]+1);
printf("%d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Unity에 안드로이드를 구축하고 실행하면 소음에 문제가 생길 수 있습니다
다음 이미지는 UnityEditor의 작업 화면입니다.
다음은 안탁실 기구가 건설된 후 집행된 화면이다.
참고로 환경은...
Unity5.3.5
Android4.4.2
XperiaZ SO-02E
그렇습니다.
안드로이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
고전적인 트리 DP~~~ 직접 방정식으로 갑시다 dp[u][j]=min(dp[u][j], dp[u][j-k]+dp[v][k]-1) 방정식은 u결점을 뿌리로 j개의 결점을 보존하기 위해 삭제해야 하는 가장 적은 변의 수를 뜻합니다. 그러면 어떤 하위 결점 v에서 k개의 보존을 선택하고 다른 결점은 j-k개를 보존할 수 있습니다. 왜 -1이 필요합니까? 하위 나무 v를 결점 u에 연결하는 것과 같기 때문에 가장자리 u->v는 삭제할 필요가 없습니다. -1은 삭제할 필요가 없습니다.
코드: #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 155
#define INF 0x3f3f3f3f
struct node
{
int v,next;
};
node edge[MAXN];
int head[MAXN],dp[MAXN][MAXN],p;
void add_edge(int u,int v,int &k)
{
edge[k].v=v;
edge[k].next=head[u];
head[u]=k++;
}
void dfs(int u)
{
if(head[u]==-1)
{
dp[u][1]=0;
return;
}
int cnt=0;
for(int i=head[u]; i!=-1; i=edge[i].next)
{
int v=edge[i].v;
dfs(v);
cnt++;
}
dp[u][1]=cnt;
for(int i=head[u]; i!=-1; i=edge[i].next)
{
int v=edge[i].v;
for(int j=p; j>=2; j--)
for(int k=1; k<=j; k++)
dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]-1);
}
}
int main()
{
int n;
while(scanf("%d%d",&n,&p)!=EOF)
{
int k=1;
memset(head,-1,sizeof(head));
memset(dp,INF,sizeof(dp));
for(int i=1; i<n; i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v,k);
}
dfs(1);
int ans=dp[1][p];
for(int i=2; i<=n; i++)
ans=min(ans,dp[i][p]+1);
printf("%d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Unity에 안드로이드를 구축하고 실행하면 소음에 문제가 생길 수 있습니다
다음 이미지는 UnityEditor의 작업 화면입니다.
다음은 안탁실 기구가 건설된 후 집행된 화면이다.
참고로 환경은...
Unity5.3.5
Android4.4.2
XperiaZ SO-02E
그렇습니다.
안드로이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 155
#define INF 0x3f3f3f3f
struct node
{
int v,next;
};
node edge[MAXN];
int head[MAXN],dp[MAXN][MAXN],p;
void add_edge(int u,int v,int &k)
{
edge[k].v=v;
edge[k].next=head[u];
head[u]=k++;
}
void dfs(int u)
{
if(head[u]==-1)
{
dp[u][1]=0;
return;
}
int cnt=0;
for(int i=head[u]; i!=-1; i=edge[i].next)
{
int v=edge[i].v;
dfs(v);
cnt++;
}
dp[u][1]=cnt;
for(int i=head[u]; i!=-1; i=edge[i].next)
{
int v=edge[i].v;
for(int j=p; j>=2; j--)
for(int k=1; k<=j; k++)
dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]-1);
}
}
int main()
{
int n;
while(scanf("%d%d",&n,&p)!=EOF)
{
int k=1;
memset(head,-1,sizeof(head));
memset(dp,INF,sizeof(dp));
for(int i=1; i<n; i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v,k);
}
dfs(1);
int ans=dp[1][p];
for(int i=2; i<=n; i++)
ans=min(ans,dp[i][p]+1);
printf("%d
",ans);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Unity에 안드로이드를 구축하고 실행하면 소음에 문제가 생길 수 있습니다다음 이미지는 UnityEditor의 작업 화면입니다. 다음은 안탁실 기구가 건설된 후 집행된 화면이다. 참고로 환경은... Unity5.3.5 Android4.4.2 XperiaZ SO-02E 그렇습니다. 안드로이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
