【拓扑排序+堆】BZOJ3832 [Poi2014]Rally

题面在这里

​

思路太妙了……

首先建立超级源\(S\)向所有点连边，所有点向超级汇\(T\)连边

可以拓扑求出\(S\)到\(x\)的最长路\(f_x\)，以\(x\)到\(T\)的最长路\(g_x\)

那么边\((u,v)\)对应的权值就是\(f_u+g_v-1\)

注意到最长路其实是\(S\)到\(T\)的任意割中所有边的最大权值

这个割把图划分成两个集合：\(S\)集和\(T\)集

一开始除\(S\)点外，所有点都在\(T\)集

按拓扑序将点从\(T\)集转移至\(S\)集

一次转移的过程是：把指向\(x\)的边从割中删去，此时割中最大权值就是\(x\)的答案，再把\(x\)的出边加入割即可

用一个堆维护割即可

​

示例程序：

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;

const int maxn=500005,maxe=2000005,INF=0x3f3f3f3f;
int n,e,ans=INF,p;
int tot,son[maxe],nxt[maxe],lnk[maxn],lnk1[maxn];
inline void add(int x,int y){
	son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;
}
inline void add1(int x,int y){
	son[++tot]=y;nxt[tot]=lnk1[x];lnk1[x]=tot;
}
int que[maxn],in[maxn],f[maxn],g[maxn];
void topo(){
	int hed=0,til=0;
	for (int i=1;i<=n;i++)
	 if (!in[i]) que[++til]=i;
	while (hed!=til){
		int x=que[++hed];
		for (int j=lnk[x];j;j=nxt[j]){
			in[son[j]]--;
			if (!in[son[j]]) que[++til]=son[j];
		}
	}
	for (int i=1;i<=n;i++){
		f[que[i]]=max(f[que[i]],1);
		for (int j=lnk[que[i]];j;j=nxt[j])
		 f[son[j]]=max(f[son[j]],f[que[i]]+1);
	}
	for (int i=n;i>=1;i--){
		g[que[i]]=max(g[que[i]],1);
		for (int j=lnk[que[i]];j;j=nxt[j])
		 g[que[i]]=max(g[que[i]],g[son[j]]+1);
	}
}
priority_queue<int> Q;
int tag[maxn]; 
inline int Top(){
	while (tag[Q.top()]) tag[Q.top()]--,Q.pop();
	return Q.top();
}
inline void Push(int x) {Q.push(x);}
inline void Del(int x) {tag[x]++;}
int main(){
	scanf("%d%d",&n,&e);
	for (int i=1,x,y;i<=e;i++) scanf("%d%d",&x,&y),add(x,y),add1(y,x),in[y]++;
	topo();
	for (int i=1;i<=n;i++) Push(g[i]);
	Push(0);
	for (int i=1;i<=n;i++){
		int x=que[i];
		for (int j=lnk1[x];j;j=nxt[j]) Del(f[son[j]]+g[x]);
		Del(g[x]);
		int t=Top();
		if (t<ans) ans=t,p=x;
		for (int j=lnk[x];j;j=nxt[j]) Push(f[x]+g[son[j]]);
		Push(f[x]);
	}
	printf("%d %d",p,ans-1);
	return 0;
}