MENU

Codeforce 11D A Simple Task

2019-07-10 • 阅读: 21 • 阅读设置

题目链接:

A Simple Task

题意:

统计所有环的个数

思路:

状压DP
从一个点出发经过若干个点后能再次回到这个点,那么这个就是环。同时我们不关注如何到达这个点,只关心到这个点有多少种方法。
按照正常状压的思路,我们枚举所有状态。
dp[s][j]dp[s][j]表示到达状态为ss且当前在jj点的方案数。然后我们用j点去更新其他点。就是jj能够到达的点vv,且状态ss未经过vv,则此时我们就可以从jj走到vv,并且让dp[s(1<<v)][v]dp[s|(1<<v)][v] 加上dp[s][j]dp[s][j],如果状态ss经过了vv,则此时就构成了一个环。
为了避免重复计数,我们认为编号小的为环的起点,也就是说对于1,2,31,2,3这个环,我们只把11当作起点,即12311\to 2\to3 \to 1。由于是无向图,计算12311\to 2\to3 \to 1的时候也会计算13211\to 3\to2 \to 1,即计算了两次,同时每条边的两个顶点也会被当成环,如2322\to3\to2,但不会被计算两次,最后处理一下即可。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include<iostream>
using namespace std;
const int N = 20;
typedef long long ll;
struct E{
	int to, next;
}edge[1005];
int head[N], tot;
int n, m;
void addedge(int from, int to)
{
	edge[++tot].to = to;
	edge[tot].next = head[from];
	head[from] = tot;
}
ll dp[1<<N][N];
int main()
{
	memset(head, -1, sizeof(head));
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		addedge(u - 1, v - 1);
		addedge(v - 1, u - 1);
	}
	for (int i = 0; i <= n; i++)
		dp[1 << i][i] = 1;
	ll ans = 0;
	for (int i = 1; i < (1<<n); i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!dp[i][j]) continue;
			for (int k = head[j]; k != -1; k = edge[k].next){
				int v = edge[k].to;//从j->v,由于不能重复计算,所以起点固定为小的开始,这个就是处理的方法
				if ((i&(-i))>(1 << v)) continue;
				if ((i >> v) & 1){
					if ((i&(-i)) == (1 << v)) ans += dp[i][j];
				}
				else{
					dp[i | (1 << v)][v] += dp[i][j];
				}
			}
		}
	}
	
	printf("%lld\n", (ans - m) / 2);
	return 0;
}

返回文章列表 文章二维码 打赏
本页链接的二维码
打赏二维码