Beyond the Void
BYVoid
pku 3177 (3352) Redundant Paths
本文正體字版由OpenCC轉換

題目大意是,給定一個連通圖,要求添加一些邊,使每兩個頂點之間都有至少兩條不相交的路徑,求最小需要添加的邊數。

很顯然,題中要求的圖就是一個邊雙連通圖,即邊連通度不小於2。我的方法是在原圖中DFS求出所有的橋,然後刪除這些橋邊,剩下的每個連通塊都是一個雙連通子圖。把每個雙連通子圖收縮爲一個頂點,再把橋邊加回來,最後的這個圖一定是一棵樹,邊連通度爲1。統計出樹中度爲1的節點的個數,即爲葉節點的個數,記爲leaf。有人說至少在樹上添加(leaf+1)/2條邊,就能使樹達到邊二連通,所以結果就是(leaf+1)/2。

這個結論我不能證明,但是可以想象出是對的。簡單說明一下,首先把兩個最近公共祖先最遠的兩個葉節點之間連接一條邊,這樣可以把這兩個點到祖先的路徑上所有點收縮到一起,因爲一個形成的環一定是雙連通的。然後再找兩個最近公共祖先最遠的兩個葉節點,這樣一對一對找完,恰好是(leaf+1)/2次,把所有點收縮到了一起。

這道題跟pku3352一模一樣,拿這個程序交兩個題一個字不用改都能AC!但實際上兩個題也稍有不同,這個題有一點很不容易被注意到,就是可能存在重邊,兩個點之間如果存在有重邊,也算是雙連通的。我的處理方法是在DFS時標記每條邊及其反向邊是否被訪問過,而不是判斷頂點。

/* 
 * Problem: pku3177 Redundant Paths (USACO JAN06)
 * Author: Guo Jiabao
 * Time: 2009.4.7 19:37
 * State: Solved
 * Memo: 橋 雙連通分支
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=5001,MAXM=10001*2*2;
using namespace std;
struct edge
{
	edge *next,*op;
	int t;
	bool vis;
}ES[MAXM];
edge *V[MAXN],*PAR[MAXN];
int N,M,EC=-1,D,Ans;
int DFN[MAXN],LOW[MAXN],Bel[MAXN],Deg[MAXN];
bool adjm[MAXN][MAXN];
inline void addedge(int a,int b)
{
	ES[++EC].next=V[a];
	V[a]=ES+EC;V[a]->t=b;V[a]->vis=false;
	ES[++EC].next=V[b];
	V[b]=ES+EC;V[b]->t=a;V[b]->vis=false;
	V[a]->op=V[b];V[b]->op=V[a];
}
void init()
{
	int i,a,b;
	freopen("rpaths.in","r",stdin);
	freopen("rpaths.out","w",stdout);
	scanf("%d%d",&N,&M);
	for (i=1;i<=M;i++)
	{
		scanf("%d%d",&a,&b);
		addedge(a,b);
	}
}
void dfs(int u)
{
	DFN[u]=LOW[u]=++D;
	for (edge *k=V[u];k;k=k->next)
	{
		int v=k->t;
		if (k->vis) continue;
		k->vis=k->op->vis=true;
		if (!DFN[v])
		{
			PAR[v]=k->op;
			dfs(v);
			if (LOW[v]<LOW[u])
				LOW[u]=LOW[v];
		}
		else if (DFN[v]<LOW[u])
			LOW[u]=DFN[v];
	}
}
void part(int u)
{
	Bel[u]=D;
	for (edge *k=V[u];k;k=k->next)
		if (k->vis && !Bel[k->t])
			part(k->t);
}
void solve()
{
	int i,u,v,leaf=0;
	edge *k;
	dfs(1);
	for (v=2;v<=N;v++)
	{
		k=PAR[v];
		u=k->t;
		if (DFN[u]<LOW[v])
			k->vis=k->op->vis=false;//標記爲橋邊
	}
	D=0;
	for (u=1;u<=N;u++)
	{
		if (!Bel[u])
		{
			++D;
			part(u);
		}
	}
	for (u=1;u<=N;u++)
		for (k=V[u];k;k=k->next)
			adjm[Bel[u]][Bel[k->t]]=adjm[Bel[k->t]][Bel[u]]=true;
	for (u=1;u<=D;u++)
		for (v=1;v<=D;v++)
			if (u!=v && adjm[u][v])
				Deg[u]++;
	for (i=1;i<=D;i++)
		if (Deg[i]==1)
			leaf++;
	if (leaf!=1)
		Ans=(leaf+1)/2;
	else
		Ans=0;
}
int main()
{
	init();
	solve();
	printf("%dn",Ans);
	return 0;
}

上次修改時間 2017-02-03

相關日誌