BZOJ3832: [Poi2014]Rally
https://lydsy.com/JudgeOnline/problem.php?id=3832
分析:
- 新建源点向所有点连边，所有点向汇点连边。
- 设\(f\)表示到这个点的最长路，\(g\)表示从这个点出发的最长路。
- 那么一条边\((u,v)\)的贡献就是\(f_u+g_v+1\)。
- 考虑用堆维护所有的边。堆中一开始无边。
- 按拓扑序删点，删一个点之前删掉连向它的边，统计答案后再加入它连出的边。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define N 1000050
template <typename T> void chkmax(T &x,T y) {if(x<y) x=y;}
template <typename T> void chkmin(T &x,T y) {if(y<x) x=y;}
int head[N],to[N<<1],nxt[N<<1],cnt,n,m,Q[N],du[N],f[N],g[N],vis[N];
priority_queue<int>q;
vector<int>v[N];
inline void add(int u,int v) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;
}
int main() {
scanf("%d%d",&n,&m);
int s=n+1,t=n+2;
int i,x,y,l=0,r=0;
for(i=1;i<=m;i++) scanf("%d%d",&x,&y),add(x,y),du[y]++,v[y].push_back(x);
for(i=1;i<=n;i++) add(s,i),add(i,t),v[i].push_back(s),v[t].push_back(i),du[i]++,du[t]++;
Q[r++]=s;
while(l<r) {
x=Q[l++];
for(i=head[x];i;i=nxt[i]) {
du[to[i]]--;
chkmax(f[to[i]],f[x]+1);
if(!du[to[i]]) Q[r++]=to[i];
}
}
for(y=r-1;y>=0;y--) {
x=Q[y];
int lim=v[x].size();
for(i=0;i<lim;i++) {
chkmax(g[v[x][i]],g[x]+1);
}
}
int ans=1<<30,p=0;
for(y=0;y<r;y++) {
x=Q[y];
int lim=v[x].size();
for(i=0;i<lim;i++) {
vis[f[v[x][i]]+g[x]+1]++;
}
while(!q.empty()&&vis[q.top()]) vis[q.top()]--,q.pop();
if(!q.empty()) {
if(ans>q.top()) {
ans=q.top(); p=x;
}
}
for(i=head[x];i;i=nxt[i]) q.push(f[x]+g[to[i]]+1);
}
printf("%d %d\n",p,ans-2);
}