loj2091 「ZJOI2016」小星星

ref

总的来说，就是

容斥转化为点对应到点集问题。
树形 dp 解决转化后的问题。

#include <iostream>

#include <cstring>

#include <vector>

#include <cstdio>

using namespace std;

typedef long long ll;

int n, m, hea[19], cnt, uu, vv;

bool w[19][19];

ll dp[19][19], ans;

struct Edge{

	int too, nxt;

}edge[105];

vector<int> vec;

void add_edge(int fro, int too){

	edge[++cnt].nxt = hea[fro];

	edge[cnt].too = too;

	hea[fro] = cnt;

}

void dfs(int x, int f){

	for(int i=0; i<vec.size(); i++)

		dp[x][vec[i]] = 1;

	for(int j=hea[x]; j; j=edge[j].nxt){

		int t=edge[j].too;

		if(t!=f){

			dfs(t, x);

			for(int i=0; i<vec.size(); i++){

				ll s=0;

				for(int k=0; k<vec.size(); k++){

					if(w[vec[i]][vec[k]]){

						s += dp[t][vec[k]];

					}

				}

				dp[x][vec[i]] *= s;

			}

		}

	}

}

int main(){

	cin>>n>>m;

	for(int i=1; i<=m; i++){

		scanf("%d %d", &uu, &vv);

		w[uu][vv] = w[vv][uu] = true;

	}

	for(int i=1; i<n; i++){

		scanf("%d %d", &uu, &vv);

		add_edge(uu, vv);

		add_edge(vv, uu);

	}

	for(int i=0; i<(1<<n); i++){

		vec.clear();

		for(int j=0; j<n; j++)

			if(i&(1<<j))

				vec.push_back(j+1);

		memset(dp, 0, sizeof(dp));

		dfs(1, 0);

		ll tmp=0;

		for(int j=0; j<vec.size(); j++)

			tmp += dp[1][vec[j]];

		if((n&1)==(vec.size()&1))	ans += tmp;

		else	ans -= tmp;

	}

	cout<<ans<<endl;

	return 0;

}

巴特西

loj2091 「ZJOI2016」小星星

最新文章

热门文章