网站建设的功能需求分析策划书,开发新闻类网站,厦门同安区建设局网站,模板网站最大缺点题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/373/C 来源#xff1a;牛客网
Q市发生了一起特大盗窃案。这起盗窃案是由多名盗窃犯联合实施的,你要做的就是尽可能多的抓捕盗窃犯。 已知盗窃犯分布于 N N个地点,以及第 i i个地点初始有 ai ai名盗…题干
链接https://ac.nowcoder.com/acm/contest/373/C 来源牛客网
Q市发生了一起特大盗窃案。这起盗窃案是由多名盗窃犯联合实施的,你要做的就是尽可能多的抓捕盗窃犯。 已知盗窃犯分布于 N N个地点,以及第 i i个地点初始有 ai ai名盗窃犯。 特别的是对于每一个地点 u u,都有一个固定的地点 v v--当前如果某个盗窃犯位于地点 u u,在下一个时刻他会移动到地点 v v。 你需要通过初始时在某些点设置哨卡来捉住他们。 现在你可以在 M M个地点设置哨卡,如果在某个地点设置哨卡,你可以抓获在任一时刻经过该地点的盗窃犯。 也就是说,哨卡存在的时间是无限长,但哨卡不能移动。
输入描述:
第一行两个整数 N,M(1≤N,M≤105) N,M(1≤N,M≤105)。
第二行 N N个整数 a1a2...aN a1a2...aN (0≤a1,a2,...aN≤105) (0≤a1,a2,...aN≤105),表示第 i i个地点初始有 ai ai名盗窃犯。
第三行 N N个整数 v1v2...vN v1v2...vN (1≤v1,v2,...vN≤N) (1≤v1,v2,...vN≤N),表示当前处于地点 i i的盗窃犯下一个时刻会移动到地点 vi vi。
输出描述:
输出一行一个整数--能够抓捕到的最大数量。
示例1
输入
复制
8 2
1 2 3 4 1 2 3 12
2 3 3 3 6 7 5 8
输出
复制
22
说明
对于样例一一种可行的方案是在地点3、地点8分别设置一个哨卡此时答案为12341222
示例2
输入
复制
8 2
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 8
输出
复制
36
说明
对于样例二一种可行的方案是在地点2、地点8分别设置一个哨卡此时答案为1234567836
解题报告
注意到每个点的入度虽然不唯一但是每个点的出度一定为1.也就是说只要这个图是联通的那么一定能都汇集到同一个点上。所以我们只需要看看有多少个连通图就可以这个过程可以用dfs来实现也可以用并查集 。最后贪心出答案来。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e5 5;
ll n,m;
ll num[MAX];
int nt[MAX];
ll val[MAX];
int tot;
bool vis[MAX];
ll tmp;
vectorint vv[MAX];
void dfs(int cur,int root) {vis[cur] 1;tmp num[cur];int up vv[cur].size();for(int i 0; iup; i) {int v vv[cur][i];if(vis[v] 0) dfs(v,cur);}
}
int main()
{cinnm;for(int i 1; in; i) scanf(%lld,numi);for(int i 1; in; i) {scanf(%d,nti);vv[i].pb(nt[i]);vv[nt[i]].pb(i);}for(int i 1; in; i) {if(!vis[i]) {tmp 0;dfs(i,-1);val[tot] tmp;}}sort(val1,valtot1);ll ans 0;for(int i tot; imax(0LL,tot-m); i--) {ans val[i];}printf(%lld\n,ans);return 0 ;}1WA了最下面tot写成了 tmp、、
