L3-001 凑零钱
//背包问题求具体方案
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 7, M = 1e2 + 7;
int n, m;
int f[N][M], v[N];
bool st[N][M];
int main() {
//ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i];
sort(v + 1, v + 1 + n, greater<int>());
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = f[i - 1][j];
if (j >= v[i] && f[i][j] <= f[i - 1][j - v[i]] + v[i]) {
f[i][j] = f[i - 1][j - v[i]] + v[i];
st[i][j] = true;
}
}
}
if (f[n][m] == m) {
int j = m;
bool flag = false;
for (int i = n; i >= 1; i--) {
if (st[i][j]) {
if (flag) cout << ' ';
cout << v[i];
flag = true;
j -= v[i];
}
}
}
else cout << "No Solution" << endl;
return 0;
}
优化版
//背包问题求解具体方案
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 7, M = 1e2 + 7;
int n, m;
int f[N], v[N];
bool st[N][M];
int main() {
//ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i];
sort(v + 1, v + 1 + n, greater<int>());
for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--) {
if (f[j] <= f[j - v[i]] + v[i]) {
f[j] = f[j - v[i]] + v[i];
st[i][j] = true;
}
}
}
if (f[m] != m) return cout << "No Solution", 0;
int j = m;
bool flag = false;
for (int i = n; i >= 1; i--) {
if (st[i][j]) {
if (flag) cout << ' ';
cout << v[i];
j -= v[i];
flag = true;
}
}
return 0;
}
L3-3 社交集群 (并查集 + 排序)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 7;
int p[N], st[N], cnt[N], n; //st记录爱好第一次出现的人的下标
int find(int x)
{
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
void merge(int x, int y)
{
int fa = find(x), fb = find(y);
if (fa != fb) p[fa] = fb, cnt[fb] += cnt[fa];
}
int main()
{
cin.tie(nullptr)->ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) p[i] = i, cnt[i] = 1;
for (int i = 1; i <= n; i++) {
int k, x;
char c;
cin >> k >> c;
for (int j = 1; j <= k; j++) {
cin >> x;
if (st[x]) merge(i, st[x]);
else st[x] = i;
}
}
priority_queue<int, vector<int>, less<int>> q;
int ans = 0;
//遍历记录群体个数和数量
for (int i = 1; i <= n; i++) {
int k = find(i);
if (i == k) ans ++, q.push(cnt[k]);
}
cout << ans << endl;
if (!q.empty()) cout << q.top(), q.pop();
while (!q.empty()) {
auto t = q.top();
cout << ' ' << t;
q.pop();
}
return 0;
}
L3-004 肿瘤诊断
简单三维BFS
#include <bits/stdc++.h>
using namespace std;
const int N = 130, M = 1300;
const int dx[6] = {0, 1, 0, -1, 0, 0}, dy[6] = {-1, 0, 1, 0, 0, 0}, dz[6] = {0, 0, 0, 0, 1, -1};
int n, m, l, t, res;
int g[65][N][M];
bool st[65][N][M];
struct node {
int x, y, z;
};
void bfs(int x, int y, int z) {
int sum = 1;
queue<node> q;
q.push({x, y, z});
st[z][x][y] = true;
while (!q.empty()) {
auto t = q.front();
q.pop();
for (int i = 0; i < 6; i++) {
int a = t.x + dx[i], b = t.y + dy[i], c = t.z + dz[i];
if (a < 1 || a > n || b < 1 || b > m || c < 1 || c > l) continue;
if (st[c][a][b] || !g[c][a][b]) continue;
st[c][a][b] = true;
sum ++;
q.push({a, b, c});
}
}
if (sum >= t) res += sum;
}
int main() {
cin.tie(nullptr)->ios::sync_with_stdio(false);
cin >> n >> m >> l >> t;
for (int k = 1; k <= l; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[k][i][j];
}
}
}
for (int k = 1; k <= l; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (g[k][i][j] && !st[k][i][j])
bfs(i, j, k);
}
}
}
cout << res << endl;
return 0;
}
L3-11 直捣黄龙 (最短路)
算法
(堆优化dijkstra) $O(mlogn)$
思路
开两个哈希表 mp
和 name
分别映射town->id
id->town
dijkstra
维护路径条数、城镇数量、杀敌数量,以及节点前驱用来打印路径
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, M = 4 * N;
int n, m, start, End;
string f, l;
unordered_map<string, int> mp;
unordered_map<int, string> name;
int h[N], w[M], ne[M], e[M], idx;
int dist[N], path[N], killem[N], node[N], road[N], em[N];
bool st[N];
//d存最短路径,path存路径,killem存杀敌数,node存经过城市数量
//em存各城市的士兵,road存最短路数量
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dijkstra(int u) {
memset(dist, 0x3f, sizeof dist);
memset(path, -1, sizeof path);
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.emplace(0, u); //dist->sno
dist[u] = 0;
road[u] = 1; //初始化
while (!heap.empty()) {
auto t = heap.top();
heap.pop();
int ver = t.y, distance = t.x;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; ~i; i = ne[i]) {
int j = e[i];
if (st[j]) continue;
if (dist[j] > distance + w[i]) {
dist[j] = distance + w[i];
killem[j] = killem[ver] + em[j]; //j表示当前 ver表示先前
node[j] = node[ver] + 1; //前面经过的城市数 + 这个城市
path[j] = ver, road[j] = road[ver]; //更新当前结点前驱 以及路径条数
heap.emplace(distance + w[i], j);
} else if (dist[j] == distance + w[i]) { //若有别的路径距离一样
road[j] += road[ver]; //更新最快进攻路径的条数
//这时看解放城镇数量
if (node[j] < node[ver] + 1) {
node[j] = node[ver] + 1;
killem[j] = killem[ver] + em[j];
path[j] = ver;
} else if (node[j] == node[ver] + 1) {
//解放城镇数量相同则看杀敌数量
if (killem[j] < killem[ver] + em[j]) {
killem[j] = killem[ver] + em[j];
path[j] = ver;
}
}
}
}
}
}
void print(int x) {
if (path[x] != -1) {
print(path[x]);
cout << name[path[x]] << "->";
}
}
signed main() {
memset(h, -1, sizeof h);
cin >> n >> m >> f >> l;
mp[f] = 1, name[1] = f;
for (int i = 2; i <= n; i++) {
string town;
int enemy;
cin >> town >> enemy;
mp[town] = i; // mp映射 town -> idx
name[i] = town; //name映射 idx -> town
em[i] = enemy; //em[]存当前城镇 敌军数量
}
start = mp[f], End = mp[l];
while (m--) {
string a, b;
int l;
cin >> a >> b >> l;
int u = mp[a], v = mp[b];
add(u, v, l), add(v, u, l);
}
dijkstra(start);
print(End);
cout << l << endl;
cout << road[End] << ' ' << dist[End] << ' ' << killem[End] << endl;
return 0;
}