多多捕蝇拼多多技术岗 7月3号笔试 第三题题目内容现在多多宿舍区有nnn个房间编号111到nnn和一只苍蝇多多准备通过在房间放置粘蝇板的方式进行捕蝇如果要在房间iii捕捉到苍蝇需要在该房间放置CiC_iCi​个粘蝇板。苍蝇会在各个房间进行活动如果它现在在房间iii下一分钟它会跑到房间aia_iai​如果iaii a_iiai​表示苍蝇不会离开房间苍蝇所在的初始房间是随机不确定的它可能初始出现在任意一个房间。如果需要捕捉到这只苍蝇请你帮多多计算下至少需要多少个粘蝇板。输入描述每个测试用例第一行包含一个整数nnn1≤n≤1051 \le n \le 10^51≤n≤105表示房间的数量第二行包含nnn个整数c1,c2,…,cnc_1,c_2,…,c_nc1​,c2​,…,cn​1≤ci≤1041 \le c_i \le 10^41≤ci​≤104cic_ici​表示在房间iii捕捉到苍蝇需要的粘蝇板数量第三行包含nnn个整数a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​1≤ai≤n1 \le a_i \le n1≤ai​≤naia_iai​表示在当前房间iii的苍蝇下一分钟去到的房间。输出描述每个测试用例输出一个整数表示多多捕捉到苍蝇需要的最少的粘蝇板数量。样例1输入4 1 10 2 10 2 4 2 2输出10说明把粘蝇板放在第222个房间无论苍蝇最开始出现在哪个房间在经过一段时间之后都会通过第222个房间所需要的粘蝇板数量就是101010。题解思路解决思路:拓扑排序 DFS这道题本质是一个有向图这个图有个特点就是所有节点要不属于某个环要不指向一个环。接下来考虑怎么放置成本最低分情况讨论位于环中由于环中中节点全部可互相访问一个环中最低成本就为环中最小minc指向环的节点指向环的节点根本无需放置可由指向环中节点帮忙捕获。利用A - B --C把C看作一个环覆盖这个块最低成本就是选择C。根据2的分析根本无需处理指向环的节点这部分节点可通过拓扑排序进行剔除。成本由环决定可通过递归处理接下来每个环总成本为所有环中sum(min(c))C#includebits/stdc.husingnamespacestd;intmain(){intn;cinn;vectorinta(n1);vectorintc(n1);vectorintindeg(n1,0);for(inti1;in;i)cinc[i];for(inti1;in;i){cina[i];indeg[a[i]];}queueintq;for(inti1;in;i){if(indeg[i]0){q.push(i);}}while(!q.empty()){intuq.front();q.pop();intva[u];indeg[v]--;if(indeg[v]0){q.push(v);}}longans0;// 现在剩余的都是环vectorintvis(n1,false);for(inti1;in;i){if(indeg[i]0!vis[i]){intcurrenti;intminCostc[i];vis[i]true;currenta[current];while(current!i){minCostmin(minCost,c[current]);vis[current]true;currenta[current];}ansminCost;}}coutans;return0;}javaimportjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));intnInteger.parseInt(br.readLine());int[]anewint[n1];int[]cnewint[n1];int[]indegnewint[n1];String[]partsbr.readLine().split( );for(inti1;in;i){c[i]Integer.parseInt(parts[i-1]);}partsbr.readLine().split( );for(inti1;in;i){a[i]Integer.parseInt(parts[i-1]);indeg[a[i]];}QueueIntegerqnewLinkedList();for(inti1;in;i){if(indeg[i]0){q.offer(i);}}while(!q.isEmpty()){intuq.poll();intva[u];indeg[v]--;if(indeg[v]0){q.offer(v);}}longans0;// 现在剩余的都是环boolean[]visnewboolean[n1];for(inti1;in;i){if(indeg[i]0!vis[i]){intcurrenti;intminCostc[i];vis[i]true;currenta[current];while(current!i){minCostMath.min(minCost,c[current]);vis[current]true;currenta[current];}ansminCost;}}System.out.println(ans);}}pythonimportsysfromcollectionsimportdeque datalist(map(int,sys.stdin.read().split()))ndata[0]idx1a[0]*(n1)c[0]*(n1)indeg[0]*(n1)foriinrange(1,n1):c[i]data[idx]idx1foriinrange(1,n1):a[i]data[idx]indeg[a[i]]1idx1qdeque()foriinrange(1,n1):ifindeg[i]0:q.append(i)whileq:uq.popleft()va[u]indeg[v]-1ifindeg[v]0:q.append(v)ans0# 现在剩余的都是环vis[False]*(n1)foriinrange(1,n1):ifindeg[i]0andnotvis[i]:currenti min_costc[i]vis[i]Truecurrenta[current]whilecurrent!i:min_costmin(min_cost,c[current])vis[current]Truecurrenta[current]ansmin_costprint(ans)javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letinput[];rl.on(line,(line){input.push(...line.trim().split(/\s/));});rl.on(close,(){letidx0;constnNumber(input[idx]);constanewArray(n1).fill(0);constcnewArray(n1).fill(0);constindegnewArray(n1).fill(0);for(leti1;in;i){c[i]Number(input[idx]);}for(leti1;in;i){a[i]Number(input[idx]);indeg[a[i]];}constq[];lethead0;for(leti1;in;i){if(indeg[i]0){q.push(i);}}while(headq.length){constuq[head];constva[u];indeg[v]--;if(indeg[v]0){q.push(v);}}letans0;// 现在剩余的都是环constvisnewArray(n1).fill(false);for(leti1;in;i){if(indeg[i]0!vis[i]){letcurrenti;letminCostc[i];vis[i]true;currenta[current];while(current!i){minCostMath.min(minCost,c[current]);vis[current]true;currenta[current];}ansminCost;}}console.log(ans);});Gopackagemainimport(bufiofmtos)funcmain(){in:bufio.NewReader(os.Stdin)varnintfmt.Fscan(in,n)a:make([]int,n1)c:make([]int,n1)indeg:make([]int,n1)fori:1;in;i{fmt.Fscan(in,c[i])}fori:1;in;i{fmt.Fscan(in,a[i])indeg[a[i]]}q:make([]int,0)head:0fori:1;in;i{ifindeg[i]0{qappend(q,i)}}forheadlen(q){u:q[head]headv:a[u]indeg[v]--ifindeg[v]0{qappend(q,v)}}varansint640// 现在剩余的都是环vis:make([]bool,n1)fori:1;in;i{ifindeg[i]0!vis[i]{current:i minCost:c[i]vis[i]truecurrenta[current]forcurrent!i{ifc[current]minCost{minCostc[current]}vis[current]truecurrenta[current]}ansint64(minCost)}}fmt.Println(ans)}