小琳在一个独特的游戏地图里，地图呈有根树结构，由 n 个关卡组成，起始关卡编号为 1 ，小琳初始就在关卡 1 。
地图每个最终关卡都有一个宝藏。部分关卡设有陷阱，若从有宝藏的关卡到起始关卡路径中，连续含陷阱的关卡超
过 m 个，小琳就拿不到该宝藏。已知哪些关卡有陷阱，求小琳能拿到的宝藏数量。
第一行包含两个整数 n 和 m （ 2 ≤ n ≤ 10e5 ， 1 ≤ m ≤ n ），分别代表游戏地图关卡数和小琳能容忍的连续含陷阱
关卡数。
第二行包含 n 个整数 a1, a2, ..., an ，其中每个 ai 要么等于 0 （关卡 i 没有陷阱），要么等于 1 （关卡 i 有陷阱）。
接下来的 n-1 行包含地图关卡连接关系，格式为 xi yi （ 1 ≤ xi ， yi ≤ n ， xi ≠ yi) ，其中 xi 和 yi 是关卡编号，表示这两
个关卡相连。
输出占一行，一个整数。代表小琳可以拿到的宝藏数。 
#include<bits/stdc++.h>
using namespace std;

const int N = 100005;

int s[N];

struct Node{
	int start, end;
};

vector<int>g[N];
int sum = 0;
int n, m;

void BFS(int start, int end, int cur){
	if(s[end] == 1){
		cur --;
	}
	if(s[end] == 0){
		cur = m;
	}
	
	if(cur < 0){
		return;
	}
	
	int num = g[end].size();
	if(num == 1 && end != 1){//只有1个相连的边， 肯定是叶子 
		sum ++; 
	}
	
	for(int i = 0; i < num; i ++){
		if(g[end][i] == start){//起点 
			continue;
		}
		else{
			BFS(end, g[end][i], cur);
		}
	}
	return;
}



int main(){
	while(cin>>n>>m){
		sum = 0;
		for(int i = 1; i <= n; i ++){
			g[i].clear();
		}
		for(int i = 1; i <= n; i ++){
			cin>>s[i];
		}
			for(int i = 0; i < n - 1; i ++){
		int x, y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	int count = 0;
	int cur = m;
	BFS(0, 1, cur);
	cout<<sum<<endl;
			
}//		
}

选课顺序 (拓扑排序)

Time Limit: 1000 ms | Memory Limit: 256 mb

【题目描述】 学校共有 n 门课程，编号为 1 ~ n。 给出 m 条先修关系，每条关系 a b 表示：课程 a 必须在课程 b 之前学习。

请你输出一种合法的选课顺序。 如果有多种合法顺序，输出字典序最小的那一种。 如果不存在合法顺序（即存在环），输出 -1。

【输入格式】 第一行输入两个整数 n, m。 接下来 m 行，每行两个整数 a, b。

【输出格式】

  • 如果存在合法顺序，输出 n 个整数，表示字典序最小的合法选课顺序，用空格隔开。

  • 否则输出 -1。

【数据范围】

  • 1 <= n <= 10^5

  • 0 <= m <= 2 * 10^5

  • 1 <= a, b <= n

  • a != b

【测试数据】 输入样例 1:

Plaintext 

4 3
1 2
1 3
3 4

输出样例 1:

Plaintext 

1 2 3 4

输入样例 2:

Plaintext 

3 3
1 2
2 3
3 1

输出样例 2:

Plaintext 

-1

输入样例 3:

Plaintext 

6 6
1 4
2 4
2 5
3 5
4 6
5 6

输出样例 3:

Plaintext 

1 2 3 4 5 6
#include<bits/stdc++.h>
using namespace std;

const int N = 20005;

vector<int>g[N];

int in[N] = {0};



int main(){
	int m, n;
	while(cin>>n>>m){
		for(int i = 1; i <= n; i ++){
			g[i].clear();
			in[i] = 0;
		}
		
		int a, b;
		for(int i = 0; i < m; i ++){
				cin>>a>>b;
				g[a].push_back(b);
				in[b] ++;
		}
		
		priority_queue<int, vector<int>, greater<int>>q;// 
		
		for(int i = 1; i <= n; i ++){
			if(in[i] == 0){
				q.push(i);
			}
		}
		
		vector<int>result;
		
		while(!q.empty()){
			int u = q.top();
			q.pop();
			
			result.push_back(u);
			
			for(int i = 0; i < g[u].size(); i ++){
				int v = g[u][i];
				in[v] --;
				if(in[v] == 0){
					q.push(v);
				}
			}
		}
		
		if(result.size() == n){
			for(int i = 0; i < result.size(); i ++){
				cout<<result[i]<<" ";
			}
			cout<<endl;
		}
		else{
			cout<<"-1"<<endl;
		}
		
		
		
	}
	
}

神奇的压缩编码
Time Limit: 1000 ms | Memory Limit: 256 mb

【题目描述】 小 Y 发明了一种字符串压缩规则。规则如下：k[S] 表示方括号内部的字符串 S 会被重复 k 次。其 中 k 是一个正整数，S 是一个由小写英文字母组成的字符串或另一个压缩字符串。 给定一个按照此规则压缩的字符串，请你输出解压后的完整字符串。保证输入合法，且解压后的 字符串长度不超过 100000。

【输入格式】 单组输入。输入一行压缩后的字符串，长度不超过 100。

【输出格式】 输出一行，表示解压后的字符串。

【输入输出样例】 输入样例 1: 3[a]2[bc]

输出样例 1: aaabcbc

输入样例 2: 3[a2[c]]

输出样例 2: accaccacc

输入样例 3: 2[abc]3[cd]ef

输出样例 3: abcabccdcdcdef

#include<bits/stdc++.h>
using namespace std;

int main(){
	
	string str;
	while(cin>>str){
		string cur_str = "";
		int cur_num = 0;
		
		stack<string>s;
		stack<int>num;
		
		for(int i = 0; i < str.size(); i ++){
			
			if(str[i] - '0' >= 0 && str[i] - '0' <= 9){//是数字 
				cur_num = cur_num * 10 + (str[i] - '0'); 
			}
			
			if(str[i] >= 'a' && str[i] <= 'z'){
				cur_str = cur_str + str[i];
			}
			
			if(str[i] == '['){//存档 
				s.push(cur_str);
				num.push(cur_num);
				cur_num = 0;
				cur_str = "";
			}
			
			if(str[i] == ']'){//读档 
				string str_top = s.top();
				s.pop();
				
				int temp = num.top();
				num.pop();
				
				for(int j = 0; j < temp; j ++){
					str_top = str_top + cur_str;
				}
				
				cur_str = str_top;
			}
		}
		cout<<cur_str<<endl;
	}
		
	

	
	
	
}

最短路径问题

 查看题解 查看答案

题目描述

Time Limit: 1000 ms
Memory Limit: 256 mb

给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

输入输出格式
输入描述:

输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点t。n和m为0时输入结束。 (1<n<=1000, 0<m<100000, s != t)

输出描述:

输出 一行有两个数， 最短距离及其花费。

输入输出样例
输入样例#:

复制

3 2
1 2 5 6
2 3 4 5
1 3
0 0
输出样例#:

复制

9 11
题目来源
浙江大学机试题
#include<bits/stdc++.h>
using namespace std;

const int N = 100005;
const long long INF = 100000005;

int dist[N];
int cost[N];
int visit[N];

struct Edge{
	int to, weight, cost;
};
vector<Edge>g[N];

struct Node{
	int id, dis;
	bool operator<(const Node& a)const{
		return a.dis < dis;
	}
};


int main(){
	
	int n, m;
	while(cin>>n>>m){
		if(n == 0 && m == 0){
			break;
		}
		
		for(int i = 1; i <= n; i ++){//初始化 
			dist[i] = INF;
			g[i].clear();
			visit[i] = 0;
		}
		
		for(int i = 0; i < m; i ++){//输入 
			int a, b, d, p;
			cin>>a>>b>>d>>p;
			g[a].push_back({b, d, p});
			g[b].push_back({a, d, p});
		}
		
		int start, end;
		cin>>start>>end;
		
		dist[start] = 0;
		cost[start] = 0;
		
		priority_queue<Node>q;
		q.push({start, 0});
		
		
		while(!q.empty()){
			Node cur=  q.top();
			q.pop();
			
			int u = cur.id;
			
			if(visit[u]){
				continue;
			}
			visit[u] = 1;
			
			for(int j = 0; j < g[u].size(); j ++){
				int v = g[u][j].to;
				int w = g[u][j].weight;
				int c = g[u][j].cost;
				
				if(dist[v] > dist[u] + w){//>
					dist[v] =  dist[u] + w;
					cost[v] = cost[u] + c;
					q.push({v, dist[v]});
				}
				else if(dist[v] == dist[u] + w){//=
					
					if(cost[v] > cost[u] + c){
						dist[v] = dist[u] + w;
						cost[v] = cost[u] + c;
						q.push({v, dist[v]});
					}
					
				}
			}//

		}
		cout<<dist[end]<<" "<<cost[end]<<endl;
		
		
		
}		
}//end

安全路径

 查看题解 查看答案

题目描述

Time Limit: 1000 ms
Memory Limit: 256 mb

卫斯理小说经常提及外星人，比如蓝血人。 在土星星球有很多城市，每个城市之间有一条或多条飞行通道， 但是并不是所有的路都是很安全的，每一条路有一个安全系数 s,s 是在 0和1 间的实数 (包括 0 ， 1) ，一条从 u 到 v 的通道 P 的安全度为 Safe(P) = s(e1)*s(e2)…*s(ek) e1,e2,ek是P 上的边 ，现在蓝血人想出去旅游，面对这这么多的路，他想找一条最安全的路。但是蓝血人的数学不好，想请你帮忙 ^_^ --

输入输出格式
输入描述:

输入包括多个测试实例，每个实例包括： 第一行： 一个整数 n。 n 表示城市的个数 n<=1000; 接着是一个 n*n 的矩阵表示两个城市之间的安全系数， (0可以理解为那两个城市之间没有直接的通道 )。 接着是一个整数m (m<=100)表示若干个蓝血人要旅游的路线 ,下面每行有两个数字，表示蓝血人所在的城市和要去的城市。

输出描述:

如果蓝血人无法达到他的目的地，输出 "What a pity!" ， 其他的输出这两个城市之间的最安全道路的安全系数，保留三位小数。

输入输出样例
输入样例#:

复制

3
1 0.5 0.5
0.5 1 0.4
0.5 0.4 1
3		
1 2
2 3
1 3
输出样例#:

复制

0.500
0.400
0.500
题目来源
中南大学机试题
#include<bits/stdc++.h>
using namespace std;

const int N = 1005;

double g[N][N];
int visit[N];
double dist[N];

int main(){

	int m, n;
	while(cin>>n){
		for(int i = 1; i <= n; i ++){
			for(int j = 1; j <= n; j ++){
				cin>>g[i][j];
			}
		}
	
		cin>>m;
		while(m --){
			int start, end;
			cin>>start>>end;
			
			for(int i = 1; i <= n; i ++){
				visit[i] = 0;
				dist[i] = 0;
			}
			
			
			int u = start;
			dist[start] = 1;
			
			
			for(int i = 0; i < n; i ++){
				double max_dist = 0;
				
				for(int j = 1; j <= n; j ++){//找最大的 , 变量别写传 
					if(!visit[j] && dist[j] > max_dist){
						max_dist = dist[j];
						u = j;
					}
				}
				
				if(visit[u]){//访问过 
					continue;
				}
				visit[u] = 1;//先标记
				
				
				for(int j = 1; j <= n; j ++){//在更新 
					if(dist[j] < dist[u] * g[u][j]){
						dist[j] = dist[u] * g[u][j];
					}
				}
				
			}
				
			if(dist[end] == 0){
				cout<<"What a pity!"<<endl;
			}
			else{
				printf("%.3f\n", dist[end]);
			}
			
		}


}//
}

连接村庄的最短路径

 查看题解 查看答案

题目描述

Time Limit: 1000 ms
Memory Limit: 256 mb

有一个乡镇有很多村子，政府要建设道路把所有村子连接起来，政府的目标是使任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的路程。现请你编写程序，计算出全部村庄连接起来需要的最短路径。

输入输出格式
输入描述:

测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M (N, M < =100 )；随后的 N 行对应村庄间道路的路程，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的路程（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。

输出描述:

对每个测试用例，在1行里输出全部村庄连接起来需要的最低成本。若统计数据不足以保证全部连接，则输出“?”。

输入输出样例
输入样例#:

复制

3 3
1 2 1
1 3 2
2 3 4
1 3
2 3 2
0 100
输出样例#:

复制

3
?
题目来源
华南师范大学2023年机试题

# 深度优先 # 算法
Logo
AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

006、检索篇：相似度算法、混合检索与重排序（Rerank）技术详解

召回阶段追求“全面”，重排序阶段追求“精准”。这是两个不同的优化目标。# 小型交叉编码器，比双塔模型更精准但更慢# 业务规则处理器（硬约束）"""返回重排序后的列表"""# 1. 交叉编码器计算精细相关度# 2. 业务规则调整（比如时效性、权威性）# 3. 综合打分（这个公式调了两个月...）'components': { # 保留各维度分数，调试用})# 按最终分数排序重排序模型的选择很关键。初

avatar AtomGit开源社区
cover

CVPR 2026 | 别人去噪要几十上百步，InvAD 只需 3 步反演：88 FPS 的扩散异常检测

avatar AtomGit开源社区
cover

【AI编程工具系列：第09篇】其他国外AI编程工具速览：Supermaven、Cody、Qodo、Replit AI等

avatar AtomGit开源社区