首页 > 搜索 > BFS搜索 > HDU 4640-Island and study-sister-动态规划-[解题报告]HOJ
2015
09-17

HDU 4640-Island and study-sister-动态规划-[解题报告]HOJ

Island and study-sister

问题描述 :

Members of ACM/ICPC teams of Fuzhou University always stay in the laboratory in their free time. One day the team members of OOXX are doing their daily training and suddenly received k calls from study-sisters asking for their help. You can regard the campus of Fuzhou University is consist of n beautiful islands and connected by m undirection bridges and the study-sisters are in some of these islands waiting for them. As the members of OOXX are all warm-hearted, they don’t want these study-sisters waiting too long and just want the time the girl whom waiting for the longest be as short as possible. You can assume that they begin to move immediately after they received the calls. They start from the laboratory and they can go anywhere freely by the bridges.
But due to some mysterious reason, each island can be visited only by one member except the laboratory. This means that even if two guys come to an island in two different times is forbidden. Now your task is calculating how long these study-sisters will wait. Note that there are three students in team OOXX.

输入:

The first line contains only one integer T (T<=150), which is the number of test cases. Each test case contains two integer n (1<= n <=17), m (m <= n*n), means that Fuzhou university is consist of n islands and there are m undirection bridges connect them. Then comes m lines, each line contains three integer x, y, s, means that there is a bridge connect island x and island y and it takes s unit of time to go through this bridge. The numbers start from 1 to n and the number of the laboratory is always 1. Then comes a number k (k>=1) indicate that there are k study-sisters waiting for help. The next line are k integers xi (2<=xi<=n) describe where these study-sisters are. You can assume that all the study-sisters are in different islands.

输出:

The first line contains only one integer T (T<=150), which is the number of test cases. Each test case contains two integer n (1<= n <=17), m (m <= n*n), means that Fuzhou university is consist of n islands and there are m undirection bridges connect them. Then comes m lines, each line contains three integer x, y, s, means that there is a bridge connect island x and island y and it takes s unit of time to go through this bridge. The numbers start from 1 to n and the number of the laboratory is always 1. Then comes a number k (k>=1) indicate that there are k study-sisters waiting for help. The next line are k integers xi (2<=xi<=n) describe where these study-sisters are. You can assume that all the study-sisters are in different islands.

样例输入:

4
2 0
1
2
2 1
1 2 1
1
2
4 3
1 2 1
2 3 2
2 4 2
2
3 4
4 3
1 2 2
1 3 3
1 4 4
3
2 3 4

样例输出:

Case 1: -1
Case 2: 1
Case 3: 7
Case 4: 4

bfs+状态压缩求出所有的状态,然后由于第一个节点需要特殊处理,可以右移一位剔除掉,也可以特判。然后采用集合的操作,

#pragma comment(linker,"/STACK:1024000000,1024000000")
#include <cstdio>
#include <queue>
using namespace std;
#define inf 0x3f3f3f3f

int n, m, cnt;
int head[17], next[17 * 17 * 2 + 3][3], dp[1 << 17][17], dis[1 << 17], num[1 << 17];

void add (int u, int v, int w)
{
	next[cnt][1] = v;
	next[cnt][2] = w;
	next[cnt][0] = head[u];
	head[u] = cnt++;
}

void bfs ()
{
	queue<pair<int, int> > q;
	q.push(make_pair(0, 1));
	dp[1][0] = 0;
	while (!q.empty()){
		pair<int, int> p = q.front();
		q.pop();
		int su = p.second;
		int u = p.first;
		for (int i = head[u]; i != -1; i = next[i][0]){
			int v = next[i][1];
			int w = next[i][2];
			int sv = su|(1 << v);
			if(dp[sv][v] > dp[su][u] + w){
				dp[sv][v] = dp[su][u] + w;
				q.push(make_pair(v, sv));
			}
		}
	}
}

int main ()
{
	//freopen ("in.txt", "r", stdin);
	int t, count = 0;
	scanf ("%d", &t);
	while (t--)
	{
		scanf ("%d %d", &n, &m);
		int u, v, w;
		for (int i = 0; i < n; ++i) head[i] = -1;
		for (int i = (1 << n) - 1; i >= 0; --i){
			dis[i] = inf;
			num[i] = inf;
			for (int j = 0; j < n; ++j) dp[i][j] = inf;
		}
		cnt = 0;
		for (int i = 0; i < m; ++i){
			scanf ("%d %d %d", &u, &v, &w);
			add (u - 1, v - 1, w);
			add (v - 1, u - 1, w);
		}
		scanf ("%d", &m);
		v = 0;
		for (int i = 0; i < m; ++i){
			scanf ("%d", &u);
			v |= (1 << (u - 1));
		}
		v >>= 1;
		if (!m || (m == 1 && u == 1)){
			printf("Case %d: 0\n", ++count);
			continue;
		}
		bfs ();
		u = inf;
		w = (1 << (n-1)) - 1;
		for(int i = 1; i < (1 << n); ++i)
			for(int j = 0; j < n; ++j) 
				dis[i >> 1] = min(dis[i >> 1], dp[i][j]);		
		for (int i = 1; i <= w; ++i)
			for (int j = i; j; j = (j - 1) & i)
				num[i] = min(num[i], max(dis[j], dis[i ^ j]));
		for (int i = 1; i <= w; ++i)
			for(int j = i; j; j = (j - 1) & i)
			if((i & v) == v) u = min(u, max(num[j], dis[i ^ j]));
		if (u == inf) u = -1;
		printf("Case %d: %d\n", ++count, u);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/moyan_min/article/details/12032391