poj3352 Road Construction

2023-11-07 21:32

文章标签 construction road poj3352

本文主要是介绍poj3352 Road Construction，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

It’s almost summer time, and that means that it’s almost summer
construction time! This year, the good people who are in charge of the
roads on the tropical island paradise of Remote Island would like to
repair and upgrade the various roads that lead between the various
tourist attractions on the island.

The roads themselves are also rather interesting. Due to the strange
customs of the island, the roads are arranged so that they never meet
at intersections, but rather pass over or under each other using
bridges and tunnels. In this way, each road runs between two specific
tourist attractions, so that the tourists do not become irreparably
lost.

Unfortunately, given the nature of the repairs and upgrades needed on
each road, when the construction company works on a particular road,
it is unusable in either direction. This could cause a problem if it
becomes impossible to travel between two tourist attractions, even if
the construction company works on only one road at any particular
time.

So, the Road Department of Remote Island has decided to call upon your
consulting services to help remedy this problem. It has been decided
that new roads will have to be built between the various attractions
in such a way that in the final configuration, if any one road is
undergoing construction, it would still be possible to travel between
any two tourist attractions using the remaining roads. Your task is to
find the minimum number of new roads necessary.

Input

The first line of input will consist of positive integers n and r,
separated by a space, where 3 ≤ n ≤ 1000 is the number of tourist
attractions on the island, and 2 ≤ r ≤ 1000 is the number of roads.
The tourist attractions are conveniently labelled from 1 to n. Each of
the following r lines will consist of two integers, v and w, separated
by a space, indicating that a road exists between the attractions
labelled v and w. Note that you may travel in either direction down
each road, and any pair of tourist attractions will have at most one
road directly between them. Also, you are assured that in the current
configuration, it is possible to travel between any two tourist
attractions.

Output

One line, consisting of an integer, which gives the minimum number of
roads that we need to add.

首先用tarjan将边双连通分量缩点，然后得到的是一棵树。
在树上找到找到所有度为1的点，将它们之间相互连边，则可以消除掉所有桥。边数为（度为1的点数+1）/2。

#include<cstring>
#include<cstdio>
int fir[1010],ne[3010],to[3010],bel[1010],dfn[1010],low[1010],tot,cnt,sta[1010],top,du[1010];
void dfs(int p,int fa)
{int i,j,k,x,y,z;dfn[p]=low[p]=++cnt;sta[++top]=p;for (i=fir[p];i;i=ne[i])if (!dfn[to[i]]){dfs(to[i],p);if (low[to[i]]<low[p]) low[p]=low[to[i]];}elseif (to[i]!=fa&&dfn[to[i]]<low[p]) low[p]=dfn[to[i]];if (dfn[p]==low[p]){tot++;do{x=sta[top--];bel[x]=tot;}while (x!=p);}
}
int main()
{int i,j,k,m,n,p,q,x,y,z,ans;scanf("%d%d",&n,&m);for (i=1;i<=m;i++){scanf("%d%d",&x,&y);ne[2*i]=fir[x];fir[x]=2*i;to[2*i]=y;ne[2*i+1]=fir[y];fir[y]=i*2+1;to[2*i+1]=x; }dfs(1,-1);for (i=1;i<=n;i++)for (j=fir[i];j;j=ne[j])if (bel[i]!=bel[to[j]])du[bel[i]]++;ans=0;for (i=1;i<=tot;i++)if (du[i]==1) ans++;printf("%d\n",(ans+1)/2);
}