搜索与图论

DFS

dfs，即深度优先搜索，主要运用递归的思想。会将一种可能性搜索完的情况下再开始搜索下一种可能性。

acwing 1355母亲的牛奶

给你三个不同大小的桶，一开始只有c桶装满牛奶，三个桶来回倒，求问在a桶空着的情况下c桶可能有多少牛奶，答案升序输出
数据很小，我们考虑每种情况而并非考虑每个桶，开一个三维数组记录是否出现过相同情况，相同则return
并且由于我们的vis数组考虑的是单独情况而非是否选某个点，因此不需要回溯（这样说有点歧义，总之就是不用讲vis数组变为0）

#include<bits/stdc++.h>
using namespace std;
int A,B,C;
struct node
{
	int a;
	int b;
	int c;
};
int vis[30][30][30];
int avis[30];
int ans[30],cnt=0;
void dfs(int a,int b,int c)
{
	if(vis[a][b][c]) return;
	vis[a][b][c]=1;
	if(!avis[c]&&a==0) avis[c]=1,ans[++cnt]=c;
	dfs(a-min(a,B-b),min(a+b,B),c);
    dfs(a-min(a,C-c),b, min(a+c,C));
    dfs(min(a+b,A),b-min(b,A-a),c);
    dfs(a,b-min(b,C-c),min(c+b,C));
    dfs(min(a+c,A),b,c-min(c,A-a));
    dfs(a,min(b+c,B),c-min(c,B-b));
}
int main()
{
	cin>>A>>B>>C;
	dfs(0,0,C);
	sort(ans+1,ans+cnt+1);
	for(int i=1;i<=cnt;i++)
	printf("%d ",ans[i]);
	return 0;
}

BFS

又称广度优先搜索，和bfs思想上的区别主要在于bfs是对于每种情况，会将它后续可能的下一步情况一一进行处理。而dfs则是选中下一步情况的某一个一直搜直到搜出结果再进行另一种情况。（也就是bfs每次都能获得每种情况的每一步结果，而dfs要先得到一种情况的结果再进行下一种情况）。这样的特性使得bfs适合做最短路。因为所有情况都是同步进行的，那么先达到目标点的情况就是最短的情况。
而在实现方法上，bfs采用队列的实现方法，每次发现新的可行方案时将该情况放到队尾，也就是说对于一种情况，它的所有下一步情况都会被依次放进队列，这样就能保证他们能依次被处理。

acwing 1355母亲的牛奶

没错，还是这题，写了bfs版本的

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int a;
	int b;
	int c;
};
queue<node> q;
int A,B,C;
bool vis[25][25][25];
int vans[25];
int ans[50],cnt=0;
void inst(int a,int b,int c)
{
	if(!vis[a][b][c]) 
	{
		q.push({a,b,c});
		vis[a][b][c]=true;
	}
	if(!vans[c]&&a==0) 
	{
		ans[++cnt]=c;
		vans[c]=1;
	}
}
void bfs()
{
	q.push({0,0,C});
	vis[0][0][C]=1;
	while(!q.empty())
	{
		node h=q.front();
		q.pop();
		int a=h.a,b=h.b,c=h.c;
		inst(a-min(a,B-b),min(a+b,B),c);
        inst(a-min(a,C-c),b, min(a+c,C));
        inst(min(a+b,A),b-min(b,A-a),c);
        inst(a,b-min(b,C-c),min(c+b,C));
        inst(min(a+c,A),b,c-min(c,A-a));
        inst(a,min(b+c,B),c-min(c,B-b));
	}
}
int main()
{
	cin>>A>>B>>C;
	bfs();
	sort(ans+1,ans+cnt+1);
	for(int i=1;i<=cnt;i++)
	printf("%d ",ans[i]);
	return 0;
}