Atcoder Beginner Contest 441 - D

D - Paid Walk题解

题目传送门-Luogu

题目传送门-Atcoder

题目大意

一个图，有 $n$ 个顶点， $m$ 条边，找到满足：

1. 恰好经过 $l$ 条边

2. 经过的边边权之和在 $[s,t]$ 的区间内

这两个条件的顶点，并输出

思路

题目中说 $1\le l\le 10$ 每个节点的出度 $\le 4$ ，使用暴力枚举最多枚举 $4^{10}$ 次，可以暴搜

定义结构体 Node 用于存储图

struct Node{
	int p,q;
};

这里考虑使用 DFS 暴力枚举（其实 BFS 也是可以哒，这里先只讲深搜），然后开一个桶数组 $b$ ，走到 $l$ 条边之后判断，如果达标就标记 $b_x=1$

int b[200010];
int cnt=0,sum=0;    //全局变量cnt表示搜的边数，sum表示搜的边权和
void dfs(int x){    //x表示搜到哪一个节点
	if(cnt>=l){
		if(sum>=s&&sum<=t)b[x]=1;
		return ;
	}
	for(auto it:e[x]){
		cnt++,sum+=it.q;
		dfs(it.p);
		cnt--,sum-=it.q;    //回溯
	}
}

然后输入输出

cin>>n>>m>>l>>s>>t;
for(int i=1;i<=m;i++){
    int u,v,c;
	cin>>u>>v>>c;
    e[u].push_back({v,c});
}
dfs(1);
for(int i=1;i<=n;i++){
    if(b[i])cout<<i<<" ";
}

！圆满完成任务！

忘给AC代码了！！！

AC代码来了

#include<bits/stdc++.h>
#define int long long
using namespace std;
int b[200010];
int cnt=0,sum=0;    //全局变量cnt表示搜的边数，sum表示搜的边权和
int n,m,l,s,t;
struct Node{
	int p,q;
};
vector<Node>e[200010];
void dfs(int x){    //x表示搜到哪一个节点
	if(cnt>=l){
		if(sum>=s&&sum<=t)b[x]=1;
		return ;
	}
	for(auto it:e[x]){
		cnt++,sum+=it.q;
		dfs(it.p);
		cnt--,sum-=it.q;    //回溯
	}
}
signed main(){
	cin>>n>>m>>l>>s>>t;
	for(int i=1;i<=m;i++){
		int u,v,c;
		cin>>u>>v>>c;
		e[u].push_back({v,c});
	}
	dfs(1);
	for(int i=1;i<=n;i++){
		if(b[i])cout<<i<<" ";
	}
	return 0;
}

AC记录