樹形dp和二分圖

• 樹形dp
• • 沒有上司的舞會
  • 選課
• 二分圖

樹形dp

沒有上司的舞會

樹形dp主要是用于對一棵樹上的結點按照樹的周遊順序進行動态規劃，樹形dp的思維難度不高，主要原因是樹的周遊方式一般固定，dp的變化不多，是以多做題熟悉樹形dp的方式就可以很好的掌握這種算法。

沒有上司的舞會.

在一場舞會上，每個員工不能和自己的直接上司共同出席，每個員工都有出席的快樂質數，求舞會最大的快樂值。

這是很經典的樹形dp圖，主要是用到樹的周遊嵌套上01背包

狀态表示：

f[u][0]：所有以u為根的子樹中選擇，并且不選u這個點的方案
f[u][1]：所有以u為根的子樹中選擇，并且選u這個點的方案
           

屬性：求出這場舞會的最大快樂值

狀态計算：

當目前u這個結點選的時候，子節點一定不能選

f[u][1] += f[j][0];
           

當目前u這個結點不選的時候，子節點可以選可以不選

f[u][0] += max(f[j][0], f[j][1]);
           

存點的話可以用鄰接表來存，鄰接表比較适合dfs

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const ll mod = 1000000007;
pair<int, int> mate[10];
const int N = 6000 ;
const int M = 200010;
typedef pair<int, int> PII;
//priority_queue<int, vector<int>, less<int> > q;  //這樣就是小頂堆

int h[N], e[N], ne[N], idx;
int happy[N];
int n;
bool has_fa[N];
int f[N][2];

void add(int a,int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs(int u)
{
    f[u][1] = happy[u];
    for (int i = h[u]; ~i;i=ne[i])
    {
        int j = e[i];
        dfs(e[i]);
        f[u][1] += f[j][0];
        f[u][0] += max(f[j][0], f[j][1]);
    }
}   

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n;i++)
    {
        cin >> happy[i];
    }
    
    for (int i = 0; i < n-1 ;i++)
    {
        int a,b;
        cin >> a >> b;
        add(b, a);
        has_fa[a] = true;
    }
    int root = 1;
    while(has_fa[root])
        root++;
    dfs(root);
    cout << max(f[root][1], f[root][0]);
    return 0;
}

           

選課

選課.

有些課會有一門先選課，如果要選這門課的話，就需要把所有的先選課都選上，每一門課都有學分，求可以選擇的最大學分。

這題用到的是樹上的分組背包來求解，每一門課以及它的所有兒子結點是一組，一組内需要的體積就是從根結點到這個點的點的個數，這題有一點需要注意，可能會出現多棵樹，這就需要創造出一個虛拟結點0，以這個結點為根節點，把所有樹變成一棵樹。

狀态表示

f[u][j]：所有以u為根節點，選了j個結點的方案
           

屬性：這個方案的最大值

狀态計算：

我們已經把這題按照分組背包的優化，将二維優化到一維，是以為了用到上一組的狀态，我們需要從後往前周遊，不然會發生串聯，具體可以看分組背包。對于每一個結點，枚舉一下背包的容量，然後周遊一下要挑選的點的個數，e[i]為目前結點的子節點。

f[u][j] = max(f[u][j], f[u][j - k]+f[e[i]][k]);
           

void dfs(int u)     
{
    for (int i = h[u]; i != -1;i=ne[i])物品組
    {
        dfs(e[i]) ;
        for (int j = m - 1; j;j--)背包容量
        {
        決策組内的選擇，下标從1開始可以參見前面的分組背包問題
            for (int k = 1; k <= j;k++)
            {
                f[u][j] = max(f[u][j], f[u][j - k]+f[e[i]][k]);
            }
        }
    }       
	選u本身也會有價值，加上選u的價值

    for (int i = m; i;i--)
    {
        f[u][i] = f[u][i - 1] + w[u];
    }
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n;i++)
    {
        int p;
        cin >> p >> w[i];   
        add(p, i);
    }
    m++;
   	構造虛拟結點0
    dfs(0);
    cout << f[0][m];
    return 0;
}

           

二分圖

二分圖的定義

将所有點分成兩個集合，使得所有邊隻出現在集合之間，就是二分圖
           

二分圖的性質

二分圖：一定不含有奇數環，可能包含長度為偶數的環， 不一定是連通圖
           

我們可以依據二分圖的性質來操作，用染色法來判斷一個圖是不是二分圖

首先，我們開一個color數組，用1和2來區分不同的顔色，0表示還未染色。

然後周遊所有的點，每次将未然而的點進行不斷的遞歸，染色成1或者2

隻要出現有一個點有沖突，就說明這個圖不是二分圖，我們就可以直接退出遞歸，有沖突是指一條邊上的兩個點是相同的顔色

bool dfs(int u,int c)
{
    color[u]=c;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!color[j])
        {
            if(!dfs(j,3-c))return false;
        }
        else if(color[j]==c)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    bool flag=true;
    for(int i=1;i<=n;i++)
    {
        if(!color[i])
        {
            if(!dfs(i,1))
            {
                flag=false;
                break;
            }
        }
    }
    if(flag)
    {
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;

    }
    return 0;
}