UVa 1218(트리 dp)
제목: n대의 컴퓨터가 있는데, 서로 뿌리가 없는 나무로 연결된다.현재 그 중 일부 컴퓨터를 서버로 하고 있으며, 모든 컴퓨터에 서버를 연결해야 한다.(자체가 서버인 컴퓨터는 포함하지 않음) 서버로 몇 대의 컴퓨터가 필요하냐고 물었다.
생각:
설u는 아버지이고, v는 u의 아이이다.
d(u,0): u 자체가 서버입니다.
d(u,1): u는 서버가 아닙니다. u의 아버지는 서버입니다.
d(u,2): u는 서버가 아닙니다. u의 아버지는 서버가 아닙니다. u의 아이는 반드시 있어야 하고 하나만 서버입니다.
그러면 나올 수 있어요.
d(u,0) = Sum(d(v,1));
d(u,1) = Sum(d(v,2));
d(u,2) = min(d(u,2), d(u,1)-d(v,2)+d(v,0));
코드: d[u][2]를 주의하십시오. inf를 초기화하지 마십시오. 이렇게 누적할 때 상한선을 초과합니다. 이것은wa가 여러 번 있기 때문입니다.
#include
#include
#include
#include
#include
#include
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 10010;
int n;
vectorg[maxn];
int dp[maxn][3];
int vis[maxn];
void dfs(int u)
{
queueq;
vis[u] = 1;
dp[u][0] = 1;
dp[u][1] = 0;
dp[u][2] = n;
for(int i = 0; i < g[u].size(); i++)
{
int v = g[u][i];
if(!vis[v])
{
dfs(v);
q.push(v);
dp[u][0] += min(dp[v][0],dp[v][1]);
dp[u][1] += dp[v][2];
}
}
while(!q.empty())
{
dp[u][2] = min(dp[u][2],dp[u][1]-dp[q.front()][2]+dp[q.front()][0]);
q.pop();
}
}
int main()
{
while(cin>>n)
{
if(n==0)
continue;
if(n==-1)
break;
for(int i = 1; i <= n; i++)
g[i].clear();
for(int i = 0; i < n-1; i++)
{
int u,v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
memset(vis,0,sizeof(vis));
dfs(1);
int ans = min(dp[1][0],dp[1][2]);
cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
