算法-DFS

DFS

暴力回溯

1. 2021-4-7 两次回溯

题目：

现在有n个物品，每一个物品都有一个价值，现在想将这些物品分给两个人，要求这两个人每一个人分到的物品的价值总和相同（个数可以不同，总价值相同即可），剩下的物品就需要扔掉，现在想知道最少需要扔多少价值的物品才能满足要求分给两个人。

输入描述:

第一行输入一个整数 T，代表有 T 组测试数据。

对于每一组测试数据，一行输入一个整数 n ，代表物品的个数。

接下来 n 个数，a[i] 代表每一个物品的价值。

1<= T <= 10
1 <= n <= 15
1 <= a[i] <= 100000

输出描述:

对于每一组测试数据，输出一个答案代表最少需要扔的价值。

示例1

输入

1
5
30 60 5 15 30

输出

20

说明

样例解释，扔掉第三个和第四个物品，然后将第一个物品和第五个物品给第一个人，第二个物品给第二个人，每一个人分到的价值为60，扔掉的价值为20。

思路：

先通过回溯找到最大的sum/2的值，即tsum，中间交给mark标记已经选择的物品。
然后交给match。判断剩余的物品能否拼出这个tsum。
通过一个很巧妙的办法：设置一个vector，其中每个元素是已经加过方案，即这个vector是动态增加方案的。一旦某个方案+当前v[i]等于tsum则返回true。

代码：

#include<bits/stdc++.h>
using namespace std;
bool match(int tsum,vector<int>& v,vector<bool>& mark){
    vector<int> t(1,0);
    for(int i=0;i<v.size();++i){
        int tn=t.size();
        if(!mark[i]){
            for(int j=0;j<tn;++j){
                if(v[i]+t[j]==tsum)return true;
                else t.push_back(v[i]+t[j]);
            }
        }
    }
    return false;
}
void search1(int &ans,int now,int n,int tsum,vector<int>& v,int sum,vector<bool>& mark){
    if(now>n||tsum*2>sum)return;
    if(now==n){
        if(match(tsum,v,mark)){
            ans=max(ans,tsum);
        }
        return;
    }
    mark[now]=1;
    search1(ans,now+1,n,tsum+v[now],v,sum,mark);
    mark[now]=0;
    search1(ans,now+1,n,tsum,v,sum,mark);
}
int main(){
    int T;
    scanf("%d",&T);
    vector<int> res;
    while(T>0){
        int n;
        scanf("%d",&n);
        vector<int> v(n,0);
        int sum=0;
        int ans=0;
        for(int i=0;i<n;++i)scanf("%d",&v[i]),sum+=v[i];
        vector<bool> mark(n,false);
        search1(ans,0,n,0,v,sum,mark);
        res.push_back(sum-2*ans);
        T--;
    }
    for(auto e:res)cout<<e<<endl;
    return 0;
}
}
	

2. 2021-4-8 无向图转有向图

题目：

小团找到一颗有 n 个节点的苹果树，以 1 号节点为根，且每个节点都有一个苹果，苹果都有一个颜色，但是这棵树被施加了咒术，这使得小团只能从某一个节点的子树中选取某一种颜色的拿。小团想要拿到数量最多的那种颜色的所有苹果，请帮帮她。每次她会指定一个节点 t ，如果小团只能从节点 t 的子树中选取某一种颜色的苹果，选取什么颜色能拿到最多的苹果？如果有多种颜色都可以拿同样多的苹果，输出颜色编号最小的那个对应的编号。

节点 x 的子树定义为所有将 x 当作祖先的节点， x 也视为 x 的子树的一部分。

输入描述:

第一行一个正整数n表示这颗树上节点的个数。

接下来n-1行，每行两个正整数x­­i,yi,表示树上第i条边连接的两个节点。

接下来一行n个正整数c­i，分别表示从1~n号节点上的苹果的颜色。

接下来一行一个正整数q,表示接下来有q次独立的询问。

接下来q行，每行一个正整数t表示询问：如果小团只能从节点t的子树中选取某一种颜色的苹果，选取什么颜色能拿到最多的苹果？如果有多种颜色都可以拿同样多的苹果，输出颜色编号最小的那个对应的编号。

对于100%的数据n≤5000, 1≤xi,yi,t≤n, ci≤1000000000,q≤1000

输出描述:

输出q行，每行一个整数，表示答案。

示例1

输入

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

输出

1
1
2
1
2
2
3

思路：

这道题首先没有说明谁是谁的子树，只说了1是根，那么要通过深搜把孩子指向父的边都去掉。
这里注意必须先去再深搜，不然1->2，2->1会循环。

得到有向图以后，只需要把待求节点深搜一遍，统计每个颜色的数量，处理一下。

代码：
这道只能通过百分之10.

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


unordered_map<int, list<int>> edges;

void dfs(unordered_map<long long, long long>& mt, int root, vector<long long>& apples) {
	mt[apples[root]]++;
	for (auto next : edges[root]) {
		dfs(mt, next, apples);
	}
}
void delete_edges(int root) {
	for (auto next : edges[root]) {
		edges[next].remove(root);
		delete_edges(next);
	}
}
int main() {
	int n;
	scanf("%d", &n);
	vector<long long> apples(n + 1);
	for (int i = 1; i <n; ++i) {
		int x, y;
		scanf("%d%d", &x,&y);
		edges[x].push_back(y);
		edges[y].push_back(x);
	}
	
	delete_edges(1);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &apples[i]);
	}
	int q; scanf("%d", &q);
	vector<int> query(q, 0);

	for (int i = 0; i < q; ++i) {
		scanf("%d",&query[i]);
	}
	for (int i = 0; i < q; ++i) {
		int root = query[i];
		unordered_map<long long, long long> mt;
		long long ans = 1000000005;
		dfs(mt, root,apples);
		int rr = 0;
		for (auto be = mt.begin(); be != mt.end(); ++ be) {
			if (be->second >= rr) {
				rr = be->second;
				ans = min(ans, be->first);
			}
		}
		cout << ans << endl;
	}
	return 0;
}