hdu 1054 Strategic Game(트리 DP | | 다이어그램)

소기: 전에 이미 이 문제를 풀었기 때문에 문제를 푸는 주간 훈련에서 또 이 문제를 냈어요. 제 머릿속에 분명히 풀었다는 인상이 있어서 이 문제를 생각하지 않았어요.안 했어.그리고 오늘 hoj에 들어가서 봤는데 과연 제출했어, A야.또 어제 주간에 훈련한 것이 dp이기 때문에 제가 제출한 코드는 이분도로 만든 것을 봤습니다. 제목은 분명히 매우 전형적인 트리 dp입니다. 이분도에서 왜 이분도의 해제가 2로 정해되었는지 기억이 나지 않습니다. 훈련dp이기 때문에 제가 직접 트리 dp를 만들었습니다. 정말 클래식합니다. 코드는 모두 간단합니다. 1A입니다.
사고방식: 트리 dp 또는 이분도.이분도는 왜 가장 잘 어울리는지 모르겠다. 정해는 여기서 말하지 않고 코드를 붙인다.나무
dproot[i]는 i를 뿌리로 한 자수를 표시하며, i에 병사를 한 명 놓아 전체 자수를 지키는 데 병사가 얼마나 필요한지 확인한다.
all[i]는 i를 뿌리로 한 자수 전체를 지키는 데 얼마나 많은 병사가 필요한지 보라고 한다.
상태 이동 방정식: dproot[i] = 1 + ∑dproot[j] (j는 i의 아들)
all[i]=min(dproot[i], ∑all[j])(j는 i의 아들)
잎 노드를 dproot[i]=1,all[i]=0으로 초기화;
마지막 answer는min(dproot[root],all[root])(루트는 루트 노드)
트리 dp 코드:

#include <stdio.h>
#include <string.h>
#include <stack>
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))

const int MAX_ = 1510;


struct node{
    int to,next,cap;
}edge[MAX_*MAX_];

int dproot[MAX_];
int all[MAX_];
bool vis[MAX_];
int head[MAX_];
int n, M;

void add(int from,int to){
    edge[M].to = to;
    edge[M].cap = 1;
    edge[M].next = head[from];
    head[from] = M++;
}

void dfs(int x,int pre){
    dproot[x] = 1;
    int sum = 0;
    for(int i = head[x]; i+1; i = edge[i].next){
        int v = edge[i].to;
        if(pre == v)continue;
        dfs(v,x);
        sum += dproot[v];
        dproot[x] += all[v];
    }
    all[x] = min(dproot[x],sum);
}



int main() {
    int T;
    int m, k;

    while(~scanf("%d",&n)){
        M = 0;
        mst(head,-1);

        for(int i = 0; i < n; ++i){
            scanf("%d:(%d)",&m,&k);
            while(k--){
                int t;
                scanf("%d",&t);
                add(m,t);
                add(t,m);
            }
        }
        dfs(0,-1);
        printf("%d
",min(all[0],dproot[0]));
    }
    return 0;
}

이분도 코드:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 1501
typedef struct
{
    int to,next,cap;
}E;
E edge[N*N];
int V[N];
int dis[N];
int link[N];
int n,M;

void insert(int from,int to)
{
    edge[M].to=from;
    edge[M].cap=1;
    edge[M].next=V[to];
    V[to]=M++;
}
int dfs(int k)
{
    int i,t;
    for(i=V[k]; i+1; i=edge[i].next)
    {
        t=edge[i].to;
        if(!dis[t])
        {
            dis[t]=1;
            if(link[t]==-1||dfs(link[t]))
            {
                link[t]=k;
                return 1;
            }
        }
    }
   return 0;
}
int main()
{
    int i,j,m,num,k;
    while(~scanf("%d",&n))
    {
        memset(link,-1,sizeof(link));
        memset(V,-1,sizeof(V));
        M=0;
        for(i=0; i<n; i++)
        {
            scanf("%d:(%d)",&m,&k);
            while(k--)
            {
                scanf("%d",&j);
                insert(m,j);
                insert(j,m);
            }
        }
        num=0;
        for(i=0; i<n; i++)
        {
            memset(dis,0,sizeof(dis));
            if(dfs(i))num++;
        }
        printf("%d
",num/2);
    }
    return 0;
}