@OceanEye7年前
08/30
16:52
思路清奇的一道题
首先有向图的最长链可以通过添加超级源超级汇，计算超级源超级汇之间的最长路来实现
如果仅仅如此并不足以做这道题
这道题还用了最小割的思想
看大佬题解吧……不是很清楚这题要怎么讲明白
大佬题解的传送门
\(S\) 为超级源
\(T\) 为超级汇
\(g[i] \) 为 \(S\) 到 \(i\) 的最长路
\(f[i] \) 为 \(i\) 到 \(T\) 的最长路
\( edge={ From,To } \)
令一条边存在的贡献为 \( g[From]+f[To]+1 \)
这是这条边对最长路的贡献
我们维护两个点集 \( A,B \) 。一开始 \( A \) 中只有S，其余点都在 \(B\) 中。
我们用数据结构来维护两个集合之间的连边，注意这是一定包括了所有能从S到T的路径的。每次我们按照昂拓扑序从B中拿点到A中，在这个过程中维护边集即可
令被移动的点为 \(x\)
那么我们需要先把从 \(A\) 到 \(x\) 的边全部删除，即删除 \(x\) 的所有入边 【为什么？我们之前用的是拓扑序啊不是吗】
完成统计后再将 \(x\) 到 \(B\) 的边全部加入即可
同时为了保证一个点在被删除后，两端的点依然有贡献，我们要在一开始加入 \(f[x]\)
后面点 \(x\) 从B移动到A后，我们要把 \(f[x]\) 删除，再将 \(g[x]\) 加入边集。
某次删点之后我们选出来的边的贡献值中最大的最小，那么这就是我们要求的答案
值的维护随便挑个数据结构就做了
难点是边的值要怎么去想到
【算了反正我也是看题解的记住这个思路就好了】
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <queue> #include <cstdlib> #include <cmath> #include <vector> #define ll long long #define INF 100000000 #define For(i,a,b) for(int i=a;i<=b;++i) #define Rev(i,a,b) for(int i=a;i>=b;i--) #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; C=1; cc=getchar(); while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } #undef p using namespace std; #define N 3000010 #define M 500005 struct Tedge { int from,to,val; }edge[N]; int fst[2][M],cnt[2][M],nxt[2][N],e_tot,d[2][M]; int que[M],tot; int ans,mx=INF,n,m; void add_e(int a,int b) { static int &i = e_tot; edge[i].from=a; edge[i].to=b; nxt[0][i]=fst[0][a]; fst[0][a]=i; cnt[0][b]++; nxt[1][i]=fst[1][b]; fst[1][b]=i; cnt[1][a]++; i++; } void topo() { #define MOD 500003 int q[500005],he,ta,x; he=ta=0; For(i,1,n) if(!cnt[0][i])q[ta++]=i,d[0][i]=1; while(he!=ta) { x=q[he++]; he==MOD?he=0:he; que[tot++]=x; for(int i=fst[0][x];~i;i=nxt[0][i]) { if(!--cnt[0][edge[i].to]) q[ta++]=edge[i].to; ta==MOD?ta=0:ta; d[0][edge[i].to]=d[0][x]+1; } } //-------------- Rev(i,n-1,0) { d[1][que[i]]=max(1,d[1][que[i]]); for(int j=fst[1][que[i]];~j;j=nxt[1][j]) d[1][edge[j].from]=max(d[1][edge[j].from],d[1][que[i]]+1); } For(i,0,e_tot) edge[i].val=d[0][edge[i].from]+d[1][edge[i].to]; #undef MOD } namespace Heap { priority_queue <int , vector<int> , less<int> > A,Bin; void Push(int val) { A.push(val); } void erase(int val){ Bin.push(val); } int get() { while(!A.empty()&&!Bin.empty()&&Bin.top()==A.top()) Bin.pop(),A.pop(); return A.top(); } } void solve() { Heap::Push(0); For(i,1,n) Heap::Push(d[1][i]); int b; #define now que[j] for(int j=0;j<tot;++j) { for(int i=fst[1][now];~i;i=nxt[1][i]) Heap::erase(edge[i].val); Heap::erase(d[1][now]); b=Heap::get(); if(mx>b) mx=b,ans=now; for(int i=fst[0][now];~i;i=nxt[0][i]) Heap::Push(edge[i].val); Heap::Push(d[0][now]); } #undef now } void init() { memset(fst,-1,sizeof(fst)); int a,b,val; read(n); read(m); For(i,1,m) { read(a); read(b); add_e(a,b); } topo(); } int main() { freopen("1.in","r",stdin); init(); solve(); printf("%d %d",ans,mx-1); return 0; } |