正文

bzoj4331:jsoi2012越狱老虎桥

ccz181078  2022-02-09  536

关键词：

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 *++ptr
const 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;
}

bzoj2733[hnoi2012]永无乡线段树合并

Description永无乡包含n座岛，编号从1到n，每座岛都有自己的独一无二的重要度，按照重要度可以将这n座岛排名，名次用1到n来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛a出发经过若干座（含... 查看详情

[bzoj2733][hnoi2012]永无乡(splay启发式合并)

Description　　永无乡包含n座岛，编号从1到n，每座岛都有自己的独一无二的重要度，按照重要度可以将这n座岛排名，名次用1到n来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛a出发经过若干座... 查看详情

[bzoj2733][p3224][hnoi2012]永无乡[平衡树+启发式合并+并查集]

合并和查询kth查询kth是裸的平衡树操作，合并时将size小的合并到size大的上面，用并查集维护联通关系Description永无乡包含n座岛，编号从1到n，每座岛都有自己的独一无二的重要度，按照重要度可以将这n座岛排名，名次用1到n来... 查看详情

bzoj_2622_[2012国家集训队测试]深入虎穴_最短路

...scription虎是中国传统文化中一个独特的意象。我们既会把老虎的形象用到喜庆的节日装饰画上，也可能把它视作一种邪恶的可怕的动物，例如“武松打虎”或者“三人成虎”。“不入虎穴焉得虎子”是一个对虎... 查看详情

bzoj3504:[cqoi2014]危桥网络流

一种网络流建图的思路吧，改天最好整理一波网络流建图思路1#include<bits/stdc++.h>2usingnamespacestd;3intn,h,t,a1,a2,an,b1,b2,bn,flow,now;charch;4intdis[52],l[52],d[52][52];charc[52][52];5chargetch()6{7for(ch=getchar();ch!=‘O 查看详情

bzoj2157:旅游

DescriptionRay乐忠于旅游，这次他来到了T城。T城是一个水上城市，一共有N个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T城的任意两个景点之间有且只有一条路径。换句话说，T城中只有N?... 查看详情

[bzoj2157]旅游

题面戳我DescriptionRay乐忠于旅游，这次他来到了T城。T城是一个水上城市，一共有N个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T城的任意两个景点之间有且只有一条路径。换句话说，T... 查看详情

bzoj2157旅行模拟

题目内容：Ray乐忠于旅游，这次他来到了T城。T城是一个水上城市，一共有N个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T城的任意两个景点之间有且只有一条路径。换句话说，T城中只... 查看详情

bzoj2157旅游(代码片段)

题目描述Ray乐忠于旅游，这次他来到了T城。T城是一个水上城市，一共有N个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T城的任意两个景点之间有且只有一条路径。换句话说，T城中只有N... 查看详情

bzoj_2157_旅游_树剖+线段树

BZOJ_2157_旅游_树剖+线段树DescriptionRay乐忠于旅游，这次他来到了T城。T城是一个水上城市，一共有N个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T城的任意两个景点之间有且只有一条路径... 查看详情

bzoj1008:[hnoi2008]越狱

BZOJ1008:[HNOI2008]越狱Description　　监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱Input　　输入... 查看详情

bzoj1008越狱题解裸快速幂

BZOJ1008越狱题解裸快速幂1008:[HNOI2008]越狱TimeLimit: 1Sec MemoryLimit: 162MBSubmit: 7887 Solved: 3372[Submit][Status][Discuss]Description　　监狱有连续编号为1. 查看详情

bzoj1008越狱

...其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱Input　　输入两个整数M，N.1<=M<=10^8,1<=N<=10^12Output　　可能越狱的状态数，模100003取余SampleInput23SampleOutput 查看详情

[bzoj1008][hnoi2008]越狱(数学)

bzoj1008:[hnoi2008]越狱

1008:[HNOI2008]越狱TimeLimit: 1Sec MemoryLimit: 162MBDescription　　监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求... 查看详情

[tjoi2012]桥(代码片段)

Description有n个岛屿，m座桥，每座桥连通两座岛屿，桥上会有一些敌人，玩家只有消灭了桥上的敌人才能通过，与此同时桥上的敌人会对玩家造成一定伤害。而且会有一个大Boss镇守一座桥，以玩家目前的能力，是不可能通过的。... 查看详情

[bzoj]1008:[hnoi2008]越狱

bzoj1008[hnoi2008]越狱

1008:[HNOI2008]越狱TimeLimit: 1Sec MemoryLimit: 162MBSubmit: 9635 Solved: 4160[Submit][Status][Discuss]Description　　监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰查看详情