poj Road Construction
4071 ワード
http://poj.org/problem?id=3352
テーマ:
n個の旅行ポイントm本の道をあげます
任意の2点の間が直接または間接的に通じることが知られており、2点の間には最大1本の直通路(重辺がない)がある.
しかし、ある道路を修理するとこの道路が使えなくなり、ある2点が通じなくなる現象が発生します.
だからもういくつかの道を建てて
任意の2点の間に少なくとも2つの共通エッジのないパスがあります.
少なくとも何辺建てますか?
方法:
1、縮み点
2、新しい木を建てる
3、葉の節点を求めます
注意:
双方向のエッジなので、慎重に処理してください.
リーフノード数を仮定するときv
なぜ最後の答えは(v+1)/2なのか (ルート結点の特審は1つしかありません)
私たちはそう考えることができます.
vが偶数の任意の2つの葉の結点の間に1つの辺がつながっている場合、この2つの葉の結点から根の結点までの経路上の点はすべてリング上にあるので、
少なくともv/2
vが奇数の場合、任意の2点が1つのエッジに直接接続され、残りの1つの点がリングに1つのエッジを追加しないので、少なくとも(v+1)/2
最終的な答えは(v+1)/2です (ルートノードが1つしかない場合を除く)
コードとそのコメント:
テーマ:
n個の旅行ポイントm本の道をあげます
任意の2点の間が直接または間接的に通じることが知られており、2点の間には最大1本の直通路(重辺がない)がある.
しかし、ある道路を修理するとこの道路が使えなくなり、ある2点が通じなくなる現象が発生します.
だからもういくつかの道を建てて
任意の2点の間に少なくとも2つの共通エッジのないパスがあります.
少なくとも何辺建てますか?
方法:
1、縮み点
2、新しい木を建てる
3、葉の節点を求めます
注意:
双方向のエッジなので、慎重に処理してください.
リーフノード数を仮定するときv
なぜ最後の答えは(v+1)/2なのか (ルート結点の特審は1つしかありません)
私たちはそう考えることができます.
vが偶数の任意の2つの葉の結点の間に1つの辺がつながっている場合、この2つの葉の結点から根の結点までの経路上の点はすべてリング上にあるので、
少なくともv/2
vが奇数の場合、任意の2点が1つのエッジに直接接続され、残りの1つの点がリングに1つのエッジを追加しないので、少なくとも(v+1)/2
最終的な答えは(v+1)/2です (ルートノードが1つしかない場合を除く)
コードとそのコメント:
#include<iostream>
#include<cstring>
#include<stack>
#include<cstdio>
#include<math.h>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1005;
struct node
{
struct tt *next;
}mem[N];
struct tt
{
struct tt *next;
int j;
};
struct node1
{
struct tt *next;
}newmem[N];
bool newtree[N][N];
bool in[N];
bool visited[N];
int low[N];
int dfn[N];
stack<int>str;
int deep;
int uppoint[N];
int ans;
void build(int i,int j)
{
struct tt *t=new tt;
t->j=j;
t->next=mem[i].next;
mem[i].next=t;
}
void newbuild(int i,int j)
{
struct tt *t=new tt;
t->j=j;
t->next=newmem[i].next;
newmem[i].next=t;
}
void Clearlist(int n)
{
for(int i=1;i<=n;++i)
{
mem[i].next=NULL;
newmem[i].next=NULL;
}
}
void Tarjan(int pre,int x)
{
++deep;
dfn[x]=low[x]=deep;
in[x]=true;
visited[x]=true;
str.push(x);
struct tt *t=mem[x].next;
while(t!=NULL)
{
if(visited[t->j]==false)
{
Tarjan(x,t->j);
low[x]=min(low[x],low[t->j]);
}else if(in[t->j]==true&&t->j!=pre)//
{
low[x]=min(low[x],dfn[t->j]);
}
t=t->next;
}
if(low[x]==dfn[x])
{
while(str.top()!=x)
{
in[str.top()]=false;
uppoint[str.top()]=x;//
str.pop();
}
in[str.top()]=false;
uppoint[str.top()]=x;
str.pop();
}
}
void dfs(int x)
{
visited[x]=true;
struct tt *t=mem[x].next;
while(t!=NULL)
{
if(uppoint[x]!=uppoint[t->j])
{
newtree[uppoint[x]][uppoint[t->j]]=true;//
newtree[uppoint[t->j]][uppoint[x]]=true;
}
if(visited[t->j]==false)
{
dfs(t->j);
}
t=t->next;
}
}
void findans(int pre,int x)
{
int sum=0;
struct tt *t=newmem[x].next;
while(t!=NULL)
{
if(t->j!=pre)//
{
++sum;
findans(x,t->j);
}
t=t->next;
}
if(sum==0&&x!=1)
++ans;//
}
int main()
{
int n,m;
while(scanf("%d %d",&n,&m)!=EOF)
{
while(m--)
{
int i,j;
scanf("%d %d",&i,&j);
build(i,j);
build(j,i);
}
memset(visited,false,sizeof(visited));
memset(in,false,sizeof(in));
while(!str.empty())
str.pop();
deep=0;
Tarjan(0,1);
memset(visited,false,sizeof(visited));
memset(newtree,false,sizeof(newtree));
dfs(1);//cout<<"TT
";
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
if(newtree[i][j])
{
newbuild(i,j);//
}
}
}
ans=0;
findans(0,1);
printf("%d
",(ans+1)/2);
Clearlist(n);
}
return 0;
}