jzoj通行证【DFS(两种方法)】【图论】

两种方法)】【图论】"/>

jzoj通行证【DFS(两种方法)】【图论】

>Description
每条道路由若干个机构管辖，要在这条街道上通过，至少要拥有其中一个机构的通行证。
要靠贿赂来获得通行证，为了让开销尽量小，你希望能找出一种方案，使得能通行与家与工作地点之间，且通行证数最少。城市的交通网络可视为由若干路口和双向行驶的街道组成。

>Input
第一行三个整数k; n;m，分别表示机构数，路口数，以及街道的描述数。接下来m 行，每行三个整数a; b; c，表示机构c 管辖连接路口a，b的街道。
路口的编号范围为[0; n ? 1]，机构的编号范围为[0; k ? 1]。家的编号为0，工作地点的编号为1。

>Output
若有解，输出第一行一个整数ans，表示最少的通行证数，第二行ans个整数，表示所需通行证的编号。若有多种方案，请输出字典序最小的方案。若无解，输出"Impossible"。

>Sample Input
3 3 3
0 2 0
0 2 1
1 2 2

>Sample Output
2
0 2

>解题思路
有两种方法，都是用DFS解：
1.深搜机构个数，每个机构贿赂或不贿赂，每次都把贿赂机构所管辖的道路连通，看看0和1两点之间是否连通，如果连通就判断机构数是否小于ans。
2.深搜道路，枚举当前点连接所有道路，如果管辖的机构不同，也视为不同道路。如果当前道路所属于的机构之前就贿赂过了，就直接搜下一个点所连接道路，如果没有，就贿赂这个机构，然后同上。注意要标记每个点有没有走过。

>代码
第一种：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct ooo
{int a,b;
}h[25][900];
int k,n,m,x,y,z,t[25],ans,l[25];
bool yd[25],aa[35][35];
void lil(int s,int sum) //s为现在搜索的深度，sum为贿赂机构的数量
{if(s==k) return; //如果越界就return(记住顺序从0~k-1)if(sum>=ans) return; //如果这时机构数已经超过答案了，就直接returnfor(int i=0;i<n;i++)for(int j=i+1;j<n;j++)aa[i][j]=aa[j][i]=0; //清0for(int i=0;i<=s;i++)if(yd[i]) //如果此机构贿赂过{for(int j=1;j<=t[i];j++)aa[h[i][j].a][h[i][j].b]=aa[h[i][j].b][h[i][j].a]=1; //把此机构管辖的道路连接}for(int kk=0;kk<n;kk++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(kk!=i&&i!=j&&j!=kk&&aa[i][kk]&&aa[kk][j])aa[i][j]=aa[j][i]=1; //floyedif(aa[0][1]) //如果0和1相连的话{if(sum<ans) //如果贿赂机构数比答案小就更新答案{ans=sum;l[0]=0;for(int i=0;i<=s;i++)if(yd[i]) l[++l[0]]=i; //l记录答案}return;}yd[s+1]=1;lil(s+1,sum+1); //贿赂yd[s+1]=0;lil(s+1,sum); //不贿赂
}
int main()
{
//	freopen("license.in","r",stdin);
//	freopen("license.out","w",stdout);ans=30;scanf("%d%d%d",&k,&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);h[z][++t[z]].a=x; h[z][t[z]].b=y; //记录每个机构管辖的道路}lil(-1,0); //从-1开始搜（第0个机构也可能不被贿赂）if(ans==30){printf("Impossible");return 0;}printf("%d\n",ans);for(int i=1;i<=l[0];i++)printf("%d ",l[i]);return 0;
}

第二种：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct ooo
{int to,sb;
}h[35][35];
int k,n,m,x,y,z,ans,t[25],l[25];
bool yd[35],p[25];
bool aka(ooo aa,ooo bb){return aa.sb<bb.sb;}
void lil(int s,int sum) //s为当前点，sum为贿赂机构数
{if(s==1) //如果到了1{if(sum<ans) //同上{ans=sum; l[0]=0;for(int i=0;i<k;i++)if(p[i]) l[++l[0]]=i;}return;}if(sum>=ans) return;yd[s]=1;for(int i=1;i<=t[s];i++)if(!yd[h[s][i].to]) //没有走过此点if(p[h[s][i].sb]==1) lil(h[s][i].to,sum); //已经贿赂过else //没有贿赂过{p[h[s][i].sb]=1;lil(h[s][i].to,sum+1);p[h[s][i].sb]=0;}yd[s]=0;
}
int main()
{
//	freopen("license.in","r",stdin);
//	freopen("license.out","w",stdout);ans=30;scanf("%d%d%d",&k,&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);h[x][++t[x]].to=y; h[x][t[x]].sb=z;h[y][++t[y]].to=x; h[y][t[y]].sb=z; //记录分别于x,y相连的边所指向的点和管理的机构}for(int i=0;i<n;i++)sort(h[i]+1,h[i]+t[i]+1,aka); //排个序lil(0,0);if(ans==30){printf("Impossible");return 0;}printf("%d\n",ans);for(int i=1;i<=l[0];i++)printf("%d ",l[i]);return 0;
}