无向无环图 --- 森林;树上的dp (最后解的形式为,M * a + b) a为森林某棵树上需放置的最小灯数,b为最少一盏灯照亮的边数;
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int maxn = 1010;
const int M = 2000;
int n,m,pre[maxn],vis[maxn][2],d[maxn][2];
vector<int> son[maxn];
int dp(int i,int j,int fa){
if(vis[i][j]) return d[i][j];
vis[i][j]=1; pre[i]=1;
d[......
阅读全文