dfs算法第一次加训

用户11956880

发布于 2025-12-18 18:07:59

1190

今天先通过简单点的找手感,这些题都是dfs相关的不算难的题

P1030 [NOIP 2001 普及组] 求先序排列

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 ≤8）。

输入格式

共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

输出格式

共一行一个字符串，表示一棵二叉树的先序。

输入输出样例

输入 #1复制

BADC
BDCA

输出 #1复制

ABCD

思路

首先我们知道后序遍历的最后一个节点是根节点，我们就可以先利用这个性质得到整个树的根节点，其次中序遍历是左中右，后序遍历是左右中，看下面这个图

我们可以利用后序找到根节点，再利用中序遍历，找到这个根节点在中序中找到对应的根节点索引3，那中序的左子树就是substr（0,pos）,后序的左子树是substr(0,pos),中序的右子树就是substr(pos+1);(因为中间有个根，所以跳一个位置),后序的就是substr(pos,size()-pos-1)(总长减去左子树的长度-1，就是右子树的长度)，可能有些人会觉得这个长度就是pos，像题中给的样例

1，根节点为 A，左子树中序长度 1（B），右子树中序长度 3（D C E）。

2，后序右子树必须截取 post.substr(1, 3)（即 D E C），若错误使用 pos=1 直接分割，则只能截取 D，导致右子树丢失。

接下来看代码就行了应该

#include<bits/stdc++.h> 
using namespace std;
string pre;
void dfs(string in ,string post){
	if(in.size()==0) return ;
	char root=post.back();
	pre+=root;
	int pos=in.find(root);//找到root对应的索引 
	dfs(in.substr(0,pos),post.substr(0, pos));//构成左子树，从后序的左子树里面找最后一个节点，root 
	dfs(in.substr(pos+1),post.substr(pos,post.size()-pos-1)); //构成右子树，从后序的右子树里找最后一个节点，root 
}
int main(){
    string in,post;
    cin>>in>>post;
    dfs(in,post);
    cout<<pre;
}

P1036 [NOIP 2002 普及组] 选数

题目描述

已知 n 个整数 x1,x2,⋯,xn，以及 1 个整数 k（k<n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k=3，4 个整数分别为 3,7,12,19 时，可得全部的组合与它们的和为：

3+7+12=22

3+7+19=29

7+12+19=38

3+12+19=34

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：3+7+19=29。

输入格式

第一行两个空格隔开的整数 n,k（1≤n≤20，k<n）。

第二行 n 个整数，分别为 x1,x2,⋯,xn（1≤xi≤5×106）。

输出格式

输出一个整数，表示种类数。

输入输出样例

输入 #1复制

4 3
3 7 12 19

输出 #1复制

思路

两个方法

一是选或不选

#include <iostream>
#include <vector>
using namespace std;

int n, k, result = 0;
vector<int> nums;

bool is_prime(int x) {
    if (x <= 1) return false;
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) return false;
    }
    return true;
}

void dfs(int p, int sum, int selected) {
    if (p == n) {
        if (selected == k && is_prime(sum)) result++;
        return;
    }
    dfs(p + 1, sum + nums[p], selected + 1); // 选当前元素
    dfs(p + 1, sum, selected);               // 不选当前元素
}

int main() {
    cin >> n >> k;
    nums.resize(n);
    for (int i = 0; i < n; ++i) cin >> nums[i];
    dfs(0, 0, 0);
    cout << result << endl;
    return 0;
}

说一下我对这个题理解，k 要是3的话就相当于找三个数去相加嘛，也就是三个for循环去相加

for + for + for 然后看满足不满足，第一个for从i开始，第二个就从i+1开始，第三个就是i+2，然后一直遍历都最后

#include<bits/stdc++.h>
using namespace std;
const int N=20+10;
int k,n,result;
int arr[N];
bool isPrime(int num) {
   if (num <= 1) return false;
       if (num == 2) return true;
       if (num % 2 == 0) return false;
       for (int i = 3; i * i <= num; i += 2) {
           if (num % i == 0) return false;
       }
       return true;
   }
void dfs(int start,int count,int sum) {
    if (count==k) {
        if(isPrime(sum))result++;
        return;
    }
    for (int i=start;i<n;i++)  dfs(i+1,count+1,sum+arr[i]);
}
int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++) scanf("%d",&arr[i]);
	dfs(0,0,0);
	cout<<result;
}

P1294 高手去散步

题目描述

鳌头山上有 n 个观景点，观景点两两之间有游步道共 m 条。高手的那个它，不喜欢太刺激的过程，因此那些没有路的观景点高手是不会选择去的。另外，她也不喜欢去同一个观景点一次以上。而高手想让他们在一起的路程最长（观景时它不会理高手），已知高手的穿梭机可以让他们在任意一个观景点出发，也在任意一个观景点结束。

输入格式

第一行，两个用空格隔开的整数 n 、 m. 之后 m 行，为每条游步道的信息：两端观景点编号、长度。

输出格式

一个整数，表示他们最长相伴的路程。

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

对于 100% 的数据：n≤20，m≤50，保证观景点两两之间不会有多条游步道连接。

思路

就是直接先遍历每一个景点，然后都dfs一遍，看看从哪个景点走，时间呆的最长，又因为走过的路线力度景点不能重复，用一个visited数组维护一下子，dfs里面遍历一遍图就好，看代码就行

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<vector<pair<int, int>>>graph;  // 邻接表：存储相邻节点及边权
int max_sum = 0;
void dfs(int u, int sum, vector<bool>& visited) {
    max_sum = max(max_sum, sum);  //利用全局变量，持续更新最大值 
    // 遍历当前节点的所有邻接节点1
    for (auto& edge:graph[u]){
        int v=edge.first;
        int w=edge.second;
        if (!visited[v]){//没有访问过就继续访问 
            visited[v]=true;
            dfs(v,sum+w,visited);  // 递归访问下一个节点
            visited[v]=false;        // 回溯，恢复节点状态
        }
    }
}
int main(){
    cin>>n>>m;
    graph.resize(n+1);// 节点编号从1到n
    // 构建邻接表（无向图）
    for (int i=0;i<m;i++) {
        int u,v,w;
        cin>>u>>v>>w;
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, w);
    }
    //可以在任意景点开始走，所以遍历所有景点 
    for(int u=1;u<=n;u++) {
        vector<bool>visited(n + 1,false);
        visited[u]=true; // 标记起点已访问
        dfs(u,0,visited); // 初始路径和为0
    }
    cout<<max_sum<<endl;
    return 0;
}

P1331 海战

题目描述

在一个方形的盘上，放置了固定数量和形状的船只，每只船却不能碰到其它的船。在本题中，我们认为船是方形的，所有的船只都是由图形组成的方形。

求出该棋盘上放置的船只的总数。

输入格式

第一行为两个整数 R 和 C，用空格隔开，分别表示游戏棋盘的行数和列数。

接下来 R 行，每行 C 个字符，为 # 或 .。# 表示船只的一部分，. 表示水。

输出格式

一行一个字符串，如果船的位置放得正确（即棋盘上只存在相互之间不能接触的方形，如果两个 # 号上下相邻或左右相邻却分属两艘不同的船只，则称这两艘船相互接触了）。就输出 There are S ships.，S 表示船只的数量。否则输出 Bad placement.。

输入输出样例

输入 #1复制

6 8
.....#.#
##.....#
##.....#
.......#
#......#
#..#...#

输出 #1复制

There are 5 ships.

说明/提示

对于 100% 的数据，1≤R,C≤1000。

思路

如果遇到不是矩形的一团船聚一起，那就输出Bad placement.，否则就输出有几团船，这也是典型的洪水填充，其实只要搞一个check检查这堆船是不是矩形就是最重要的（我感觉），其他的洪水填充看看代码就好，，，我在题解中用visited数组来判断这个格子是否已经走过，其实也可以直接将#随便改成一个字符，都行

#include <bits/stdc++.h>
using namespace  std;
int num;
int c,l;
const int N=1020;
bool visited[N][N]={false};
void dfs(vector<string>& grid, int i, int j) {  
    if (i < 0 || j < 0 || i >= c || j >= l || grid[i][j] != '#' || visited[i][j]) {  
        return;  
    } 
    visited[i][j] = true; 
    dfs(grid, i + 1, j); 
    dfs(grid, i - 1, j); 
    dfs(grid, i, j + 1); 
    dfs(grid, i, j - 1); 
}  
bool check(vector<string>& grid,int i,int j){
	int x=0;
    if(grid[i][j]=='#') x++;
    if(grid[i][j+1]=='#') x++;
    if(grid[i+1][j]=='#') x++;
    if(grid[i+1][j+1]=='#') x++;
    if(x==3) return false;
    return true;
}
int main() {
     cin>>c>>l; 
	 vector<string> grid(N);
    for(int i=0;i<c;i++) {
        cin>>grid[i];
    }
    
    for(int i=0;i<c;i++)
    for(int j=0;j<l;j++){
		if(i<c&&j<l&&!check(grid,i,j)){
			cout<<"Bad placement.";
			return 0;
		}
	}
	
    for (int i=0;i<c;i++) {
        for (int j=0;j<(int)grid[i].size();j++) {
            if (grid[i][j]=='#'&&visited[i][j]==false) {
                   dfs(grid,i,j);
                num++;
            }
        }
    }
    cout<<"There are "<<num<<" ships.";
}

P1451 求细胞数量

题目描述

一矩形阵列由数字 0 到 9 组成，数字 1 到 9 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。

输入格式

第一行两个整数代表矩阵大小 n 和 m。

接下来 n 行，每行一个长度为 m 的只含字符 0 到 9 的字符串，代表这个 n×m 的矩阵。

输出格式

一行一个整数代表细胞个数。

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

数据规模与约定

对于 100% 的数据，保证 1≤n,m≤100。

思路

跟上题几乎没区别，还少了个check，直接拿上个代码搬过来就好，改一下条件就行

#include <bits/stdc++.h>
using namespace  std;
int num;
int c,l;
const int N=1020;
bool visited[N][N]={false};
void dfs(vector<string>& grid, int i, int j) {  
    if (i < 0 || j < 0 || i >= c || j >= l || grid[i][j]<='0'||grid[i][j]>'9'|| visited[i][j]) {  
        return;  
    } 
    visited[i][j] = true; 
    dfs(grid, i + 1, j); 
    dfs(grid, i - 1, j); 
    dfs(grid, i, j + 1); 
    dfs(grid, i, j - 1); 
}  
int main() {
     cin>>c>>l; 
	 vector<string> grid(N);
    for(int i=0;i<c;i++) {
        cin>>grid[i];
    }
    for (int i=0;i<c;i++) {
        for (int j=0;j<grid[i].size();j++) {
            if (grid[i][j]>'0'&&grid[i][j]<='9'&&visited[i][j]==false) {
                   dfs(grid,i,j);
                num++;
            }
        }
    }
    cout<<num;
}

P1460 [USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins

题目描述

农民 John 以拥有世界上最健康的奶牛为傲。他知道每种饲料中所包含的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛，以保持它们的健康，使喂给牛的饲料的种数最少。

给出牛所需的最低的维他命量，输出喂给牛需要哪些种类的饲料，且所需的饲料剂量最少。

维他命量以整数表示，每种饲料最多只能对牛使用一次，数据保证存在解。

输入格式

第一行一个整数 v，表示需要的维他命的种类数。第二行 v 个整数，表示牛每天需要的每种维他命的最小量。

第三行一个整数 g，表示可用来喂牛的饲料的种数。下面 g 行，第 n 行表示编号为 n 饲料包含的各种维他命的量的多少。

输出格式

输出文件只有一行，包括牛必需的最小的饲料种数 p；后面有 p 个数，表示所选择的饲料编号（按从小到大排列）。

如果有多个解，输出饲料序号最小的（即字典序最小）。

输入输出样例

输入 #1复制

4
100 200 300 400
3
50  50  50  50
200 300 200 300
900 150 389 399

输出 #1复制

2 1 3

说明/提示

【数据范围】对于 100% 的数据，1≤v≤25，1≤g≤15。输入的所有整数在 [1,1000] 范围内。

USACO 2.1

翻译来自NOCOW

思路

先说一下题是干啥的，就是给你个need数组（牛牛需要v个种类的维生素，数组里面是每个维生素需要的数量），再给g个种类的饲料，然后每个饲料里包含v个种类维生素，每个维生素的数量，这一眼就是dfs，对每个饲料判断选或不选，，总思路就是这了，具体在下面代码里

#include<bits/stdc++.h>
using namespace std;
const int N=25+10;
int vitamin[N][N]={0},need[N]={0},res[N],visited[N];//第一个数组每个种类的饲料里含有的维他命种类 
//第二个是牛牛们所需要的每个维他命种类 
int v,g,ans=N;
bool check(int cnt){
	if(cnt==0) return false;//如果最后啥也没选，那肯定是错的
	for(int i=1;i<=v;i++){//不要忘了v是维他命的数量 
		int sum=0;//sum是来选的饲料里，第i个维他命种类的的数量 
		for(int j=1;j<=g;j++){//g是饲料的种类数量 
			sum+=vitamin[visited[j]][i]; 
		}
		if(sum<need[i]) return false;//如果其中有一个不符合，就false等之后看看能不能dfs搜索下去了 
	}
	return true; 
}
void dfs(int num,int cnt){
	if(num>g) return ;//当每个饲料都已经经历过选或不选后，就return
	if(check(cnt)){
		if(cnt<ans){
			ans=cnt;
			for(int i=1;i<=cnt;i++) res[i]=visited[i];
		}
		return ;//这条路线走成功了，不能继续走下去，继续走下去那就可能会增加ans的 
	} 
	//接下来dfs就是判断选或不选这个饲料了
	//1. 如果选
	visited[cnt+1]=num+1;//选的第num+1号饲料，就是我们第cnt+1个选的饲料，记录在visited数组里
	dfs(num+1,cnt+1);//cnt+1就代表选这个了
	
	visited[cnt+1]=0;//当这个路经历完后，我们要回溯，把选的第cnt+1个饲料的编号改为0，代表我们没选 
	//2. 如果不选
    dfs(num+1,cnt);//cnt没加1就是我们跳过num+1号饲料 
}
int main(){
	cin>>v;
	for(int i=1;i<=v;i++) cin>>need[i];
	cin>>g;
	for(int i=1;i<=g;i++)//g个种类的饲料 
	for(int j=1;j<=v;j++)//每个饲料共有v个种类的维他命 
	cin>>vitamin[i][j];
	dfs(0,0);//从第0个种类开始，因为第一个种类也要面临选或不选的情况，第二个参数是当前选了多少个种类的饲料
	 //也就是已投喂的饲料总数 
	cout<<ans<<' ';
	for(int i=1;i<=ans;i++) cout<<res[i]<<' ';
}

P1498 南蛮图腾

题目描述

给定一个正整数 n，参考输出样例，输出图形。

输入格式

每个数据输入一个正整数 n，表示图腾的大小（此大小非彼大小）

输出格式

这个大小的图腾

输入输出样例

输入 #1复制

输出 #1复制

   /\
  /__\
 /\  /\
/__\/__\

输入 #2复制

输出 #2复制

       /\
      /__\
     /\  /\
    /__\/__\
   /\      /\
  /__\    /__\
 /\  /\  /\  /\
/__\/__\/__\/__\

说明/提示

数据保证，1≤n≤10。

思路

直接暴力递归就好，n最大就是10，下面是题解

#include<bits/stdc++.h>
using namespace std;
char mp[1030][2050];   //存储答案
int n;
void dr(int x,int y,int deep){      
  //x,y表示图形的第一个“/”的坐标   
//deep表示所需图形的大小
    if(deep==1){                 
        mp[x][y]='/';
        mp[x][y+1]='\\';
        mp[x+1][y-1]='/';
        mp[x+1][y]='_';
        mp[x+1][y+1]='_';
        mp[x+1][y+2]='\\'; 
        return;
    }
    dr(x,y,deep-1);    //画出中间那个  //递归分别画三个部分
    dr(x+(1<<(deep-1)),y-(1<<(deep-1)),deep-1);//画出左侧的那个 
    dr(x+(1<<(deep-1)),y+(1<<(deep-1)),deep-1);//画出右侧那个 
}
int main(){
    cin>>n;
    for(int i=1;i<=(1<<n);i++){         
        for(int j=1;j<=(1<<(n+1));j++)
        mp[i][j]=' ';
    }
    dr(1,1<<n,n);
    for(int i=1;i<=(1<<n);i++){             
        for(int j=1;j<=(1<<(n+1));j++)
        cout<<mp[i][j];
        cout<<endl;
    }
}

P1506 拯救oibh总部

题目描述

oibh 被突来的洪水淹没了，还好 oibh 总部有在某些重要的地方起一些围墙。用 * 号表示，而一个四面被围墙围住的区域洪水是进不去的。

oibh 总部内部也有许多重要区域，每个重要区域在图中用一个 0 表示。

现在给出 oibh 的围墙建设图，问有多少个没被洪水淹到的重要区域。

输入格式

第一行为两个正整数 x,y。

接下来 x 行，每行 y 个整数，由 * 和 0 组成，表示 oibh 总部的建设图。

输出格式

输出没被水淹没的 oibh 总部的 0 的数量。

输入输出样例

输入 #1复制

输出 #1复制

输入 #2复制

5 5
*****
*0*0*
**0**
*0*0*
*****

输出 #2复制

说明/提示

对于 100% 的数据，1≤x,y≤500。

思路

这题也是很简单，就很简单的洪水填充，不多说直接看代码吧

#include<bits/stdc++.h>
using namespace std;
int x,y;

void dfs(int i,int j,vector<string>& grid){
	if(i<0||j<0||i==x||j==y||grid[i][j]!='0') return;
	grid[i][j]='#';
	dfs(i-1,j,grid);
	dfs(i+1,j,grid);
	dfs(i,j-1,grid);
	dfs(i,j+1,grid);
}
int main(){
	cin>>x>>y;
	vector<string> grid(x);
	for(int i=0;i<x;i++){
		cin>>grid[i];
	}
	//题上要找被*包围的0,有几个，换个说法，就是看有几个0是没有被外围的0相连
	//我们只要从外面那层0开始dfs然后让外面那些0都变成#，然后最后遍历一遍数数有几个0就好
	//开始操作
	for(int j=0;j<y;j++){
		if(grid[0][j]=='0') dfs(0,j,grid);
	} 
	for(int j=0;j<y;j++){
		if(grid[x-1][j]=='0') dfs(x-1,j,grid);
	}
	for(int i=0;i<x;i++){
		if(grid[i][0]=='0') dfs(i,0,grid);
	}
	for(int i=0;i<x;i++){
		if(grid[i][y-1]=='0') dfs(i,y-1,grid);
	}
	int num=0;
	for(int i=0;i<x;i++){
		for(int j=0;j<y;j++){
			if(grid[i][j]=='0') num++;
		}
	}
	cout<<num;
}

P1596 [USACO10OCT] Lake Counting S

题目描述

由于最近的降雨，水在农夫约翰的田地里积聚了。田地可以表示为一个 N×M 的矩形（1≤N≤100；1≤M≤100）。每个方格中要么是水（'W'），要么是干地（'.'）。农夫约翰想要弄清楚他的田地里形成了多少个水塘。一个水塘是由连通的水方格组成的，其中一个方格被认为与它的八个邻居相邻。给定农夫约翰田地的示意图，确定他有多少个水塘。

输入格式

第 1 行：两个用空格分隔的整数：N 和 M。* 第 2 行到第 N+1 行：每行 M 个字符，表示农夫约翰田地的一行。每个字符要么是 'W'，要么是 '.'。字符之间没有空格。

输出格式

第 1 行：农夫约翰田地中的水塘数量。

显示翻译

题意翻译

输入输出样例

输入 #1复制

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

输出 #1复制

说明/提示

输出详情：共有三个水塘：一个在左上角，一个在左下角，还有一个沿着右侧。（由 ChatGPT 4o 翻译）

思路

依旧洪水填充，只不过多了四个角的dfs加上就行，不多说，看代码

#include<bits/stdc++.h>
using namespace std;
int x,y;

void dfs(int i,int j,vector<string>& grid){
	if(i<0||j<0||i==x||j==y||grid[i][j]!='W') return;
	grid[i][j]='#';
	dfs(i-1,j,grid);
	dfs(i+1,j,grid);
	dfs(i,j-1,grid);
	dfs(i,j+1,grid);
	dfs(i-1,j-1,grid);
	dfs(i-1,j+1,grid);
	dfs(i+1,j-1,grid);
	dfs(i+1,j+1,grid);
}
int main(){
	cin>>x>>y;
	vector<string> grid(x);
	for(int i=0;i<x;i++){
		cin>>grid[i];
	}
	int num=0;
	for(int i=0;i<x;i++){
		for(int j=0;j<y;j++){
			if(grid[i][j]=='W') dfs(i,j,grid),num++;
		}
	}
	cout<<num;
}

P1677 [USACO18FEB] Hoofball B

题目描述

为了准备即将到来的蹄球锦标赛，Farmer John 正在训练他的 N 头奶牛（方便起见，编号为 1…N，其中 1≤N≤100）进行传球。这些奶牛在牛棚一侧沿直线排列，第 i 号奶牛位于距离牛棚 xi 的地方（1≤xi≤1000）。每头奶牛都在不同的位置上。

在训练开始的时候，Farmer John 会将若干个球传给不同的奶牛。当第 i 号奶牛接到球时，无论是从 Farmer John 或是从另一头奶牛传来的，她会将球传给最近的奶牛（如果有多头奶牛与她距离相同，她会传给其中距左边最远的那头奶牛）。为了使所有奶牛都有机会练习到传球，Farmer John 想要确保每头奶牛都持球至少一次。帮助他求出为了达到这一目的他开始时至少要传出的球的数量。假设他在开始的时候能将球传给最适当的一组奶牛。

输入格式

输入的第一行包含 N。第二行包含 N 个用空格分隔的整数，其中第 i 个整数为 xi。

输出格式

输出 Farmer John 开始的时候最少需要传出的球的数量，使得所有奶牛至少持球一次。

输入输出样例

输入 #1复制

5
7 1 3 11 4

输出 #1复制

说明/提示

在上面的样例中，Farmer John 应该将球传给位于 x=1 的奶牛和位于 x=11 的奶牛。位于 x=1 的奶牛会将她的球传给位于 x=3 的奶牛，在此之后这个球会在位于 x=3 的奶牛和位于 x=4 的奶牛之间来回传递。位于 x=11 的奶牛会将她的球传给位于 x=7 的奶牛，然后球会被传给位于 x=4 的奶牛，在此之后这个球也会在位于 x=3 的奶牛和位于 x=4 的奶牛之间来回传递。这样的话，所有的奶牛都会至少一次接到球（可能从 Farmer John，也可能从另一头奶牛）。

可以看出，不存在这样一头奶牛，Farmer John 可以将球传给她之后所有奶牛最终都能被传到球。

思路

这题我看的题解鹅鹅鹅鹅鹅，说一下题解吧，，，就是先排序然后，，有n头牛站成一排，每头牛都有一个编号ai，现在每头牛要选择将球传给它左右两边中距离它最近的牛（距离相等则选择左边）。要求统计最终没有收到任何球的牛的数量。剩下的直接看代码吧，代码很详细都有注释

#include <bits/stdc++.h>
using namespace std;
//a[0]=-INF,a[n+1]=INF;设置哨兵,在数组的两端添加极小值和极大值,方便后续计算距离时不用考虑边界情况。  
const int N=110,INF=2e9;
int n,res,a[N],to[N],cnt[N];
int main(){
    scanf("%d",&n);
    a[0]=-INF,a[n+1]=INF;
    for(int i=1;i<=n; i ++ )
        scanf("%d",&a[i]);
    sort(a+1,a+1,+n);
    // 模拟传球
    //  遍历每头牛，确定其传球的目标。  
	// if(a[i]-a[i-1]<=a[i+1]-a[i]) 判断左边的牛和右边的牛哪个离它更近。如果到左边的距离小于等于到右边的距离，则传给左边的牛。  
	// cnt[i-1]++,to[i]=i-1;左边的牛收到的球的数量加1，记录第i头牛传给了第i-1头牛。  
	// else cnt[i+1]++,to[i]=i+1;否则，传给右边的牛，并更新 `cnt` 和 `to`。  
    for(int i=1;i<=n;i++){
        if(a[i]-a[i-1]<=a[i+1]-a[i])
            cnt[i-1]++,to[i]=i-1;
        else
            cnt[i+1]++,to[i]=i+1;
    }
    // 记录没有牛会给它传球的牛的数量
    // 遍历每头牛，如果cnt[i]为0，说明没有牛传球给它,res加1。  
    for(int i=1;i<=n;i++)
        if(!cnt[i])
            res ++ ;
    // 特判产生环的情况
    for(int i=2;i<=n;i++)
        if(to[i-1]==i&&to[i]==i-1&&cnt[i-1]==1&&cnt[i]==1)
            res++;
    printf("%d\n",res);
}

P1700 [USACO19OPEN] Milk Factory B

题目描述

牛奶生意正红红火火！Farmer John 的牛奶加工厂内有 N 个加工站，编号为 1…N（1≤N≤100），以及 N−1 条通道，每条连接某两个加工站。（通道建设很昂贵，所以 Farmer John 选择使用了最小数量的通道，使得从每个加工站出发都可以到达所有其他加工站）。

为了创新和提升效率，Farmer John 在每条通道上安装了传送带。不幸的是，当他意识到传送带是单向的已经太晚了，现在每条通道只能沿着一个方向通行了！所以现在的情况不再是从每个加工站出发都能够到达其他加工站了。

然而，Farmer John 认为事情可能还不算完全失败，只要至少还存在一个加工站 i 满足从其他每个加工站出发都可以到达加工站 i。注意从其他任意一个加工站 j 前往加工站 i 可能会经过 i 和 j 之间的一些中间站点。请帮助 Farmer John 求出是否存在这样的加工站 i。

输入格式

输入的第一行包含一个整数 N，为加工站的数量。以下 N−1 行每行包含两个空格分隔的整数 ai 和 bi，满足 1≤ai,bi≤N 以及 ai=bi。这表示有一条从加工站 ai 向加工站 bi 移动的传送带，仅允许沿从 ai 到 bi 的方向移动。

输出格式

如果存在加工站 i 满足可以从任意其他加工站出发都可以到达加工站 i，输出最小的满足条件的 i。否则，输出 −1。

输入输出样例

输入 #1复制

3
1 2
3 2

输出 #1复制

思路

这个明显就是建图，然后遍历图，对每个节点进行dfs搜索，因为是有向图，我们就在每一个节点进行dfs就行，先看代码吧，看完后了，开始说，题上就是要我们找有没有哪个节点，可以被所有节点到达，看给的样例，2可以被1和3到达所以就输出2，如果找不到就输出-1，又因为是有向图，如果我们从某个节点开始遍历，那他肯定能到达某个节点之后就停下，然后我们再遍历下一个节点进行dfs以此类推，我们再用一个w数组，记录每个节点会被几个节点到达，看看里面是否有能被所有节点到达就好，，中间我们还需一个visited数组，防止我们走重复，但刚刚我突然想了一下好像不需要，我把这个visited数组去了之后也ac了，可能是样例少的缘故？但其实我觉得加了visited代码更健壮吧，这样就保证每个节点只走了一次，不加的话我觉得可能会碰到环形的图，那就不好了

其实我觉得这个跟下面某个题挺像，跟下面危险系数哪个题很像，都是遍历图把每条路都走一遍，看看哪个节点走的次数和总路径数量相同，因为这个是单向图，所以t就是他的总路数量

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int w[N];
bool visited[N]={false};
void dfs(int u,vector<vector<int>>& graph){
	visited[u]=true;//每个节点只走一次 
	for(auto v:graph[u]){
		if(!visited[v]){
			w[v]++;
			dfs(v,graph);
		}
	} 
}
int main(){
	int n;
	cin>>n;
	int t=n-1;
	vector<vector<int>>graph(N+1);
	for(int i=0;i<t;i++){
		int u,v;
		cin>>u>>v;
		graph[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		memset(visited,0,sizeof(visited));//清空数组
		dfs(i,graph);
	}
	for(int i=1;i<=n;i++){
			if(w[i]==t)
			{
				cout<<i<<endl;
				return 0;
			}
	}
cout<<-1<<endl;
return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-08，如有侵权请联系 cloudcommunity@tencent.com 删除

int