紫书例题 11-6 UVa 658 （状态压缩+隐式图搜索+最短路）

这道题用到了很多知识点，是一道好题目。

第一用了状态压缩，因为这里最多只有20位，所以可以用二进制来储存状态（要对数据范围敏感），然后

涉及到了一些位运算。

第二这里是隐式图搜索，和之前有一道bfs倒水的有点像，就是题目和图论没有半毛钱关系，但是却可以自己建

图来做，把状态看作点，把状态转移看作边。

第三因为求最短时间，所以用了堆优化dijsktra。

#include<cstdio>

#include<queue>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 20;

const int MAXM = 112;

int t[MAXN], d[1<<MAXN], n, m;

char pre[MAXM][MAXN + 5], aft[MAXM][MAXN + 5];

struct node

{

	int u, w;

	node(int u = 0, int w = 0) : u(u), w(w) {}

	bool operator < (const node& rhs) const

	{

		return w > rhs.w;

	}

};

int solve()

{

	REP(i, 0, 1 << n) d[i] = (i == ((1 << n) - 1) ? 0 : 1e9);

	priority_queue<node> q;

	q.push(node((1 << n) - 1, 0));

	while(!q.empty())

	{

		node x = q.top(); q.pop();

		if(x.u == 0) return x.w;

		int u = x.u;

		if(x.w != d[u]) continue;

		REP(i, 0, m)

		{

			int ok = true;

			REP(j, 0, n) //相当于判断是否可以走当前这条边，相当于遍历与当前点连接的边

			{

				if(pre[i][j] == '+' && !(u & (1 << j))) { ok = false; break; }

				if(pre[i][j] == '-' && (u & (1 << j))) { ok = false; break; }

			}

			if(!ok) continue;

			node v = node(u, x.w + t[i]);

			REP(j, 0, n) //相当于达到新的点

			{

				if(aft[i][j] == '+') v.u |= (1 << j); //把当前位变为1

				if(aft[i][j] == '-') v.u &= ~(1 << j); //把当前位变成0

			}

			if(d[v.u] < 0 || v.w < d[v.u]) //松弛

			{

				d[v.u] = v.w;

				q.push(v);

			}

		}

	}

	return -1;

}

int main()

{

	int kase = 0;

	while(~scanf("%d%d", &n, &m) && n && m)

	{

		REP(i, 0, m) scanf("%d%s%s", &t[i], pre[i], aft[i]);

		int ans = solve();

		printf("Product %d\n", ++kase);

		if(ans < 0) printf("Bugs cannot be fixed.\n\n");

		else printf("Fastest sequence takes %d seconds.\n\n", ans);

	}

	return 0;

}

巴特西

紫书例题 11-6 UVa 658 （状态压缩+隐式图搜索+最短路）

最新文章

热门文章

巴特西

紫书 例题 11-6 UVa 658 （状态压缩+隐式图搜索+最短路）

最新文章

热门文章

紫书例题 11-6 UVa 658 （状态压缩+隐式图搜索+最短路）