题目描述
经过旷久的战争，ZMiG和707逐渐培养出了深厚的感♂情。他们逃到了另一块大陆上，决定远离世间的纷争，幸福地生活在一起。钟情707的neither_nor决心要把他们拆散，他要动用手中最大杀器之一——超时空传送仪来分开ZMiG和707。ZMiG和707所在的大陆可以被描述成N个点M条边的有向无环图。707和ZMiG自带魔法防御，neither_nor只可以用超时空传送仪把707传送到一个点，再把ZMiG传送到一个能到达707所在点的点，然后为ZMiG指定一条寻找707的路径，他当然想把707和ZMiG分隔的越远越好，所以他会规划一条距离最长的路线。707自然也知道这一点，但是她没有办法阻止，她唯一能做且必须做的就是利用手中的炸药炸掉大陆上的一个点，然后与这条大陆相连的边也会自动被抹去，这样就会打乱neither_nor本来的计划。但是由于707过于敏捷，他的行动必须在neither_nor之前。换句话说，707需要先选择他炸掉哪个点，之后neither_nor一定会选择一条图中存在的最长路径来分开ZMiG和707。
707想让这条路径最短，所以她要问问你他应该炸掉哪个点。
数据范围
对于20%的数据，N<=20,M<=40
对于40%的数据，N<=1000,M<=2000
对于100%的数据，N<=75000,M<=100000
解法
考虑统计删掉每一个点之后的最长路。
新建一个超级源st和一个超级汇en，那么就转化成为一个连通图。
预处理出每个点到超级源的最长路f[i]，到超级汇的最长路g[i]，设h[i]=f[i]+g[i]。
对于一个点i，计算删掉它的贡献来自于：
1.i的入边的另一端j，贡献f[j]；
2.i的出边的另一端j，贡献g[j]；
3.在拓扑序中，与i同层的任意其他点j，贡献h[j]。
删掉i点后，最长路就是上述三者的最大值。
考虑使用数据结构实时维护上述三者。
按照拓扑序，处理点i（姑且称i的出/入边的另一端作出/入点）：
1.从数据结构中删除h[i]；
2.从数据结构中加入i的出点j的g[j]，入点k的f[k]，
由于要保证只取同层的h，如果入点的h尚未删除，那么将入点的h[k]删除；
3.取出数据结构中的最大值作为删掉i后的最长路；
4.删除g[j]以及f[k]，重加入h[i]。
代码
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define ll long long
#define F(x) (x)
#define G(x) ((x)+n)
#define H(x) ((x)+n+n)
using namespace std;
const char* fin="chronosphere.in";
const char* fout="chronosphere.out";
const int inf=0x7fffffff;
const int maxn=600007,maxm=600007;
int n,m,i,j,k,st,en,ans1,ans=inf;
bool bz[maxn],az[maxn];
int b[maxn],head,tail;
void add(int v){
if (!bz[v]){
b[++tail]=v;
bz[v]=true;
}
}
struct dui{
int data[maxn],pos[maxn],xpos[maxn],num;
dui(){
num=0;
}
bool cmp(int a,int b){
return a>b;
}
void lift(int a,int b){
swap(data[a],data[b]);
swap(xpos[pos[a]],xpos[pos[b]]);
swap(pos[a],pos[b]);
}
void up(int v){
while (v>1 && cmp(data[v],data[v/2])){
lift(v,v/2);
v/=2;
}
}
void down(int v){
int k;
while (v*2<=num && cmp(data[v*2],data[v]) || v*2+1<=num && cmp(data[v*2+1],data[v])){
if (v*2+1>num || cmp(data[v*2],data[v*2+1])) k=v*2;
else k=v*2+1;
lift(k,v);
v=k;
}
}
void push(int v,int v1){
if (az[v]==true) return ;
data[++num]=v1;
az[v]=true;
xpos[v]=num;
pos[num]=v;
up(num);
}
void pull(int v){
if (!az[v]) return ;
int k=xpos[v];
az[v]=false;
data[k]=0;
down(k);
}
int top(){
return num?data[1]:0;
}
}d;
struct graph{
int dis[maxn],fi[maxn],la[maxm],ne[maxm];
int tot,ru[maxn];
void init(){
memset(fi,0,sizeof(fi));
memset(ru,0,sizeof(ru));
memset(dis,0,sizeof(dis));
memset(la,0,sizeof(la));
memset(ne,0,sizeof(ne));
tot=0;
}
graph(){
init();
}
void add_line(int a,int b){
tot++;
ne[tot]=fi[a];
la[tot]=b;
fi[a]=tot;
ru[b]++;
}
void getdis(int v){
int i,j,k;
head=tail=0;
memset(bz,0,sizeof(bz));
b[++tail]=v;
bz[v]=true;
dis[v]=0;
while (head!=tail){
head++;
if (head>maxn) head-=maxn;
for (k=fi[b[head]];k;k=ne[k]){
if (dis[la[k]]<dis[b[head]]+1){
dis[la[k]]=dis[b[head]]+1;
if (!bz[la[k]]){
bz[la[k]]=true;
tail++;
if (tail>maxn) tail-=maxn;
b[tail]=la[k];
}
}
}
bz[b[head]]=false;
}
}
}g[2];
void topsort(){
int i,j,k;
head=tail=0;
b[++tail]=st;
for (i=1;i<=n;i++) d.push(G(i),g[1].dis[i]-1);
while (head++<tail){
for (k=g[1].fi[b[head]];k;k=g[1].ne[k]) {
d.pull(H(k));
if (g[1].la[k]!=st && g[1].la[k]!=en) d.pull(G(g[1].la[k]));
}
if (b[head]!=st && b[head]!=en){
d.pull(G(b[head]));
if (ans>d.top()){
ans=d.top();
ans1=b[head];
}else if (ans==d.top() && b[head]<ans1) ans1=b[head];
}
for (k=g[0].fi[b[head]];k;k=g[0].ne[k]){
d.push(H(k),g[0].dis[b[head]]+g[1].dis[g[0].la[k]]-1);
g[0].dis[g[0].la[k]]=max(g[0].dis[b[head]]+1,g[0].dis[g[0].la[k]]);
if (!--g[0].ru[g[0].la[k]]) b[++tail]=g[0].la[k];
}
if (b[head]!=st && b[head]!=en) d.push(F(b[head]),g[0].dis[b[head]]-1);
}
}
int main(){
freopen(fin,"r",stdin);
freopen(fout,"w",stdout);
scanf("%d%d",&n,&m);
st=n+1;
en=n+2;
for (i=1;i<=m;i++){
scanf("%d%d",&j,&k);
g[0].add_line(j,k);
g[1].add_line(k,j);
}
for (i=1;i<=n;i++){
if (g[0].fi[i]==0) g[0].add_line(i,en),g[1].add_line(en,i);
if (g[0].ru[i]==0){
g[0].add_line(st,i),g[1].add_line(i,st);
}
}
//g[0].getdis(st);
g[1].getdis(en);
topsort();
printf("%d %d",ans1,ans);
return 0;
}启发
DAG套路
考虑建立超级源和超级汇将原DAG转化为一个连通的DAG。
初步探究分析法与“交集优化”
问题
经常使用演绎法做题，即：
先想使用什么算法，在代入题目中考虑，匹配磨合。
这种做法局限性大，并且很耗时。
渐渐地，通过经验的增加，我会更加偏向于分析法：
譬如遇到一道有关树的题目，我会第一时间想到LCA、树形DP等等有关树的方法，而不会是其他的别的什么东西。
但这仍然具有局限，因为这只是很浅的分析法，某种程度上不异于演绎法：
毕竟树的算法涵括很多，一个一个地演绎尝试显然不优。
演绎过度到分析
通过上述说明，我必须将演绎的范围尽可能缩小，才能尽可能地向分析法靠近。
为了缩小演绎的范围，我必须学会挖掘题目的性质，寻找题目的特殊性。
通过许多题，总结出一些惯用的思路：
1.明白题目所求并将其转化
我认为这一点最为重要。
正譬如这一道题：
题目求的是删掉一个点后最长路径最短，并且要使这个点的编号尽可能小。
从中我觉得能挖掘的东西非常少。
因为这个条件委实有点复杂，不好维护什么。
那好，显然我可以耗费
删掉某个点后最长路径是多少。
我认为这个问题就让人感觉很舒服。
额外地，我找不到更好的花费代价来转化为更舒服的问题。
那好：如果我现在觉得这个问题合适，考虑贡献的来源：
本题的贡献来源如解法所写。
那么我只要处理这些贡献，那么答案就水到渠成。
2.优化算法
目前，我已将演绎的范围缩小为如何维护这些贡献的来源。
显然，如果我暴力处理这些贡献来源，我是用的复杂度是
所以我可以采取的是：
- 演绎一种优化方法
我认为当前范围已经足够小了，所以直接演绎。
好，我现在演绎出一个优化方法：
利用交集关系来优化，
对于拓扑序同层的点的h，显然不需要多次删除或加入。
所以可以利用拓扑序来优化具有相同来源的贡献。
于是就可以将O(mlogn) 的时间复杂度均摊了。 - 继续分析，缩小演绎范围
考虑时间复杂度的主要来源，显然我在处理同层点时；
我会多算很多重复的东西。
于是想到交集优化：
因此与1.殊途同归。
未来
我觉得这种分析和演绎的结合，就是解决任何问题的剑和盾。
种种问题，我必须平衡分析和演绎，才能快速解题。
未来，锻炼这种对问题的看法和观点，多实践，多完善这个理论。
我相信“分析和演绎”可以贯穿所有OI问题甚至生活中的一切。