复兴提高班第二十一课 综合练习
2025-10-31 12:42:10
发布于：上海
2阅读
0回复
0点赞
T1请柬
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 9;
struct node {
long long v, w;
};
vector<node> ve[2][maxn];
long long d[maxn];
bool vis[maxn];
int n, m;
void dijkstra(int s) {
memset(d, 0x3f, sizeof(d));
memset(vis, 0, sizeof(vis));
d[1] = 0;
for (int i = 1; i < n; i++) {
int id = -1;
for (int j = 1; j <= n; j++) {
if (!vis[j]) {
if (id == -1 || d[id] > d[j]) id = j;
}
}
if (id == -1) break;
vis[id] = 1;
for (int j = 0; j < ve[s][id].size(); j++) {
int y = ve[s][id][j].v, w = ve[s][id][j].w;
if (d[y] > d[id] + w) {
d[y] = d[id] + w;
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
ve[0][u].push_back({ v,w });
ve[1][v].push_back({ u,w });
}
long long ans = 0;
dijkstra(0);
for (int i = 1; i <= n; i++) ans += d[i];
dijkstra(1);
for (int i = 1; i <= n; i++) ans += d[i];
cout << ans;
return 0;
}
T2山峰和山谷
#include<bits/stdc++.h>
using namespace std;
int a[1009][1009], n;
bool vis[1009][1009];
struct node {
int x, y;
}l,r;
int dir[8][2] = { -1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1,-1,-1 };
int peak, valley;
void bfs(int x, int y) {
queue<node> q;
q.push({ x,y });
vis[x][y] = 1;
bool high = false, low = false;
while (q.size()) {
r = q.front();
q.pop();
for (int i = 0; i < 8; i++) {
l.x = r.x + dir[i][0], l.y = r.y + dir[i][1];
if (l.x >= 1 && l.x <= n && l.y >= 1 && l.y <= n) {
if (a[l.x][l.y] > a[r.x][r.y]) high = 1;
else if (a[l.x][l.y] < a[r.x][r.y]) low = 1;
else {
if (!vis[l.x][l.y]) {
q.push({ l.x,l.y });
vis[l.x][l.y] = 1;
}
}
}
}
}
if (!high) peak++;
if (!low) valley++;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) cin >> a[i][j];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (!vis[i][j]) {
bfs(i, j);
}
}
}
cout << peak << " " << valley;
return 0;
}
T3兽径管理
#include<bits/stdc++.h>
using namespace std;
int fa[209], n, w, num[209];
struct node {
int u, v, w, id;
}a[6009];
bool cmp(node A, node B) {
return A.w < B.w;
}
int get(int x) {
if (fa[x] == x) return x;
return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
fa[get(x)] = get(y);
}
void solve(int up) {
for (int i = 1; i <= n; i++) fa[i] = i, num[i] = 0;
int ans = 0;
for (int i = 0; i < w; i++) {
if (a[i].id > up) continue;
if (get(a[i].u) == get(a[i].v)) continue;
merge(a[i].u, a[i].v);
ans += a[i].w;
}
for (int i = 1; i <= n; i++) num[get(i)]++;
for (int i = 1; i <= n; i++) {
if (num[i] == n) {
cout << ans << '\n';
return;
}
}
cout << -1 << '\n';
}
int main() {
cin >> n >> w;
for (int i = 0; i < w; i++) {
cin >> a[i].u >> a[i].v >> a[i].w;
a[i].id = i;
}
sort(a, a + w, cmp);
for (int i = 0; i < w; i++) solve(i);
return 0;
}
T4纪念品
#include<bits/stdc++.h>
using namespace std;
long long p[109][109], dp[10009];
int main() {
int T, N, M;
cin >> T >> N >> M;
for (int i = 1; i <= T; i++) {
for (int j = 1; j <= N; j++) cin >> p[i][j];
}
for (int i = 1; i < T; i++) {
memset(dp, 0, sizeof(dp));
for (int j = 1; j <= N; j++) {
for (int k = p[i][j]; k <= 10000; k++) {
dp[k] = max(dp[k], dp[k - p[i][j]] + p[i + 1][j] - p[i][j]);
}
}
M += dp[M];
}
cout << M << '\n';
}
T5摆花
#include<bits/stdc++.h>
using namespace std;
int a[109], dp[109][109];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= min(a[i], j); k++) {
dp[i][j] += dp[i - 1][j - k];
dp[i][j] %= 1000007;
}
}
}
cout << dp[n][m];
return 0;
}
T6棋盘
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int map[105][105],n,m,ans=0x3f3f3f3f,val[105][105];
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
struct node{
int x,y,c,v;
};
queue<node> q;
void bfs(){
q.push(node{1,1,map[1][1],0});
val[1][1]=0;
while(!q.empty()){
node n1=q.front();
q.pop();
if(n1.x==m && n1.y==m){
ans=min(ans,n1.v);
}
for(int i=1;i<=4;i++){
int x2=dx[i]+n1.x;
int y2=dy[i]+n1.y;
if(x2<1 || x2>m || y2<1 || y2>m) continue;
int c1=map[n1.x][n1.y],c2=map[x2][y2],v1=0;
if(c1>=0 && c2>=0){
if(c1==c2) v1=0;
else v1=1;
if(val[x2][y2]>n1.v+v1){
q.push({x2,y2,c2,n1.v+v1});
val[x2][y2]=n1.v+v1;
}
}else if(c1>=0 && c2<0){
if(val[x2][y2]>n1.v+2){
q.push({x2,y2,c1,n1.v+2});
val[x2][y2]=n1.v+2;
}
}else if(c1<0 && c2>=0){
if(n1.c==c2) v1=0;
else v1=1;
if(val[x2][y2]>n1.v+v1){
q.push({x2,y2,c2,n1.v+v1});
val[x2][y2]=n1.v+v1;
}
}
}
}
}
int main(){
memset(map,-1,sizeof map);
memset(val,0x3f,sizeof val);
cin>>m>>n;
for(int i=1;i<=n;i++){
int x,y,c;
cin>>x>>y>>c;
map[x][y]=c;
}
bfs();
if(ans==0x3f3f3f3f) cout<<-1;
else cout<<ans;
return 0;
}
有帮助，赞一个