Bactracking grafuri

[•Mitza444]

Salut !Am urmatoarea problemahttp://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1196.
Am incercat o rezolvare cu backtracking in care cabanele sun nodurile unui graf si am retinut vecinii in liste.Dupa asta am luat fiecare varf l-am pus pe prima poz in sirul de solutii sol si fiecare vecin al nodului de pe sol[1] l-am pus pe pozitia M astfel incat sa existe poteca de intoarcere.Dupa care fac un backtracking recursiv in care determin drumurile posibile care au si un izvor(pt a vedea daca e izvor sau nu am folosit sirul ok).Sursa mea merge bine problema e ca pica la timp un test si ia doar 90p.
Imi puteti da ceva idei de optimizare pt. a lua 100p.
Am incercat 2 implementari una cu liste de adiacenta una cu matrice de adiacenta amandoua iau 90p ,dar mi se pare ca cea cu matrice merge mai repede(trece doar cu putin 1.2s la testul cel mai mare).
Aici e sursa cu liste:

Cod:

#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
#define ff first
#define ss second
vector < pair<int,int> > v[101];
int sol[30];
bool viz[22],ok[22];
int N,M,P,nr;
int find(int x,int y){
	unsigned i;
	for(i=0;i<v[x].size();i++){
		if(y==v[x][i].ff){
			if(v[x][i].ss==1)
				ok[M]=1;
			return 1;
		}
	}
	return 0;
}
void back(int k){
	unsigned i;
	int izvor;
	izvor=0;
    if(k==M){
		/*for(i=1;i<=k;i++)
			cout<<sol[i]<<" ";
		cout<<'\n';
		for(i=1;i<=k;i++)
			cout<<ok[i]<<" ";
		cout<<'\n';*/
		if(find(sol[k-1],sol[k])){
		for(i=1;i<=k;i++){
			if(ok[i]==1){
				izvor=1;
				break;
			}
		}
		ok[M]=0;
		if(izvor)
			nr++;
	}
	}
    else{
        for(i=0;i<v[sol[k-1]].size();i++){
            if(!viz[v[sol[k-1]][i].ff]){
				sol[k]=v[sol[k-1]][i].ff;
				viz[v[sol[k-1]][i].ff]=1;
				if(v[sol[k-1]][i].ss==1)
					ok[k]=1;
				back(k+1);
				ok[k]=0;
				viz[v[sol[k-1]][i].ff]=0;
			}
		}
	}
}
int main(){
    int i,x,y,z;
	unsigned j;
    freopen("izvor.in","r",stdin);
    scanf("%d%d%d",&N,&P,&M);
    for(i=1;i<=P;i++){
        scanf("%d%d%d",&x,&y,&z);
        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }
    fclose(stdin);
    for(i=1;i<=N;i++){
        if(v[i].size()>=2){
            sol[1]=i;
			viz[i]=1;
            for(j=0;j<v[i].size();j++){
                sol[M]=v[i][j].ff;
				viz[v[i][j].ff]=1;
                back(2);
				viz[v[i][j].ff]=0;
            }
			viz[i]=0;
        }
    }
	freopen("izvor.out","w",stdout);
	printf("%d\n",nr);
	fclose(stdout);
	return 0;
}

Si aici e sursa cu matrice:

Cod:

#include<cstdio>
#include<iostream>
using namespace std;
int N,P,M;
int mat[21][21],nr,sol[10];
bool viz[21],ok[10];
void back(int k){
	int i,izvor=0;
	if(k==M){
		izvor=0;
		for(i=1;i<=M;i++){
			if(ok[i]){
				izvor=1;
				break;
			}
		}
		if(izvor)
			nr++;
	}
	else{
		for(i=1;i<=N;i++){
			if(mat[sol[k-1]][i] && !viz[i] && k<M-1){
				sol[k]=i;
				viz[i]=1;
				if(mat[sol[k-1]][i]==2)
					ok[k]=1;
				back(k+1);
				viz[i]=0;
				ok[k]=0;
			}
			else if(k==M-1){
				if(!viz[i] && mat[sol[k-1]][i] && mat[i][sol[M]]){
					sol[k]=i;
					viz[i]=1;
					if(mat[sol[k-1]][i]==2)
						ok[k]=1;
					if(mat[i][sol[M]]==2)
						ok[k+1]=1;
					back(k+1);
					viz[i]=0;
					ok[k]=0;
                                        ok[M]=0;
				}
			}
		}
	}
}
int main(){
	int i,x,y,z,j;
	freopen("izvor.in","r",stdin);
	scanf("%d%d%d",&N,&P,&M);
	for(i=1;i<=P;i++){
		scanf("%d%d%d",&x,&y,&z);
		mat[x][y]=mat[y][x]=z+1;
	}
	fclose(stdin);
	for(i=1;i<=N;i++){
		sol[1]=i;
		viz[i]=1;
		for(j=1;j<=N;j++){
			if(mat[i][j]){
				sol[M]=j;
				viz[j]=1;
				back(2);
				viz[j]=0;
			}
		}
		viz[i]=0;
	}
	freopen("izvor.out","w",stdout);
	printf("%d\n",nr);
	fclose(stdout);
	return 0;
}

Multumesc.