POI20143832: [Poi2014]Rally

本文主要是介绍POI20143832: [Poi2014]Rally，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意给你一个有向无环图让你最小化去掉一个点之后图中的最长链。

一道toposort神题
以下要点：
1、遇到这种不知何时开始何时终止的可以加一个源一个汇
2、这题还利用了割的思想。很多这样删东西的题目都是可以用类似的思想做。
题解：
建图：建立源0汇n+1，源向所有点连边，所有点向汇连边。
首先正反toposort一遍，求出超级源点到每个点的最长链F[i]，以及每个点到汇点的最长链G[i]。
定义一条边的权值为经过这条链的最长链长度即F[from]+ G[to]
图中的最长链为图中任意一个割的的边的权值最大值，证明：所有链都经过这个割。
那么删除一个点x之后的最长链就是从topo序0..x-1的点至x+1..n + 1这些边的最大值，显然删掉之后的割就是他们。用一个堆维护。这样就是O((n+m)log(n+m))了。

代码 ：

//卡常毒瘤 
%:pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;const int N = 1000005;
const int M = N * 3 + 5;struct heap{priority_queue<int>Del,Ins;void clear(void) {while(!Del.empty()) Del.pop();while(!Ins.empty()) Ins.pop();Ins.push(0);}void move(void) {while(Del.top() == Ins.top()) {Del.pop();Ins.pop();if(Del.size() == 0)  break;}}void del(int x) {Del.push(x);move();}void insert(int x) {Ins.push(x);}int Max(void) {return Ins.top();}
} Heap;queue<int>q , Q;
int rd[N] , fir[M] , ne[M] , to[M] , cnt , F[N] , G[N] , cd[N] , n , m;vector<int>fan[N];void add(int x ,int y) {cd[x] ++;rd[y] ++;to[++ cnt] = y;ne[cnt] = fir[x];fir[x] = cnt;fan[y].push_back(x);
}#define Foreachson(i,x) for(int i = fir[x]; i ; i = ne[i])void topo1(void) {memset(F , 0, sizeof(F));q.push(0);Q.push(0);F[0] = 0;while(!q.empty()) {int ind = q.front(); q.pop();Foreachson(i,ind) {int V = to[i];rd[V] --;if(rd[V] == 0) {q.push(V);Q.push(V);F[V] = F[ind] + 1;
//              cerr<<V<<" "<<ind<<endl;}}}
}void topo2(void) {memset(G , 0 , sizeof(G));q.push(n + 1);G[n + 1] = 0;while(!q.empty()) {int ind = q.front(); q.pop();for(int i = 0;i < fan[ind].size();i ++) {int V = fan[ind][i];cd[V] --;if(cd[V] == 0) {q.push(V);G[V] = G[ind] + 1;}}} 
}vector<int>val[N];int main() {scanf("%d%d",&n,&m);for(int i = 1 , x, y;i <= m;i ++) {scanf("%d%d",&x,&y);add(x,y);}for(int i = 1;i <= n;i ++) {add(0 , i);add(i , n + 1);}topo1(); topo2();Heap.clear();int no = -1 , now = 2e9;while(!Q.empty()) {int ind = Q.front(); Q.pop();for(int i = 0;i <(int) fan[ind].size();i ++) {int V = fan[ind][i];Heap.del(F[V] + G[ind] - 1);}if(ind != 0 && ind != n + 1) {if(Heap.Max() < now) {now = Heap.Max();no = ind;}}Foreachson(i,ind) {int V = to[i];Heap.insert(F[ind] + G[V] - 1);}}printf("%d %d",no,now);
}

这篇关于POI20143832: [Poi2014]Rally的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---