pat 1034 :这是关于字符串转对应数字编号的经典题型(在图结构一般用编号代替节点id)

一点教训

1034

此题的困难就在怎么利用map,见注释

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
//该题使用人数代表编号,将字符串数字化,使用map<int , string> 和map<string , int>的映射解题
//而且,还利用到了map本身对字符串进行字典排序的特性,都很值得学习 *****
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <climits>
#define MAX 2010 //题目说明通话条数不少于1000条,那就是说人的个数是不少于2000条的
using namespace std;
//string G[MAX][MAX] = {"NULL"};
/*
struct node
{
int data;
string id;
vector<int> child;
}Node[MAX];
int n;
bool vis[MAX] = {false};
int count = 0 , cnt = 0;
void DFS(int root , int depth)
{
vis[root] = true;
++cnt;//计算顶点数
for(int i = 0 ; i < n ; ++i)
{
if(vis[i] == false && G[root][i] != "NULL")
{
vis[i] = true;
DFS(i , depth +1);
}
}
}
void DFSTravel()
{
for(int i = 'A' ; i <= 'Z'; ++i)
{
if(vis[i] == false)
{
DFS(i , 0);
cout<<cnt<<endl;
cnt = 0;
}
}
}
*/
map<int,string> intToString;//编号->姓名
map<string ,int> stringToInt; //姓名->编号
map<string ,int> TotalGang; //head->人数
vector<int> Gang;
int G[MAX][MAX] = {0} , weight[MAX] = {0}; //有边权的一般要使用邻接矩阵,还要注意二维数组的初始化方法
bool vis[MAX] = {false};
int n , k , numPerson = 0; //边数n,下限k,总人数numPerson
int numMem =0;//计算每个连通块的人数
int sum = 0;//计算每个连通块的权值之和
int max(vector<int> Gang)
{
int max = weight[Gang[0]] , index = 0;
//int i;
for(int i = 1; i < Gang.size() ; ++i)
{
if(max < weight[Gang[i]])
{
max = weight[Gang[i]];
index = i;
}
}
return index;
}
void DFS(int root , int depth)
{
vis[root] = true;
++numMem;
sum += weight[root];
Gang.push_back(root);
for(int i = 0 ; i < numPerson ; ++i)
{
if(vis[i] == false && G[root][i] != 0)
{
//sum += G[root][i];
DFS(i , depth+1);
}
}
}
int count = 0;//计算合格的连通分量数目
void DFSTravel()
{
for(int i = 0 ; i < n ; ++i)
{
if(vis[i] == false)
{
DFS(i , 0);
//cout<<numMem<<" "<<sum/2<<endl;
if(sum / 2 > k && numMem > 2)
{
++count;
int max_gang = max(Gang);
string max_name = intToString[Gang[max_gang]];
TotalGang[max_name] = numMem;
}
numMem = 0;
sum = 0;
Gang.clear();
}
}
}
//chang函数返回姓名str对应的编号(以人数作为编号,巧!)
int change(string str)
{
if(stringToInt.find(str) != stringToInt.end()) //如果str出现过
{
return stringToInt[str];
}
else
{
stringToInt[str] = numPerson; //str的编号为numPerson
intToString[numPerson] = str;
return numPerson++; //总人数+1
}
}
int main()
{
cin>>n>>k;
int i;
for(i = 0 ; i < n ; ++i)
{
string a , b;
int w;
cin>>a>>b>>w;
int id1 = change(a);
int id2 = change(b);
weight[id1] += w; //此处的输入也很吊
weight[id2] += w;
G[id1][id2] += w;
G[id2][id1] += w;
}
DFSTravel();
cout<<count<<endl;
for(map<string ,int>::iterator it = TotalGang.begin() ; it != TotalGang.end() ; ++it)
{
cout<<it->first<<" "<<it->second<<endl;
}
return 0;
}

热评文章