例题7-6 带宽

Posted on | In |

给出一个n个节点的图G和一个节点的排列，定义节点i的带宽b(i)为i和相邻节点在排列中最远的距离，而所有b(i)的最大值就是整个图的带宽。给定图G，求出让带宽最小的节点排列。

法一

暴力全排列就行了。
记录下当前已找到的最小带宽k

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
#include <cctype>
#include<iostream>
using namespace std;
 
const int MAX = 300;
const int INF = 0x3f3f3f3f;
char a[MAX];
vector<char> G[MAX];
 
int main(void)
{
    //freopen("s.txt","r",stdin);
    while(scanf("%s",a),a[0] != '#'){
    	cout<<a<<endl;
        for(int i = 'A'; i <= 'Z'; ++i)
            G[i].clear();
        vector<char> b;
        int n = strlen(a);
        for(int i = 0; i < n;++i){
            int s = a[i];
            b.push_back(s);
            G[s].clear();
            i += 2;
            while(isalpha(a[i])){
                G[s].push_back(a[i]);
                G[a[i]].push_back(s);
                b.push_back(a[i++]);
            }
 
        }
            for(vector<char>::iterator it=b.begin();it<b.end();it++)
			cout<<*it<<" ";
		cout<<endl;
        sort(b.begin(),b.end());
            for(vector<char>::iterator it=b.begin();it<b.end();it++)
			cout<<*it<<" ";
		cout<<endl;
        b.erase(unique(b.begin(),b.end()),b.end());
//        for(vector<char>::iterator it=b.begin();it<b.end();it++)
//			cout<<*it<<" ";
//		cout<<endl;
        vector<char> ans(b.size());
        int res = INF;
        do{
            int t = 0;
            for(int i = 0, sz = b.size(); i < sz; ++i){
                for(int j = 0, szz = G[b[i]].size(); j < szz; ++j)
                    t = max(t, abs(i -(int)(find(b.begin(),b.end(),G[b[i]][j]) - b.begin())));
            }
            if(t < res){
                res = t ;
                copy(b.begin(),b.end(),ans.begin());
            }
        }while(next_permutation(b.begin(),b.end()));
        for(int i = 0, sz = ans.size(); i < sz ; ++i)
            printf("%c ",ans[i]);
        printf("-> %d\n",res);
    }
    return 0;
}

法二

1.首先对字母进行散列，保存每个字符对应的编号，每个编号对应的字母。

2.不用暴力查找位置，而是直接记录位置，根据记录的位置直接求出结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<iostream>
#include<cstring>
#define INF 10000
using namespace std;
int main(){
	int id[256];
	int letter[20];
	char s[1000];
	while(scanf("%s",s)==1&&s[0]!='#'){
			int n=0;
	for(char ch='A';ch<='Z';ch++){
		if(strchr(s,ch)!=NULL){
		id[ch]=n;
		letter[n]=ch;
		n++;
			
		}

		
	}
	int p=0,q=0;
	vector<int> u,v;
	int len=strlen(s);

//!!!	for(int i=0;i<len;i++)
	while(1)
	{
		while(p<len&&s[p]!=':') p++;
		if(p==len) break;
		while(q<len&&s[q]!=';') q++;
		for(int k=p+1;k<q;k++){
			u.push_back(id[s[p-1]]);
			v.push_back(id[s[k]]);
			
		}
		p++;q++;
	}
//	for(vector<int>::iterator it=u.begin();it!=u.end();it++)
//	printf("%c ",letter[*it]);
//	cout<<endl;
//		for(vector<int>::iterator it=v.begin();it!=v.end();it++)
//	cout<<letter[*it]<<" ";
//	cout<<endl;
	int best_p[20];
	int pos[20];
	int num[20]; 
	for(int i=0;i<n;i++) num[i]=i;
		int	min=n;
	do{
	for(int i=0;i<n;i++) 	pos[num[i]]=i;
				int maxn=0;	
		for(int i=0;i<u.size();i++){
			maxn=max(maxn,abs(pos[u[i]]-pos[v[i]]));
		}
		if(min>maxn) 
		
		{
			min=maxn;
		 memcpy(best_p, num, sizeof(num));
		}
	}while(next_permutation(num,num+n));
	 for(int i=0;i<n;i++)
	 printf("%c ",letter[best_p[i]]);
	 printf("-> %d\n", min);			
	}
	return 0;
}

参考博客
https://blog.csdn.net/u013537860/article/details/49532053
https://blog.csdn.net/u012139398/article/details/39355601