【BZOJ 2238】Mst

【題目】

題目描述：

給出一個 n n n 個點 m m m 條邊的無向帶權圖，以及 q q q 個詢問，每次詢問在圖中删掉一條邊後圖的最小生成樹。（各詢問間獨立，每次詢問不會對之後的詢問産生影響，即被删掉的邊在下一條詢問中依然存在）

輸入格式：

第一行兩個正整數 n , m ( n ≤ 50000 , m ≤ 100000 ) n,m(n≤50000,m≤100000) n,m(n≤50000,m≤100000) 表示原圖的頂點數和邊數。

下面 m m m 行，每行三個整數 x , y , w x,y,w x,y,w 描述了圖的一條邊 ( x , y ) (x,y) (x,y)，其邊權為 w ( w ≤ 10000 ) w(w≤10000) w(w≤10000)。保證兩點之間至多隻有一條邊。

接着一行一個正整數 q q q，表示詢問數。 ( 1 ≤ q ≤ 100000 ) (1≤q≤100000) (1≤q≤100000)

下面 q q q 行，每行一個詢問，詢問中包含一個正整數 t t t，表示把編号為 t t t 的邊删掉(邊從 1 1 1 到 m m m 按輸入順序編号)。

輸出格式：

q q q 行，對于每個詢問輸出對應最小生成樹的邊權和的值，如果圖不連通則輸出 “Not connected”

樣例資料：

輸入

4 4

1 2 3

1 3 5

2 3 9

2 4 1

4

1

2

3

4

輸出

15

13

9

Not connected

資料規模：

10 % 10\% 10% 的資料 n , m , q ≤ 100 n,m,q\le 100 n,m,q≤100。

另外 30 % 30\% 30% 的資料， n ≤ 1000 n\le 1000 n≤1000。

100 % 100\% 100% 的資料如題目。

【分析】

一道比較妙的題

首先用 k r u s k a l kruskal kruskal 把整張圖的最小生成樹求出來

如果要删掉的邊是非樹邊，那答案就是最小生成樹的值，現在考慮删掉樹邊

對于一條樹邊，考慮哪些非樹邊可以"代替"它（也就是删掉這條樹邊，加上非樹邊後依舊是一顆生成樹）

不難發現的是，隻有這條樹邊在非樹邊兩端點的簡單路徑上，那才可以被替代

是以我們就從能把它替代的所有非樹邊中找出最短的一條，那此時的最小生成樹自然是最小的

如果用 Min[i] 表示能替代 i i i 這條邊的最短非樹邊的話，那麼就枚舉每條非樹邊，對于這條非樹邊兩端點的簡單路徑上的所有樹邊取個 min(Min[i],w[i]),w[i] 是邊權（就是預處理出 Min[i]）

查詢的時候 ans=MST-w[x]+Min[x]，MST 是最小生成樹的值

是以用樹鍊剖分維護鍊修改，用線段樹維護區間取 m i n min min

然後，Not connected 有兩種情況：

1. 在不删邊的情況下就已經不連通，全部輸出 Not connected
2. 沒有發現能替代目前樹邊的非樹邊，輸出 Not connected

注意轉邊為點

【代碼】

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 50005
#define M 200005
#define inf 0x3f3f3f3f
using namespace std;
int n,m,q,t,tot;
int first[N],v[M],nxt[M];
int father[N],ID[M],Min[N<<2],mark[N<<2];
int fa[N],dep[N],son[N],top[N],pos[N],Size[N];
bool tree[M];
struct edge{int u,v,w,id;}e[M];
bool comp1(const edge &p,const edge &q){return p.w<q.w;}
bool comp2(const edge &p,const edge &q){return p.id<q.id;}
int find(int x)
{
	if(father[x]==x)  return x;
	return father[x]=find(father[x]);
}
void add(int x,int y)
{
	nxt[++t]=first[x];
	first[x]=t,v[t]=y;
}
int Kruskal()
{
	int x,y,i,ans=0,tot=0;
	sort(e+1,e+m+1,comp1);
	for(i=1;i<=n;++i)  father[i]=i;
	for(i=1;i<=m;++i)
	{
		x=find(e[i].u);
		y=find(e[i].v);
		if(x!=y)
		{
			father[y]=x;
			tot++,ans+=e[i].w;
			tree[e[i].id]=true;
			add(e[i].u,e[i].v),add(e[i].v,e[i].u);
		}
	}
	sort(e+1,e+m+1,comp2);
	return (tot==n-1)?ans:-1;
}
void dfs1(int x)
{
	int i,k;
	Size[x]=1;
	for(i=first[x];i;i=nxt[i])
	{
		if((k=v[i])==fa[x])  continue;
		fa[k]=x,dep[k]=dep[x]+1,dfs1(k),Size[x]+=Size[k];
		if(Size[son[x]]<Size[k])  son[x]=k;
	}
}
void dfs2(int x,int tp)
{
	int i;
	top[x]=tp,pos[x]=++tot;
	if(son[x])  dfs2(son[x],top[x]);
	for(i=first[x];i;i=nxt[i])
	  if(v[i]!=son[x]&&v[i]!=fa[x])
	    dfs2(v[i],v[i]);
}
void pushnow(int root,int z)
{
	Min[root]=min(Min[root],z);
	mark[root]=min(mark[root],z);
}
void pushdown(int root)
{
	if(mark[root]==inf)  return;
	pushnow(root<<1,mark[root]),pushnow(root<<1|1,mark[root]);
	mark[root]=0x3f3f3f3f;
}
void modify(int root,int l,int r,int x,int y,int z)
{
	if(l>=x&&r<=y)
	{
		pushnow(root,z);
		return;
	}
	pushdown(root);
	int mid=(l+r)>>1;
	if(x<=mid)  modify(root<<1,l,mid,x,y,z);
	if(y>mid)  modify(root<<1|1,mid+1,r,x,y,z);
	Min[root]=min(Min[root<<1],Min[root<<1|1]);
}
void change(int x,int y,int z)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])  swap(x,y);
		modify(1,1,n,pos[top[x]],pos[x],z),x=fa[top[x]];
	}
	if(dep[x]>dep[y])  swap(x,y);
	modify(1,1,n,pos[x]+1,pos[y],z);
}
int query(int root,int l,int r,int x)
{
	if(l==r)  return Min[root];
	pushdown(root);int ans=inf,mid=(l+r)>>1;
	if(x<=mid)  ans=min(ans,query(root<<1,l,mid,x));
	else  ans=min(ans,query(root<<1|1,mid+1,r,x));
	return ans;
}
int main()
{
	int x,y,z,i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i)
	  scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w),e[i].id=i;
	scanf("%d",&q);
	int MST=Kruskal();
	dfs1(1),dfs2(1,1);
	memset(Min,0x3f,sizeof(Min));
	memset(mark,0x3f,sizeof(mark));
	for(i=1;i<=m;++i)
	  if(!tree[i])
	    change(e[i].u,e[i].v,e[i].w);
	for(i=1;i<=q;++i)
	{
		scanf("%d",&x);
		if(MST==-1)  puts("Not connected");
		else  if(!tree[x])  printf("%d\n",MST);
		else
		{
			int ans=query(1,1,n,max(pos[e[x].u],pos[e[x].v]));
			if(ans==inf)  puts("Not connected");
			else  printf("%d\n",MST-e[x].w+ans);
		}
	}
	return 0;
}