进食后入题目没有保证连通思路题目中每个点都有且只有一条连向其它点的单向边那么整张图是一棵基环树。题目的要求就是每个点有且仅有一条出边所以基环树属于基环内向树。因此所有的警察最终全部会移动到环上。由于小偷可以不移动所以叶子结点上都必须布置警察。由于叶子结点上全都布置了警察所以小偷最终必定会被逼到环上。那么是不是在叶子结点和环上全部布置警察就行了可行但不是最优。很容易发现若环上一开始就布置满警察那么经过足够的步数后必定有叶子结点的警察走到环上并且与环上的警察重叠。这样就造成了浪费。所以环上的每个点我们可以记录一下若一开始就在这里布置一个警察xxx有哪些点布置的警察最终会与警察xxx重叠。那么为什么会有多种情况呢有两种情况。第一种如上图选取两个点中的任意一个都可满足条件。第二种题目中对于wiw_iwi的规定是0≤wi≤1090\le w_i\le10^90≤wi≤109存在代价为零的情况。因此在选好一个方案后剩下的代价为 0 的点都可以选或不选。最终的实现先找环然后计算每个非环点会与环上的哪个警察重叠我写的是倍增最后计算答案和方案。code#includebits/stdc.h#defineintlonglong//#define lc p1//#define rc p1|1#defineendlputchar(\n)#definepspputchar( )usingnamespacestd;typedefunsignedlonglongull;typedeflonglongll;constintN1e65;constintmod998244353;intread(){intx0,f1;charcgetchar();while(c0||c9){if(c-)f-1;cgetchar();}while(c0c9)x(x3)(x1)c-0,cgetchar();returnx*f;}voidprint(intx){if(x0)putchar(-),x-x;if(x10){putchar(x0);return;}print(x/10);putchar(x%100);}voidputstr(string s){for(inti0;is.size();i)putchar(s[i]);}intlowbit(intx){returnx-x;}intn,m,k;intT;intw[N];vectorinta[N];intvis[N];vectorinthas[N];inton[N];intd[N];intleaf[N];intdis[N];intnex[21][N];voidxfs(intfa,intx){nex[0][x]fa;if(vis[x])return;vis[x]1;for(inti0;ia[x].size();i){intya[x][i];xfs(x,y);}}intto[N];voidzfs(intx){if(vis[x])return;vis[x]1;for(inti0;ia[x].size();i){intya[x][i];zfs(y);dis[x]min(dis[x],dis[y]1);to[x]to[y];}}intdont[N];signedmain(){//ios::sync_with_stdio(0);Tread();while(T--){nread();for(inti1;in;i)a[i].clear(),has[i].clear(),on[i]1,leaf[i]0,dis[i]1e9,vis[i]0,nex[0][i]0,to[i]0,dont[i]0;for(inti1;in;i)d[i]0;for(inti1;in;i)w[i]read();for(inti1;in;i){intxread();d[x];a[i].push_back(x);}//找环queueintq;for(inti1;in;i)if(d[i]0)q.push(i),on[i]0,leaf[i]1;while(!q.empty()){intxq.front();q.pop();for(inti0;ia[x].size();i){intya[x][i];if(--d[y]0){on[y]0;q.push(y);}}}for(inti1;in;i){if(on[i]){dis[i]0;}}intans0;for(inti1;in;i)if(leaf[i])answ[i];//叶子必选for(inti1;in;i){if(on[i]!vis[i]){xfs(i,i);}}for(intlen1;len20;len){for(inti1;in;i){if(!on[i])continue;to[i]i;nex[len][i]nex[len-1][nex[len-1][i]];}}for(inti1;in;i){if(!vis[i]){zfs(i);}}for(inti1;in;i){//存储会与当前警察重合的警察if(on[i]){has[i].push_back(i);}else{intonlto[i];inttimdis[i];for(intlen20;len0;len--){if((1len)tim){tim-(1len);onlnex[len][onl];}}if(leaf[i])dont[onl]1;//由于叶子必选所以对应的环上点可以不选elsehas[onl].push_back(i);}}inttot1;for(inti1;in;i){if(!on[i])continue;if(dont[i]){for(intj0;jhas[i].size();j){//处理 0 的情况intyhas[i][j];if(w[y]0)(tot*2)%mod;}}else{intmul1;for(intj0;jhas[i].size();j){intyhas[i][j];if(w[y]0)(mul*2)%mod;}if(mul!1){(tot*(mul-1)%mod)%mod;//每个 0 都可以选或不选但是不能全不选}else{mul0;intmn1e18;//由于需要最优所以只能在最小值里面选for(intj0;jhas[i].size();j){intyhas[i][j];mnmin(mn,w[y]);}ansmn;for(intj0;jhas[i].size();j){intyhas[i][j];if(mnw[y]){mul;}}(tot*(mul)%mod)%mod;}}}print(ans),psp,print((tot%modmod)%mod),endl;}}
P17406 【MX-X31-T2】「FAOI-R14」警察抓小偷
进食后入题目没有保证连通思路题目中每个点都有且只有一条连向其它点的单向边那么整张图是一棵基环树。题目的要求就是每个点有且仅有一条出边所以基环树属于基环内向树。因此所有的警察最终全部会移动到环上。由于小偷可以不移动所以叶子结点上都必须布置警察。由于叶子结点上全都布置了警察所以小偷最终必定会被逼到环上。那么是不是在叶子结点和环上全部布置警察就行了可行但不是最优。很容易发现若环上一开始就布置满警察那么经过足够的步数后必定有叶子结点的警察走到环上并且与环上的警察重叠。这样就造成了浪费。所以环上的每个点我们可以记录一下若一开始就在这里布置一个警察xxx有哪些点布置的警察最终会与警察xxx重叠。那么为什么会有多种情况呢有两种情况。第一种如上图选取两个点中的任意一个都可满足条件。第二种题目中对于wiw_iwi的规定是0≤wi≤1090\le w_i\le10^90≤wi≤109存在代价为零的情况。因此在选好一个方案后剩下的代价为 0 的点都可以选或不选。最终的实现先找环然后计算每个非环点会与环上的哪个警察重叠我写的是倍增最后计算答案和方案。code#includebits/stdc.h#defineintlonglong//#define lc p1//#define rc p1|1#defineendlputchar(\n)#definepspputchar( )usingnamespacestd;typedefunsignedlonglongull;typedeflonglongll;constintN1e65;constintmod998244353;intread(){intx0,f1;charcgetchar();while(c0||c9){if(c-)f-1;cgetchar();}while(c0c9)x(x3)(x1)c-0,cgetchar();returnx*f;}voidprint(intx){if(x0)putchar(-),x-x;if(x10){putchar(x0);return;}print(x/10);putchar(x%100);}voidputstr(string s){for(inti0;is.size();i)putchar(s[i]);}intlowbit(intx){returnx-x;}intn,m,k;intT;intw[N];vectorinta[N];intvis[N];vectorinthas[N];inton[N];intd[N];intleaf[N];intdis[N];intnex[21][N];voidxfs(intfa,intx){nex[0][x]fa;if(vis[x])return;vis[x]1;for(inti0;ia[x].size();i){intya[x][i];xfs(x,y);}}intto[N];voidzfs(intx){if(vis[x])return;vis[x]1;for(inti0;ia[x].size();i){intya[x][i];zfs(y);dis[x]min(dis[x],dis[y]1);to[x]to[y];}}intdont[N];signedmain(){//ios::sync_with_stdio(0);Tread();while(T--){nread();for(inti1;in;i)a[i].clear(),has[i].clear(),on[i]1,leaf[i]0,dis[i]1e9,vis[i]0,nex[0][i]0,to[i]0,dont[i]0;for(inti1;in;i)d[i]0;for(inti1;in;i)w[i]read();for(inti1;in;i){intxread();d[x];a[i].push_back(x);}//找环queueintq;for(inti1;in;i)if(d[i]0)q.push(i),on[i]0,leaf[i]1;while(!q.empty()){intxq.front();q.pop();for(inti0;ia[x].size();i){intya[x][i];if(--d[y]0){on[y]0;q.push(y);}}}for(inti1;in;i){if(on[i]){dis[i]0;}}intans0;for(inti1;in;i)if(leaf[i])answ[i];//叶子必选for(inti1;in;i){if(on[i]!vis[i]){xfs(i,i);}}for(intlen1;len20;len){for(inti1;in;i){if(!on[i])continue;to[i]i;nex[len][i]nex[len-1][nex[len-1][i]];}}for(inti1;in;i){if(!vis[i]){zfs(i);}}for(inti1;in;i){//存储会与当前警察重合的警察if(on[i]){has[i].push_back(i);}else{intonlto[i];inttimdis[i];for(intlen20;len0;len--){if((1len)tim){tim-(1len);onlnex[len][onl];}}if(leaf[i])dont[onl]1;//由于叶子必选所以对应的环上点可以不选elsehas[onl].push_back(i);}}inttot1;for(inti1;in;i){if(!on[i])continue;if(dont[i]){for(intj0;jhas[i].size();j){//处理 0 的情况intyhas[i][j];if(w[y]0)(tot*2)%mod;}}else{intmul1;for(intj0;jhas[i].size();j){intyhas[i][j];if(w[y]0)(mul*2)%mod;}if(mul!1){(tot*(mul-1)%mod)%mod;//每个 0 都可以选或不选但是不能全不选}else{mul0;intmn1e18;//由于需要最优所以只能在最小值里面选for(intj0;jhas[i].size();j){intyhas[i][j];mnmin(mn,w[y]);}ansmn;for(intj0;jhas[i].size();j){intyhas[i][j];if(mnw[y]){mul;}}(tot*(mul)%mod)%mod;}}}print(ans),psp,print((tot%modmod)%mod),endl;}}
