本篇就PAT上图论相关习题做一个总结
Dijkstra
紧急情况
作为城市的紧急救援团队负责人，你将获得一张你所在国家的特殊地图。
该地图显示了一些通过道路连接的分散城市，道路是双向的。
地图上标出了每个城市的救援队数量以及每对城市之间的每条道路的长度。
当其他城市发出紧急求援信息时，你的工作是尽快带领你的士兵前往该地点，同时，在途中尽可能多地调动救援帮手。
输入格式
第一行包含四个整数 N，表示城市数量（城市编号从 0 到 N−1），M 表示道路数量，C1 表示你当前所在的城市编号，C2 表示发出紧急求援信息的城市编号。
第二行包含 N 个整数，其中第 i 个整数表示城市 i 的救援队数量。
接下来 M 行，每行包含三个整数 c1,c2,Li，表示城市 c1 和城市 c2 之间存在一条道路相连，道路长度为 Li。
数据保证 C1 和 C2 之间至少存在一条路径相连。
输出格式
共一行，两个整数，第一个整数表示 C1 和 C2 之间最短路的数量，第二个整数表示走最短路的情况下，能聚集到的救援队最大数量。
数据范围
2≤N≤500,
1≤M≤600,
1≤Li≤200,
每个城市包含的救援人员数量不超过 200。
输入样例：
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
输出样例：
2 4
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
const int M = 610;
int g[N][N];
bool st[N];
int dist[N], cnt[N], sum[N];
int w[N];
int n, m, S, T;
void dijkstra() {
memset(dist, 0x3f, sizeof dist);
dist[S] = 0;
cnt[S] = 1;
sum[S] = w[S];
for (int i = 0; i < n; i++) {
int t = -1;
// 在未加入的集合S中
for (int j = 0; j < n; j++) {
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
}
st[t] = true;
for (int j = 0; j < n; j++) {
// 如果被t更新，最短路径数量等于t的路径数量
if (dist[j] > dist[t] + g[t][j]) {
dist[j] = dist[t] + g[t][j];
cnt[j] = cnt[t];
sum[j] = sum[t] + w[j];
}
// 多条相同路径相同，把路径数量累加，并记录最大的救援人数
else if (dist[j] == dist[t] + g[t][j]) {
cnt[j] += cnt[t];
sum[j] = max(sum[j], sum[t] + w[j]);
}
}
}
}
int main() {
cin >> n >> m >> S >> T;
for (int i = 0; i < n; i++) {
cin >> w[i];
}
memset(g, 0x3f, sizeof g);
while (m--) {
int a, b, c;
cin >> a >> b >> c;
// 无向图 + 消除重复边
g[a][b] = g[b][a] = min(g[a][b], c);
}
dijkstra();
cout << cnt[T] << ' ' << sum[T] << endl;
return 0;
}
旅行计划
给定一张地图，包含 N 个城市，M 条高速公路。
城市之间都能相互连通。
每条高速公路的长度和走该条公路的花费都是已知的，高速公路都是双向的。
现在要从地图中的某个城市前往另一个城市。
请你确定最短路径，当最短路径不唯一时，请你选取花费最小的路径（保证唯一）。
输入格式
第一行包含四个整数 N,M,S,D，分别表示城市数量，公路数量，起点城市编号，终点城市编号。
城市编号从 0 到 N−1。
接下来 M 行，每行包含四个整数 a,b,c,d，表示城市 a 和城市 b 之间存在一条公路，长度为 c，花费为 d。
输出格式
共一行，首先输出从起点城市到终点城市的最短路径（花费最少的）经过的所有城市，然后输出最短路径的距离以及最小的花费。
数据范围
1≤N≤500,
1≤M≤600,
1≤c,d≤500
输入样例：
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
输出样例：
0 2 3 3 40
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 510;
int g[N][N], w[N][N];
int dist[N], cost[N];
int pre[N];
bool st[N];
vector<int> path;
int n, m , S, D;
void dijkstra () {
memset(dist, 0x3f, sizeof dist);
memset(cost, 0x3f, sizeof cost);
dist[S] = 0, cost[S] = 0;
for (int i = 0; i < n; i++) {
int t = -1;
for (int j = 0; j < n; j++) {
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
}
st[t] = true;
for (int j = 0; j < n; j++) {
// 每次更新j的时候，pre[j]记录前驱结点为t，最后将pre逆序输出就是路径
if (dist[j] > dist[t] + g[t][j]) {
dist[j] = dist[t] + g[t][j];
cost[j] = cost[t] + w[t][j];
pre[j] = t;
}
// 路径相等情况下，记录最小的开销
else if (dist[j] == dist[t] + g[t][j] && cost[j] > cost[t] + w[t][j]) {
cost[j] = cost[t] + w[t][j];
pre[j] = t;
}
}
}
}
int main() {
cin >> n >> m >> S >> D;
memset(g, 0x3f, sizeof g);
memset(w, 0x3f, sizeof w);
for (int i = 0; i < m; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
g[a][b] = g[b][a] = min(g[a][b], c);
w[a][b] = w[b][a] = min(w[a][b], d);
}
dijkstra();
// 输出路径
for (int i = D; i != S; i = pre[i])
path.push_back(i);
cout << S;
for (int i = path.size() - 1; i >= 0; i--) {
cout << ' ' << path[i];
}
cout << ' ' << dist[D] << ' ' << cost[D] << endl;
return 0;
}
条条大路通罗马
在线地图
输入我们的当前位置和目的地，在线地图就可以推荐一些行进路线。
现在你的工作是向用户推荐两条路线：一条是最短路线，另一条是最快路线。
保证任何询问的两地之间都存在至少一条路线。
输入格式
第一行包含两个整数 N 和 M，表示地图中共有 N 个路口（编号 0∼N−1）和 M 个街道。
接下来 M 行，每行描述一条街道，格式如下：
V1 V2 one-way length time
V1 和 V2 是两个路口的编号，表示这两个路口之间存在一条街道，one-way 如果为 1 则表示这条街道是单行道，只能从 V1 前往 V2。如果为 0 表示是双行道，可随意通行。 length 是街道的长度，time 是通过这条街道花费的时间。
最后一行，将给出起点和终点路口的编号。
输出格式
第一行输出路程最短的路线，并输出最短路程 D，格式如下：
Distance = D: source -> v1 -> ... -> destination
第二行输出用时最快的路线，并输出最短用时 T，格式如下：
Time = T: source -> w1 -> ... -> destination
如果最短路线不唯一，则输出用时最短的那条路线（保证唯一）。
如果最快路线不唯一，则输出经过路口最少的那条路线（保证唯一）。
如果最短路线和最快路线是同一条路线，则以如下格式将两个信息输出在一行：
Distance = D; Time = T: source -> u1 -> ... -> destination
数据范围
2≤N≤500,
1≤M≤N(N−1)2,
每条道路的长度和用时都不超过 1000
输入样例1:
10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
3 4 0 3 2
3 9 1 4 1
0 6 0 1 1
7 5 1 2 1
8 5 1 2 1
2 3 0 2 2
2 1 1 1 1
1 3 0 3 1
1 4 0 1 1
9 7 1 3 1
5 1 0 5 2
6 5 1 1 2
3 5
输出样例1：
Distance = 6: 3 -> 4 -> 8 -> 5
Time = 3: 3 -> 1 -> 5
输入样例2：
7 9
0 4 1 1 1
1 6 1 1 3
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 1 3
3 2 1 1 2
4 5 0 2 2
6 5 1 1 2
3 5
输出样例2：
Distance = 3; Time = 4: 3 -> 2 -> 5
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int N = 510;
int g1[N][N], g2[N][N];
int dist1[N], dist2[N], pre[N];
bool st[N];
int S, D;
int n, m;
pair<int, string> dijkstra(int d1[][N], int d2[][N], int type) {
memset(dist1, 0x3f, sizeof dist1);
memset(dist2, 0x3f, sizeof dist2);
memset(st, 0, sizeof st);
dist1[S] = 0;
dist2[S] = 0;
for (int i = 0; i < n; i++) {
int t = -1;
// 找到一个最小权值
for (int j = 0; j < n; j++) {
if (!st[j] && (t == -1 || dist1[t] > dist1[j]))
t = j;
}
st[t] = true;
for (int j = 0; j < n; j++) {
int w;
// 区分是哪种类型
if (type == 0)
w = d2[t][j];
else
w = 1;
if (dist1[j] > dist1[t] + d1[t][j]) {
dist1[j] = dist1[t] + d1[t][j];
dist2[j] = dist2[t] + w;
pre[j] = t;
} else if (dist1[j] == dist1[t] + d1[t][j]) {
if (dist2[j] > dist2[t] + w) {
dist2[j] = dist2[t] + w;
pre[j] = t;
}
}
}
}
pair<int, string> results;
vector<int> path;
for (int i = D; i != S; i = pre[i])
path.push_back(i);
results.first = dist1[D];
results.second = to_string(S);
for (int i = path.size() - 1; i >= 0; i--) {
results.second += " -> " + to_string(path[i]);
}
return results;
}
int main() {
cin >> n >> m;
memset(g1, 0x3f, sizeof g1);
memset(g2, 0x3f, sizeof g2);
while (m--) {
int v1, v2, way, length, times;
cin >> v1 >> v2 >> way >> length >> times;
if (way == 1) {
g1[v1][v2] = min(g1[v1][v2], length);
g2[v1][v2] = min(g2[v1][v2], times);
} else {
g1[v1][v2] = g1[v2][v1] = min(g1[v1][v2], length);
g2[v1][v2] = g2[v2][v1] = min(g2[v1][v2], times);
}
}
cin >> S >> D;
auto A = dijkstra(g1, g2, 0);
auto B = dijkstra(g2, g1, 1);
if (A.second == B.second) {
cout << "Distance = " << A.first << "; "
<< "Time = " << B.first << ": " << B.second << endl;
} else {
cout << "Distance = " << A.first << ": " << A.second << endl;
cout << "Time = " << B.first << ": " << B.second << endl;
}
return 0;
}
加油站
加油站的建造位置必须使加油站与距离它最近的房屋的距离尽可能远。
与此同时，它还必须保证所有房屋都在其服务范围内。
现在，给出了城市地图和加油站的几个候选位置，请你提供最佳建议。
如果有多个解决方案，请输出选取位置与所有房屋的平均距离最小的解决方案。
如果这样的解决方案仍然不是唯一的，请输出选取位置编号最小的解决方案。
输入格式
第一行包含四个整数 N，房屋总数，M，加油站的候选位置总数，K，连接房屋或加油站的道路总数，Ds 加油站的最大服务范围。
所有房屋的编号从 1 到 N，所有加油站侯选位置编号从 G1 到 GM。
接下来 K 行，每行格式如下：
P1 P2 Dist
其中，P1 和 P2 表示一条 无向 道路连接的两个房屋或加油站侯选位置的编号，Dist 是道路长度，这是一个整数。
输出格式
第一行输出所选位置的编号。
第二行输出加油站与距离其最近的房屋之间的距离以及与所有房屋之间的平均距离，精确到小数后一位。
如果解决方案不存在，则输出 No Solution。
数据范围
1≤N≤103,
1≤M≤10,
1≤K≤104,
1≤Ds≤200,
1≤Dist≤5000
输入样例1：
4 3 11 5
1 2 2
1 4 2
1 G1 4
1 G2 3
2 3 2
2 G2 1
3 4 2
3 G3 2
4 G1 3
G2 G1 1
G3 G2 2
输出样例1：
G1
2.0 3.3
输入样例2：
2 1 2 10
1 G1 9
2 G1 20
输出样例2：
No Solution
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1020;
const int INF = 0x3f3f3f3f;
int n, m, k, D;
int g[N][N];
int dist[N];
bool st[N];
// 对两种编号进行处理
int get(string s) {
if (s[0] == 'G')
return n + stoi(s.substr(1));
else
return stoi(s);
}
void dijkstra(int start, int& min_dist, int& sum_dist) {
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
dist[start] = 0;
for (int i = 0; i < n + m; i++) {
int t = -1;
for (int j = 1; j <= n + m; j++) {
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
}
st[t] = true;
for (int j = 1; j <= n + m; j++)
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
// 判断是否都在服务范围内
for (int i = 1; i <= n; i++) {
if (dist[i] > D) {
min_dist = -INF;
return;
}
}
min_dist = INF;
sum_dist = 0;
// 找到最近距离和总距离
for (int i = 1; i <= n; i++) {
min_dist = min(min_dist, dist[i]);
sum_dist += dist[i];
}
}
int main() {
cin >> n >> m >> k >> D;
memset(g, 0x3f, sizeof g);
while (k--) {
string a, b;
int c;
cin >> a >> b >> c;
int x = get(a);
int y = get(b);
g[x][y] = g[y][x] = min(g[x][y], c);
}
// 枚举每个加油站
// 记录加油站是否合适
int res = -1;
// 记录加油站距离最近房屋的最大值
int min_dist = 0;
// 记录总距离的最小值
int sum_dist = INF;
for (int i = n + 1; i <= n + m; i++) {
int d1, d2;
dijkstra(i, d1, d2);
if (d1 > min_dist) {
res = i;
min_dist = d1;
sum_dist = d2;
}
else if (min_dist == d1 && sum_dist > d2) {
res = i;
sum_dist = d2;
}
}
if (res == -1) {
cout << "No Solution" << endl;
}else{
cout << "G" << res - n << endl;
printf("%.1f %.1f\n", (double)min_dist, (double)sum_dist / n + 1e-8);
}
return 0;
}
DFS/BFS
团伙头目
警察找到团伙头目的一种方法是检查人们的通话。
如果 A 和 B 之间有通话，我们就说 A 和 B 是相关的。并且关联具有传递性，即如果 A 与 B 关联，B 与 C 关联，那么 A 与 C 也是关联的。
关联权重定义为两人之间所有通话的总时间长度。
一个“帮派”是一个由至少3个相互关联的人组成的群体，并且其总关联权重大于给定的阈值 K。
在每个帮派中，总权重最大的就是头目，数据保证每个帮派中总权重最大的人是唯一的。
你需要确定各个帮派以及帮派头目。
输入格式
第一行包含两个整数 N 和 K，表示通话数量以及权重阈值。
接下来 N 行，每行采用如下形式描述通话：
Name1 Name2 Time
Name1 和 Name2 是通话的两人的名字，Time 是通话时间。
名字的长度固定为 3，且只包含大写字母。
时间是一个不超过 1000 的正整数。
输出格式
第一行输出帮派数量。
接下来每行输出一个帮派的信息，包括帮派头目名字以及帮派人数。
帮派信息按头目名字字典序输出。
数据范围
1≤N,K≤1000
输入样例1：
8 59
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10
输出样例1：
2
AAA 3
GGG 3
输入样例2：
8 70
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10
输出样例2：
0
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
int n, k;
// 使用哈希表来存储图
unordered_map<string, vector<pair<string, int> > > g;
// 记录每个节点的总通话时间
unordered_map<string, int> total;
unordered_map<string, bool> st;
int dfs (string ver, vector<string>& nodes) {
st[ver] = true;
nodes.push_back(ver);
int sum = 0;
for (auto edge : g[ver]) {
sum += edge.second;
string cur = edge.first;
if (!st[cur])
sum += dfs(cur, nodes);
}
return sum;
}
int main() {
cin >> n >> k;
while (n--) {
string a, b;
int c;
cin >> a >> b >> c;
g[a].push_back({b, c});
g[b].push_back({a, c});
total[a] += c;
total[b] += c;
}
// 存储结果
vector<pair<string, int> > res;
// 遍历
for (auto item : total) {
string ver = item.first;
vector<string> nodes;
// 无向图我们使用的是两条有向边来存
// dfs遍历出来的权重我们需要 / 2
int sum = dfs(ver, nodes) / 2;
// 满足是团伙的要求
if (nodes.size() > 2 && sum > k) {
// 找出团队头目
string boss = nodes[0];
for (string node : nodes) {
if (total[node] > total[boss])
boss = node;
}
res.push_back({boss, nodes.size()});
}
}
// 按字典序排序
sort(res.begin(), res.end());
cout << res.size() << endl;
for (int i = 0; i < res.size(); i++) {
cout << res[i].first << ' ' << res[i].second << endl;
}
return 0;
}
微博转发
微博被称为中文版的 Twitter。
微博上的用户既可能有很多关注者，也可能关注很多其他用户。
因此，形成了一种基于这些关注关系的社交网络。
当用户在微博上发布帖子时，他/她的所有关注者都可以查看并转发他/她的帖子，然后这些人的关注者可以对内容再次转发…
现在给定一个社交网络，假设只考虑 L 层关注者，请你计算某些用户的帖子的最大可能转发量。
补充
如果 B 是 A 的关注者，C 是 B 的关注者，那么 A 的第一层关注者是 B，第二层关注者是 C。
输入格式
第一行包含两个整数，N 表示用户数量，L 表示需要考虑的关注者的层数。
假设，所有的用户的编号为 1∼N。
接下来 N 行，每行包含一个用户的关注信息，格式如下：
M[i] user_list[i]
M[i] 是第 i 名用户关注的总人数，user_list[i] 是第 i 名用户关注的 M[i] 个用户的编号列表。
最后一行首先包含一个整数 K，表示询问次数，然后包含 K 个用户编号，表示询问这些人的帖子的最大可能转发量。
输出格式
按顺序，每行输出一个被询问人的帖子最大可能转发量。
假设每名用户初次看到帖子时，都会转发帖子，只考虑 L 层关注者。
数据范围
1≤N≤1000,
1≤L≤6,
1≤M[i]≤100,
1≤K≤N
输入样例：
7 3
3 2 3 4
0
2 5 6
2 3 1
2 3 4
1 4
1 5
2 2 6
输出样例：
4
5
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int N = 1010;
vector<int> g[N];
int u[N];
int n, level;
bool st[N];
int bfs(int a) {
queue<int> q;
memset(st, 0, sizeof st);
q.push(a);
st[a] = true;
int cnt = 0;
int sum = 0;
// 限定层次的bfs搜索，sum记录人数
while(cnt < level) {
int sz = q.size();
sum += sz;
for (int i = 0; i < sz; i++) {
int t = q.front();
q.pop();
for (int j = 0; j < g[t].size(); j++) {
if (!st[g[t][j]]) {
st[g[t][j]] = true;
q.push(g[t][j]);
}
}
}
cnt++;
}
return q.size() + sum - 1;
}
int main() {
cin >> n >> level;
for (int i = 1; i <= n; i++) {
int k;
cin >> k;
while (k--) {
int a;
cin >> a;
g[a].push_back(i);
}
}
int k;
cin >> k;
while (k--) {
int query;
cin >> query;
cout << bfs(query) << endl;
}
return 0;
}
模拟
顶点覆盖
如果图中的一个顶点集合能够满足图中的每一条边都至少有一个端点在该集合内，那么这个顶点集合就是图的顶点覆盖。
现在给定一张图，以及若干个顶点集合，请你判断这些顶点集合是否是图的顶点覆盖。
输入格式
第一行包含两个整数 N 和 M，表示图中点和边的数量。
接下来 M 行，每行包含两个整数 a,b，表示点 a 和点 b 之间存在一条边。
点编号 0∼N−1。
然后包含一个整数 K，表示询问的顶点集合数量。
接下来 K 行，每行描述一组询问顶点集合，格式如下：
Nv V[1] V[2] … V[Nv]
Nv 是集合中点的数量，V[i] 是点的编号。
输出格式
每组询问输出一行结果，如果是顶点覆盖则输出 Yes，否则输出 No。
数据范围
1≤N,M≤104,
1≤K≤100,
1≤Nv≤N
输入样例：
10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 0
2 4
5
4 0 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2
输出样例：
No
Yes
Yes
No
No
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010;
int n, m;
bool st[N];
// 不存在图的遍历，我们只需要用结构体存储边
struct Edge {
int a, b;
}e[N];
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++)
cin >> e[i].a >> e[i].b;
int k;
cin >> k;
while (k--) {
int cnt;
cin >> cnt;
memset(st, 0, sizeof st);
while (cnt--) {
int x;
cin >> x;
st[x] = true;
}
int index = 0;
while (index < m) {
if (!st[e[index].a] && !st[e[index].b])
break;
index++;
}
if (index == m)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
最大团
在一个无向图中，如果一个顶点子集满足子集内的任意两个不同顶点之间都是相连的，那么这个顶点子集就被称为一个团。
如果一个团不能通过加入某个新的顶点来扩展成一个更大的团，那么该团就被称为最大团。
现在，你需要判断给定顶点子集能否构成一个最大团。
输入格式
第一行包含两个整数 Nv 和 Ne，分别表示无向图中点和边的数量。
接下来 Ne 行，每行包含两个整数 a,b，表示点 a 和点 b 之间存在一条边。
所有点的编号从 1 到 Nv。
再一行，包含整数 M，表示询问次数。
接下来 M 行，每行描述一个询问顶点子集，首先包含一个整数 K，表示子集包含点的数量，然后包含 K 个整数，表示 K 个不同顶点的编号。
一行中所有数字之间用一个空格隔开。
输出格式
每组询问在一行中输出一个结论。
如果给定子集是最大团，则输出 Yes，如果是一个团，但不是最大团，则输出 Not Maximal，如果根本不是团，则输出 Not a Clique。
数据范围
1≤Nv≤200,
1≤Ne≤Nv(Nv−1)2,
1≤M≤100,
1≤K≤Nv
输入样例：
8 10
5 6
7 8
6 4
3 6
4 5
2 3
8 2
2 7
5 3
3 4
6
4 5 4 3 6
3 2 8 7
2 2 3
1 1
3 4 3 6
3 3 2 1
输出样例：
Yes
Yes
Yes
Yes
Not Maximal
Not a Clique
#include <iostream>
#include <cstring>
using namespace std;
const int N = 210;
bool g[N][N], st[N];
int n, m;
int nodes[N];
bool check_cli (int k) {
// 注意这里枚举的方法
for (int i = 0; i < k; i++) {
for (int j = 0; j < i; j++)
if (!g[nodes[i]][nodes[j]])
return false;
}
return true;
}
bool check_max (int k) {
memset(st, 0, sizeof st);
for (int i = 0 ; i < k; i++) {
st[nodes[i]] = true;
}
for (int i = 1; i <= n; i++) {
if (!st[i]) {
bool success = true;
// 检查团能不能被继续扩展，如果可以继续扩展就不是最大团
for (int j = 0; j < k; j++) {
if (!g[i][nodes[j]]) {
success = false;
break;
}
}
if (success)
return false;
}
}
return true;
}
int main() {
cin >> n >> m;
memset(g, 0, sizeof g);
while (m--) {
int a, b;
cin >> a >> b;
g[a][b] = g[b][a] = true;
}
int cnt;
cin >> cnt;
while (cnt--) {
int k;
cin >> k;
for (int i = 0; i < k; i++)
cin >> nodes[i];
if (check_cli(k)) {
if (check_max(k))
cout << "Yes" << endl;
else
cout << "Not Maximal" << endl;
}else
cout << "Not a Clique" << endl;
}
return 0;
}
旅行商问题
“旅行商问题”是这样一个问题：“给出一个城市列表以及每对城市之间的距离，访问每个城市并返回原城市的最短路线是什么？”
这是组合优化中的一个 NP 难题，在运筹学和理论计算机科学中十分重要。
在此问题中，请你从给定的路径列表中找到最接近旅行商问题的解的路径。
输入格式
第一行包含两个整数 N 和 M，分别表示城市数量以及 无向图 中边的数量。
接下来 M 行，每行以 City1 City2 Dist 格式描述一条边，其中城市编号从 1 到 N，Dist 为正且不超过 100。
再一行包含一个整数 K，表示给定路径的数量。
接下来 K 行描述路径，格式为：
n C1 C2 … Cn
n 表示给定路径经过的城市的数目，Ci 是路径中经过的城市的编号。
输出格式
对于每个路径，在一行中输出 Path X: TotalDist (Description)。
其中 X 是路径编号（从 1 开始），TotalDist 表示路径总距离（如果距离不存在，则输出 NA），Description 是下列中的一项：
TS simple cycle，如果这是一个访问每个城市的简单回路。TS cycle，如果这是一个访问每个城市的回路，但不是简单回路。Not a TS cycle，如果这不是一个访问了每个城市的回路。
最后一行，输出 Shortest Dist(X) = TotalDist，X 是最接近旅行商问题解决方案的回路编号，TotalDist 是其总距离。
保证有唯一解。
数据范围
2<N≤200,
N−1≤M≤N(N−1)2，
1≤K≤1000,
1≤n≤300
输入样例：
6 10
6 2 1
3 4 1
1 5 1
2 5 1
3 1 8
4 1 6
1 6 1
6 3 1
1 2 1
4 5 1
7
7 5 1 4 3 6 2 5
7 6 1 3 4 5 2 6
6 5 1 4 3 6 2
9 6 2 1 6 3 4 5 2 6
4 1 2 5 1
7 6 1 2 5 4 3 1
7 6 3 2 5 4 1 6
输出样例：
Path 1: 11 (TS simple cycle)
Path 2: 13 (TS simple cycle)
Path 3: 10 (Not a TS cycle)
Path 4: 8 (TS cycle)
Path 5: 3 (Not a TS cycle)
Path 6: 13 (Not a TS cycle)
Path 7: NA (Not a TS cycle)
Shortest Dist(4) = 8
#include <iostream>
#include <cstring>
using namespace std;
const int N = 210;
const int INF = 0x3f3f3f3f;
int g[N][N];
bool st[N];
int vers[310];
int n, m;
int main() {
cin >> n >> m;
memset(g, 0x3f3f3f3f, sizeof g);
while (m--) {
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);
}
int k;
cin >> k;
int min_dist = INF;
int min_id;
for (int m = 1; m <= k; m++) {
int cnt;
cin >> cnt;
for (int i = 1; i <= cnt; i++)
cin >> vers[i];
int sum = 0;
bool success = true;
memset(st, 0, sizeof st);
// 判断距离是否存在，不存在就是fasle，总距离距离表示为-1
for (int i = 1; i + 1 <= cnt; i++) {
int a = vers[i], b = vers[i + 1];
if (g[a][b] == INF) {
sum = -1;
success = false;
break;
}else
sum += g[a][b];
st[a] = true;
}
// 判断每个点是否都能到
for (int i = 1; i <= n; i++) {
if (!st[i]) {
success = false;
break;
}
}
// 判断是否是回路
if (vers[1] != vers[cnt])
success = false;
if (sum == -1)
cout << "Path " << m << ":" << " NA (Not a TS cycle)" << endl;
else {
if (!success)
cout << "Path " << m << ": " << sum << " (Not a TS cycle)" << endl;
else {
if (cnt == n + 1)
cout << "Path " << m << ": " << sum << " (TS simple cycle)" << endl;
else
cout << "Path " << m << ": " << sum << " (TS cycle)" << endl;
if (min_dist > sum) {
min_dist = sum;
min_id = m;
}
}
}
}
cout << "Shortest Dist" << '(' << min_id << ") = " << min_dist << endl;
}
顶点着色
一个合适的顶点着色是指用各种颜色标记图中各个顶点，使得每条边的两个端点的颜色都不相同。
如果一种合适的顶点着色方案使用了一共 k 种不同的颜色，则称其为合适的 k 着色（k-coloring)。
现在，你需要判断给定的着色方案是否是合适的 k 着色方案。
输入格式
第一行包含两个整数 N 和 M，分别表示点和边的数量。
接下来 M 行，每行包含两个整数 a,b，表示点 a 和点 b 之间存在一条边。
所有点的编号从 0 到 N−1。
再一行包含一个整数 K，表示你需要判断的着色方案。
接下来 K 行，每行包含 N 个颜色，其中第 i 个颜色表示第 i 个点的颜色。
颜色用非负整数表示，不超过 int 范围。
输出格式
对于每种着色方案，如果是一种合适的 k 着色方案，则输出一行 k-coloring。
如果不是合适的着色方案，则输出一行 No。
数据范围
1≤N,M≤104,
1≤K≤100
输入样例：
10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 0
2 4
4
0 1 0 1 4 1 0 1 3 0
0 1 0 1 4 1 0 1 0 0
8 1 0 1 4 1 0 5 3 0
1 2 3 4 5 6 7 8 8 9
输出样例：
4-coloring
No
6-coloring
No
#include <iostream>
#include <cstring>
#include <unordered_set>
using namespace std;
const int M = 10010;
int n, m;
struct Edge {
int a;
int b;
}e[M];
int vers[M];
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> e[i].a >> e[i].b;
}
int k;
cin >> k;
while (k--) {
for (int i = 0; i < n; i++) {
cin >> vers[i];
}
bool success = true;
// 枚举每一条边
for (int i = 1; i <= m; i++) {
// 边的两个端点颜色相同就不是合适的着色方案
if (vers[e[i].a] == vers[e[i].b]) {
success = false;
break;
}
}
if (success) {
unordered_set<int> ss;
for (int i = 0; i < n; i++)
ss.insert(vers[i]);
cout << ss.size() << "-coloring" << endl;
}else
cout << "No" << endl;
}
return 0;
}
