[数据结构与算法]2019南昌-A Funny Bipartite Graph-(暴搜+剪枝)

B

题意：
就是给你两个点集，每个点集最多18个点，左边每个点会和右边某些点有连边，但是不会超过3条。左边的点i如果你链接了k条边，那么代价就是vb[i]的k次方。同时呢，会给你限制，也就是左边的点a和b不能同时被选。现在问你，如果右边的点每个点都被连接了，至少要花费多少，如果打不成输出-1。

思考：
刚开始我以为是对于左边的点，选了他就代表和他连边的右边的点全部就得到了，实际上对于边也是有选择的。所以对于每个点到底要选择那些边，如果每次都二进制枚举，会超时。而且这样还那么复杂，既然右边每个点都想被选，那么就是每个点就选一个，枚举一下每个点选择那个点。3的18次方，但是呢，加上剪枝和题目自己给的限制，就过了。
反正对于一些题目，都可以暴力的去试一试，因为数据到底强不强也不知道。

代码：

int T,n,m,k;
char va[M][M];
char cant[M][M];
int vb[N],ned[N];
int minn = inf;

vector<int > e[20];

int ksm(int a,int b)
{
	if(b==0) return 0;
	int sum = 1;
	while(b)
	{
		if(b&1) sum = sum*a;
		a = a*a;
		b >>= 1;
	}
	return sum;
}

void init()
{
	minn = inf;
	for(int i=1;i<=n;i++)
	{
		vb[i] = ned[i] = 0;
		e[i].clear();
	}
}

void dfs(int now,int sum)
{
	if(minn<=sum) return ;
	if(now>n)
	{
		minn = min(minn,sum);
		return ;
	}
	for(auto can:e[now])
	{
		int suc = 1;
		for(int i=1;i<=n;i++) if(ned[i]>=1&&cant[i][can]=='1') suc = 0;
		if(!suc) continue;
		ned[can]++;
		dfs(now+1,sum-ksm(vb[can],ned[can]-1)+ksm(vb[can],ned[can]));
		ned[can]--;
	}
}

signed main()
{
	IOS;
	cin>>T;
	while(T--)
	{
		cin>>n;
		init();
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				cin>>va[i][j];
				if(va[i][j]=='1') e[j].pb(i);
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			cin>>cant[i][j];
		}
		for(int i=1;i<=n;i++) cin>>vb[i];
		dfs(1,0);
		if(minn==inf) cout<<-1<<"\n";
		else cout<<minn<<"\n";
	}
	return 0;
}

总结：
多多试一试，不要怕什么的。