题目链接:

http://172.16.0.132/senior/#main/show/5465

题目:

小X所居住的X国共有n个城市,有m条无向道路将其连接。作为一个统一的国家,X 城的任意两个城市都可以相互到达。
由于X国正处于地震带上,有时X国中会有至多一条道路发生毁坏,无法使用。如果这条道路的毁坏恰好阻断了某些城市的往来,那么我们称这条道路是危险的。
人们并不喜欢危险的道路,于是人们决定重建恰好一条道路,以减少危险的道路数。请告诉人们,重建恰好一条道路后,危险的道路数最少是多少。

题解:

显然在一个边双里,任意删掉一条边依旧是连通的,也就是说危险的道路其实就是桥

因此我们缩边双,建新图

注意到缩掉所有的边双之后图会变成一棵树,我们就是要在这棵树连边,使得上形成的环最大,环上的边本来是危险的,现在不危险了

显然我们要连的是直径的两个端点,求一遍树的直径就好了

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<time.h>
#define mem(x,y) memset(x,y,sizeof(x))
using namespace std; const int N=2e5+;
const int M=1e6+;
int n,m,tot1,tot2,tim,tp,mx,pos;
int h1[N],h2[N],dfn[N],vis[N],belong[N],low[N];
bool brige[M<<];
struct E{
int to,nxt;
}e1[M<<],e2[M<<];
inline char nc(){
static char buf[],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
char ch=nc();int s=,f=;
while (ch<''||ch>'') {if (ch=='-') f=-;ch=nc();}
while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=nc();}
return s*f;
}
void link1(int u,int v){e1[++tot1]=(E){v,h1[u]};h1[u]=tot1;}
void link2(int u,int v){e2[++tot2]=(E){v,h2[u]};h2[u]=tot2;}
void chkmin(int &x,int y){if (y<x) x=y;}
void init(){
mem(h1,);mem(h2,);mem(dfn,);mem(low,);mem(brige,);
tot1=tot2=;
tim=tp=;
}
void tarjan(int x,int pre){
dfn[x]=low[x]=++tim;
for (int i=h1[x];i;i=e1[i].nxt){
int y=e1[i].to;
if (!dfn[y]){
tarjan(y,i);
chkmin(low[x],low[y]);
if (low[y]>dfn[x]) brige[i]=brige[i^]=;
}
else if (i!=(pre^)) chkmin(low[x],dfn[y]);
}
}
void dfs(int x,int edcc){
belong[x]=edcc;vis[x]=;
for (int i=h1[x],y;i;i=e1[i].nxt){
if (vis[y=e1[i].to]||brige[i]) continue;
dfs(y,edcc);
}
}
void dfs1(int x,int len,int pre){
if (len>mx) mx=len,pos=x;
for (int i=h2[x],y;i;i=e2[i].nxt){
if ((y=e2[i].to)==pre) continue;
dfs1(y,len+,x);
}
}
int main(){
freopen("rebuild.in","r",stdin);
freopen("rebuild.out","w",stdout);
while ()
{
n=read();m=read();
if (!n&&!m) break;
init();
for (int i=,u,v;i<=m;i++){
u=read();v=read();link1(u,v);link1(v,u);
}
tarjan(,-);
mem(vis,);
int cnt=;
for (int i=;i<=n;i++) if (!vis[i]) dfs(i,++cnt);
for (int x=;x<=n;x++)
for (int i=h1[x];i;i=e1[i].nxt){
int y=e1[i].to;
if (belong[x]==belong[y]) continue;
link2(belong[x],belong[y]);
}
mx=;
dfs1(,,-);
mx=;
dfs1(pos,,-);
printf("%d\n",cnt-mx);
}
return ;
}
05-11 05:05
查看更多