qz!!!10pts dfs
查看原帖
qz!!!10pts dfs
764672
ZJLmath楼主2023/4/1 10:31
#include<bits/stdc++.h>
using namespace std;
int v,g;
int vet[50];
int a[50][50];
int ansm[50];
bool dfs(int start,int n,int b[50]){
	if(!n){
		for(int i=0;i<v;++i){
			if(b[i]>0)return false;
		}
		return true;
	}else{
	    if(start==g)return false;
	}
	for(int i=start+1;i<g;++i){
		for(int j=0;j<v;++j){
			b[j]-=a[i][j];
		}
		if(dfs(i,n-1,b)){
			ansm[n]=i+1;
			return true;
		}
		for(int j=0;j<v;++j){
			b[j]+=a[i][j];
		}
	}
}
int main(){
	cin>>v;
	for(int i=0;i<v;++i){
		cin>>vet[i];
	}
	cin>>g;
	for(int i=0;i<g;++i){
		for(int j=0;j<v;++j){
			cin>>a[i][j];
		}
	}
	int ans;
	for(int i=2;i<=g;++i){
		if(dfs(0,i,vet)){
			ans=i;
			break;
		}
	}
	cout<<ans<<' ';
	sort(ansm+1,ansm+1+ans);
	for(int i=1;i<=ans;++i){
		cout<<ansm[i]<<' ';
	}
	return 0;
}
2023/4/1 10:31
加载中...