1500. Pass Licenses
Time limit: 2.5 secondMemory limit: 64 MB
A New Russian Kolyan believes that to spend his time in traffic jams is below his dignity. This is why he had put an emergency flashlight upon the roof of his Hummer and had no problems until a recent decision of the city administration. Now each street of the city belongs to one or several categories, and a driver must have a separate license in order to use an emergency flashlight in the streets of each category. If a street belongs to several categories, it is sufficient to have a license only for one of these categories. For each category, a license is issued by a separate city official. Although these officials are different, they accept bribes of the same amount for giving a license. Help Kolyan to find a way from his home to work such that he can go this way with his flashlight turned on and having spent the minimal amount of money for bribes.
Input
The input contains the street plan in the following format. There are integersK,N, andMin the first line, whereKis the number of street categories (1 ≤K≤ 20),Nis the number of crossroads (2 ≤N≤ 30), andMis the number of descriptions of street segments between crossroads.
Each of the nextMlines describes a street segment by three integersV1V2C, whereV1andV2are the numbers of the crossroads limiting this segment, andCis its category. Crossroads are numbered from 0 toN–1, categories are numbered from 0 toK–1. For any pair of crossroads no two segments of the same category connect these crossroads.
Output
Output in the first line the minimal number of licenses necessary for going from the crossroad 0 (Kolyan’s home) to the crossroad 1 (Kolyan’s work) with an emergency flashlight turned on.
In the second line, give the list of categories for which licenses must be obtained. The numbers should be separated with spaces. It is guaranteed that such list is always exist.
Sample
inputoutput
3 3 30 2 00 2 11 2 220 2
Problem Author:Magaz Asanov, Alexander Mironenko, Anton Botov, Evgeny KrokhalevProblem Source:Quarter-Final of XXXI ACM ICPC – Yekaterinburg – 2006
Tags:graph theory()
Difficulty: 677
题意：有n个点，k种交通卡，m条路。 每条路有对应的交通卡，对应的交通卡可能有多张，拥有一张就可以通行。问从0到1，所需要的交通卡最少几张，并输出是哪几张。
做法：因为数据很小，所以可以枚举交通卡，复杂度是2^k=10^6。然后dfs，每个点只走一次，所以复杂度是n。所以总的复杂度是10^7。跑得有点久用了1.7s。
int mp[30][30]; int k,n,m;//k个 cat n个点 m条路int vv[30];int cat=0;int dfs(int now)//0-1{if(now==1)return 1;vv[now]=1;for(int i=0;i<n;i++){if(vv[i]==0&&(mp[now][i]&cat)){if(dfs(i)){//这里别把vis[i]改回0，因为只是求能否到达，没有其他条件，//所以每个点只用访问一遍。//之前改回0了，一直TLE，，因为改回0，复杂度是n^2。//而这样复杂度只用n。return 1;} }}return 0;}int arr;int main(){scanf("%d%d%d",&k,&n,&m); //k cat n 点 m边memset(mp,0,sizeof mp); int v1,v2,c;for(int i=0;i<m;i++){scanf("%d%d%d",&v1,&v2,&c);mp[v1][v2]|=(1<<c);mp[v2][v1]=mp[v1][v2];}int lim=(1<<k);int ans=k;arr=lim-1;memset(vv,0,sizeof vv);for(int i=0;i<lim;i++){int cnt=0;int tem=i;while(tem){if(tem&1)cnt++;tem>>=1;} if(cnt>=ans)continue;cat=i;memset(vv,0,sizeof vv);if(dfs(0)){ans=cnt;arr=i;} }printf("%d\n",ans);int fir=1;for(int i=0;i<k;i++){if(arr&(1<<i)){if(fir){fir=0;printf("%d",i);}elseprintf(" %d",i);}}puts("");return 0;}
乐观者在灾祸中看到机会;悲观者在机会中看到灾祸
