[SHOI2010]最小生成树 - A-Failure的博客

题目

题目描述

~~不放图了烦死~~

给定一个无向连通图，每次可以花$1$的代价选择一条边，使得除这条边的其他边边权$-1$，给定一条边，求使得给定边是当前图最小生成树的必需边需要的代价最小是多少

输入输出格式

输入格式：

输入文件的第一行有3个正整数 $n,m,Lab$ 分别表示无向图中的点数、边数、必须要在最小生成树中出现的AB边的标号。

接下来 $m$ 行依次描述标号为 $1,2,3 \ldots m$ 的无向边，每行描述一条边。每个描述包含3个整数 $x,y,d$ ，表示这条边连接着标号为 $x,y$ 的点，且这条边的权值为 $d$ 。

输入文件保证 $1 \leq x,y \leq N$ ， $x \neq y$ ，且输入数据保证这个无向图一定是一个连通图。

输出格式：

输出文件只有一行，这行只有一个整数，即，使得标号为 $Lab$ 边一定出现最小生成树中的最少操作次数。

输入输出样例

输入样例#1：

输出样例#1：

说明

$1 \leq N \leq 500,1 \leq M \leq 800,1 \leq d<10^6$

题解

首先这个操作相当于选定一条边使边权$+1$，考虑求最小生成树的过程，边权大于$d_{Lab}$的一定不会对$Lab$产生影响，当$Lab$不（一定）能加入到生成树的情况为$x_{Lab}$和$y_{Lab}$能被边权不大于$d_{Lab}$的边连通

所以对于边$t$，可以花费$d_{Lab}-d_t+1$的花费移动到$Lab$后面，即消除$t$的影响，现在即删掉一些边后使得$x_{Lab}$和$y_{Lab}$不连通，这样就是个最小割问题了

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=1e5+5;
struct p{
	int x,y,dis;
	bool operator< (const p &a)
	const{
		return dis<a.dis;
	}
}c[MAX],cc[MAX];
int n,m,num=1,lab,S,T,D;
int h[MAX],H[MAX],d[MAX],qu[MAX];
int read()
{
	int x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
void add(int x,int y,int dis)
{
	c[++num]=(p){h[x],y,dis},h[x]=num;
	c[++num]=(p){h[y],x,dis},h[y]=num;
}
bool bfs()
{
	memset(d,0,sizeof(d));
	int hl=1,tl=d[S]=1;
	qu[1]=S;
	while(hl<=tl)
	{
		int tt=qu[hl++];
		for(int i=h[tt];i;i=c[i].x)
		  if(!d[c[i].y]&&c[i].dis)
		  {
		  	d[c[i].y]=d[tt]+1,qu[++tl]=c[i].y;
		  	if(c[i].y==T) return 1;
		  }
	}
	return 0;
}
int dfs(int x=S,int dix=1e8)
{
	if(x==T||!dix) return dix;
	int sum=0;
	for(int &i=H[x],dis;i;i=c[i].x)
	  if(d[c[i].y]==d[x]+1&&c[i].dis)
	  {
	  	dis=dfs(c[i].y,min(dix,c[i].dis));
	  	if(dis)
	  	{
	  		sum+=dis,dix-=dis,c[i].dis-=dis,c[i^1].dis+=dis;
	  		if(!dix) break;
		}
	  }
	if(!sum) d[x]=-2;
	return sum;
}
int Dinic()
{
	int tot=0,D;
	while(bfs())
	{
		memcpy(H,h,sizeof(h));
		while(D=dfs()) tot+=D;
	}
	return tot;
}
int main()
{
	n=read(),m=read(),lab=read();
	for(int i=1;i<=m;++i)
	  cc[i].x=read(),cc[i].y=read(),cc[i].dis=read();
	S=cc[lab].x,T=cc[lab].y,D=cc[lab].dis,sort(cc+1,cc+1+m);
	for(int i=1;cc[i].dis<=D&&i<=m;++i)
	  if(cc[i].x!=S||cc[i].y!=T) add(cc[i].x,cc[i].y,D-cc[i].dis+1);
	return printf("%d",Dinic()),0;
}

题目