题解 CF102A 【Clothes】

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 1k | 阅读时长 ≈ 1 分钟

本萌新来介绍一种$dfs$思路：

  • 1 如果件数已经$=$3，那么判断，如果符合条件，则更新答案

  • 2 如果件数$<$3，那么枚举$1$~$n$,如果该件衣服没被取过，则标记为已取并$dfs$下一件

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
	int n,m,money[110],minx=INT_MAX;
bool p[110][110],f,use[110];
int s[5];
bool comp()//判断是否符合条件
{
	if(p[s[1]][s[2]] and p[s[1]][s[3]] and p[s[2]][s[3]]) return 1;
	return 0;
}
void dfs(int t,int sum)
{
	if(t>3)//件数>3判断
	{
		if(comp())
	    {
	    	f=1;//标记为有方案
	    	minx=min(minx,sum);
		}
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(!use[i])//该件衣服没被取过
		{
			s[t]=i;//保存答案编号用于之后判断
			use[i]=1;//标记为已取
			dfs(t+1,sum+money[i]);
			use[i]=0;//回溯
		}
	}
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>money[i];
    for(int i=1;i<=m;i++)
    {
    	int x,y;
    	cin>>x>>y;
    	p[x][y]=1;//建有向图
    	p[y][x]=1;
	}
    dfs(1,0);
    if(f) cout<<minx;
    else cout<<"-1";
	return 0;
}