首页 > 代码库 > bzoj4331: JSOI2012 越狱老虎桥
bzoj4331: JSOI2012 越狱老虎桥
Description
这里，是美丽的南京；这里，是秀美的进香河；这里是安逸的老虎桥。
如果说进香河的美，美在其秀美的风光，倒不如说是美在了那惬意的南京古典小巷式生活。如果说进香河的迷人，在其淳朴的民风，倒不如说是那被历史掩埋了的秘密吸引着人们好奇的心。
也许很多人都还记得，老虎桥监狱，北洋时期江南最大的监狱，在近一个世纪中，面对满清、北洋、民国、新中国几朝兴衰，名称屡次更替，沧桑尽显其中。
现在的人们，恐怕很难相信，到底有多少惊心动魄的事情曾经就在这里上演。
那是1948年的冬天，南京地下组织的一支小分队决定偷袭老虎桥监狱，救出被困的数百名人员。那时的老虎桥监狱，被N层电网围了起来，由内而外，依次编号为1,2,…,N。第1层电网接有高压电。有M条高压线，连接了所有电网，其中第i条高压线连接了第ai和bi层电网，如果要破坏第i条高压线，需要至少动用Ti位特工。面对这么多层电网，偷袭小分队犯愁了。至少需要破坏一层电网，否则是无法偷袭成功的。
然而，狡猾的间谍却知道了这件事情，为了破坏偷袭计划，敌人秘密地又增加了一条高压线，不让偷袭小分队的成员发现。
为了能够偷袭成功，不论新增的这一条秘密高压线是连接哪两层电网的，小分队都必须要破坏且仅破坏一条高压线，使得至少有一层电网不通电。注意，对于新增的高压线，我们并不知道需要多少位特工才能成功破坏。现在的问题是，偷袭小分队至少需要多少名特工呢？
决战就在今夜！
Input
第一行有2个整数，N和M，分别表示电网层数和高压线个数。
之后M行，每行3个整数，分别是ai, bi和Ti。
Output
输出只有一行，包含一个整数，表示最少需要动用的特工人数。
如果计划必然失败，则输出 -1。
边双联通分量内的边删了不影响联通情况，所以先缩点，留下割边，问题转化为在树上选一条路径，使未被覆盖的边的最小值最大，可以直接树形dp
#include<cstdio>#define G *++ptrconst int N=500007,inf=0x3f3f3f3f;char buf[N*60],*ptr=buf-1;int _(){ int x=0,c=G; while(c<48)c=G; while(c>47)x=x*10+c-48,c=G; return x;}bool ei[N*4];int n,m,es[N*6],enx[N*6],ev[N*6],e0[N],e1[N],ep=2,id[N],idp;void ae(int*e,int a,int b,int c){ es[ep]=b;enx[ep]=e[a];ev[ep]=c;e[a]=ep++; es[ep]=a;enx[ep]=e[b];ev[ep]=c;e[b]=ep++;}int dfn[N],low[N],tk=0;void mins(int&a,int b){if(a>b)a=b;}void maxs(int&a,int b){if(a<b)a=b;}int min(int a,int b){return a<b?a:b;}int max(int a,int b){return a>b?a:b;}void tj(int w){ dfn[w]=low[w]=++tk; for(int i=e0[w];i;i=enx[i]){ int u=es[i]; if(!u)continue; if(!dfn[u]){ es[i^1]=0; tj(u); es[i^1]=w; mins(low[w],low[u]); if(low[u]>dfn[w])ei[i>>1]=1; }else mins(low[w],dfn[u]); }}void f1(int w){ id[w]=idp; dfn[w]=0; for(int i=e0[w];i;i=enx[i]){ int u=es[i]; if(!ei[i>>1]&&dfn[u])f1(u); }}int v0[N],v02[N],v1[N],v2[N],vu[N],v,ans=0;void f2(int w,int pa){ v0[w]=v02[w]=v1[w]=v2[w]=vu[w]=inf; for(int i=e1[w];i;i=enx[i]){ int u=es[i]; if(u==pa)continue; f2(u,w); v=min(v0[u],ev[i]); v2[w]=max(min(v2[w],v),min(v1[w],v1[u])); v1[w]=max(min(v1[w],v),min(v0[w],v1[u])); if(v<=v0[w])v02[w]=v0[w],v0[w]=v; else mins(v02[w],v); }}void f3(int w,int pa){ v=min(vu[w],v2[w]); maxs(ans,v); for(int i=e1[w];i;i=enx[i]){ int u=es[i]; if(u==pa)continue; vu[u]=min(min(ev[i],vu[w]),min(v0[u],ev[i])==v0[w]?v02[w]:v0[w]); f3(u,w); }}int main(){ fread(buf,1,sizeof(buf),stdin)[buf]=0; n=_();m=_(); for(int i=0,a,b,c;i<m;++i){ a=_();b=_();c=_(); if(a==b)continue; ae(e0,a,b,c); } tj(1);for(int i=1;i<=n;++i)if(dfn[i]){ ++idp; f1(i); } for(int i=2;i<ep;i+=2)if(ei[i>>1])ae(e1,id[es[i]],id[es[i^1]],ev[i]); f2(1,0); f3(1,0); if(ans==inf)ans=-1; printf("%d",ans); return 0;}
bzoj4331: JSOI2012 越狱老虎桥
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。