Codeforces 1155F 状压DP

题意：给你一张图，问最少保留多少条边，使得这张图是边双联通分量。

思路：如果一个点集中的点已经是边双联通分量，那么从这个点集中的点x出发，经过若干个不是点集中的点，回到点集中的点y（x可能等于y），那么这条路径上的点和原来的点就构成了一个新的边双联通分量。

设dp[i]是状态i中的点构成边双联通分量需要的最少的边数，那么我们需要枚举dp[i]的子集，然后判断剩下的点能不能通过一条链串起来，如果可以，那么就是剩下的链的点的个数 + 1.那么怎么知道有没有链呢？这个也需要处理，设dp2[i][j][k]是从i开始，途中经过了点集k中的点，能不能到j(k中不包括i和j),直接dp处理就可以了。

代码：

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

#define lowbit(x) (x & (-x))

using namespace std;

vector<int> G[14];

int dp[1 << 14], dp2[14][14][1 << 14];

vector<int> re[1 << 14];

pair<int, int> last_pair[1 << 14];

int pre[1 << 14];

int last[14][14][1 << 14];

bool v[1 << 14];

int main() {

	int n, m, x, y;

	scanf("%d%d", &n, &m);

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

		scanf("%d%d", &x, &y);

		G[x - 1].push_back(y - 1);

		G[y - 1].push_back(x - 1);

	}

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

		v[1 << i] = 1;

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

	dp[1] = 0;

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

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

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

				dp2[i][j][k] = INF;

			}

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

		for (auto x : G[i]) {

			dp2[i][x][0] = 1;

			last[i][x][0] = i;

		}

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

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

			if((i >> j) & 1) continue;

			for (int k = 0; k < n; k++) {

				if((i >> k) & 1) continue;

				if(j == k || dp2[j][k][i] == INF) continue;

				for (auto z : G[k]) {

					if((i >> z) & 1) continue;

					if(z == last[j][k][i]) continue;

					int tmp = i ^ (1 << k);

					if(dp2[j][z][tmp] == INF) {

						dp2[j][z][tmp] = 1;

						last[j][z][tmp] = k;

					}

				}

			}

		}

	}

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

		dp[1 << i] = 0;

//	dp[1] = 0;

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

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

			if((i >> j) & 1)

				re[i].push_back(j);

		}

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

		for (int j = i; j; j = (j - 1) & i) {

			int tmp = i ^ j;

			int cnt = __builtin_popcount(j) + 1;

			if(dp[i] < dp[tmp] + cnt) continue;

			for (auto x : re[tmp])

				for (auto y : re[tmp]) {

					if(dp2[x][y][j] == 1) {

						dp[i] = min(dp[i], dp[tmp] + cnt);

						last_pair[i] = make_pair(x, y);

						pre[i] = tmp;

					}

				}

		}

	}

	if(dp[(1 << n) - 1] == INF) {

		printf("-1\n");

	} else {

		printf("%d\n", dp[(1 << n) - 1]);

		int now = (1 << n) - 1;

		while(!v[now]) {

			int x = last_pair[now].first, y = last_pair[now].second;

			int tmp = now ^ pre[now];

			while(tmp) {

				int tmp1 = last[x][y][tmp];

				printf("%d %d\n", y + 1, tmp1 + 1);

				y = tmp1;

				tmp ^= (1 << tmp1);

			}

			printf("%d %d\n", x + 1, y + 1);

			now = pre[now];

		}

	}

}

巴特西

Codeforces 1155F 状压DP

最新文章

热门文章