蓝桥杯 文化之旅 图论 待复习

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<set>
 5 #include<cmath>
 6 #include<algorithm>
 7 using namespace std;
 8 
 9 const int N=110,K=110;
10 int c[N],cultrul[K],graph[N][N],vis[N],a[N][N];
11 int n,k,m,s,t;
12 long long res=-1;
13 set<int>cu;
14 
15 void dfs(int next,long long sum)
16 {
17     if(res!=-1 && sum>res) return ;
18     if(next==s)
19     {
20         if(res==-1) res=sum;
21         else res=min(res,sum);//记录更短的路径
22         return ;    
23     } 
24     for(int i=1;i<=n;i++)
25     {
26         //没有来过这个国家  路径走得通  没有学习过这类文化  
27         if(!vis[i] && graph[i][next] && cultrul[c[i]]==false)
28         {
29             bool ok=true;
30             for(set<int>::iterator it=cu.begin();it!=cu.end();it++)//枚举后面国家文化类型 
31             {
32                 if(a[c[i]][*it])//如果当前国家文化和后继国家文化冲突 
33                 {
34                     ok=false;
35                     break;
36                 }
37             }
38             if(ok)
39             {
40                 vis[i]=true;
41                 cultrul[c[i]]=true;
42                 cu.insert(c[i]);
43                 dfs(i,sum+graph[i][next]);
44                 vis[i]=false;
45                 cultrul[c[i]]=false;
46                 cu.erase(c[i]);
47             }
48         }   
49     } 
50 } 
51 int main(void)
52 {
53     //freopen("D:\\input6.txt","r",stdin);
54     int u,v,d;
55     cin>>n>>k>>m>>s>>t;
56     for(int i=1;i<=n;i++) cin>>c[i];
57     for(int i=1;i<=k;i++)
58     {
59         for(int j=1;j<=k;j++) cin>>a[i][j];
60     }
61     for(int i=1;i<=m;i++)
62     {
63         cin>>u>>v>>d;
64         if(graph[u][v]==0) graph[u][v]=graph[v][u]=d;
65         else if(graph[u][v]>d)
66         {
67             graph[u][v]=graph[u][v]=d;
68         }
69     }
70     
71     vis[t]=true;//访问过这个国家 
72     cultrul[c[t]]=true;//学习了这种文化 
73     cu.insert(c[t]); 
74     dfs(t,0);
75     cout<<res;
76     return 0;
77 } 

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cstdlib>
 5 using namespace std;
 6 const int Inf=100000010;
 7 int n,m,k,s,t;
 8 int k1=0,sum=0,ans=Inf;
 9 int con[110],head[20010],fig[110][110];//con[i]=j表示第i个国家冲突第j种文化 fig[i][j]表示i j文化关系 
10 bool road[110],exp[110],flag=false;//road表示已访问的国家 exp表示已访问的文化 
11 struct node{
12     int to,next,w;
13 }e[20010];
14 void add(int u,int v,int w)
15 {
16     k1++;
17     e[k1].next=head[u];
18     e[k1].to=v;
19     e[k1].w=w;
20     head[u]=k1;
21 }
22 bool judge(int x)
23 {
24   if(road[x] || exp[con[x]]) return false;
25    for(int i=1;i<=k;i++)
26     if(exp[i]&&fig[con[x]][i]==1||fig[con[t]][con[x]]==1||fig[con[t]][i]) return false;
27     //后两个判断表明如果终点的文化冲突已经学过的文化和访问次国家的文化 则return false 
28      return true;
29 }
30 void dfs(int x,int sum)
31 {
32     bool ff=false;
33   if(x==t){
34       flag=true;
35       ans=min(ans,sum);
36       return ;
37   }
38   if(sum>=ans) return;//剪枝 
39   for(int i=head[x];i;i=e[i].next)
40   {
41       int p=e[i].to;
42       if(judge(p))
43       {
44         ff=true;//判断是否可以往下走 
45         road[p]=true,exp[con[p]]=true;
46         dfs(p,sum+e[i].w);
47         road[p]=false,exp[con[p]]=false;
48     }
49   }
50   if(ff==false){
51       printf("-1");//如果没有往下走 这直接打印-1并退出 
52       exit(0);
53   }
54 }
55 int main()
56 {
57     memset(road,false,sizeof(road));
58     memset(exp,false,sizeof(exp));
59     scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
60     for(int i=1;i<=n;i++) scanf("%d",&con[i]);
61     for(int i=1;i<=k;i++)
62      for(int j=1;j<=k;j++) 
63       scanf("%d",&fig[i][j]);
64     int x,y,z;
65     for(int i=1;i<=m;i++)
66     {
67       scanf("%d%d%d",&x,&y,&z);
68       sum+=z;
69       add(x,y,z);
70       add(y,x,z);
71     }  
72     exp[con[s]]=true;
73     dfs(s,0);
74     if(ans>sum||flag==false) printf("-1");
75     else printf("%d",ans);
76     return 0;
77 }