【EOJ Monthly 2019.02 - E】中位数（二分 ，中位数 ，−1/1变换，dp求解DAG最长路）

题干：

E. 中位数

单测试点时限: 10.0 秒

内存限制: 256 MB

“你的地图是一张白纸，所以即使想决定目的地，也不知道路在哪里。”

QQ 小方最近在自学图论。他突然想出了一个有趣的问题：

一张由 n 个点，m 条边构成的有向无环图。每个点有点权 Ai 。QQ 小方想知道所有起点为 1 ，终点为 n 的路径中最大的中位数是多少。

一条路径的中位数指的是：一条路径有 n 个点，将这 n 个点的权值从小到大排序后，排在位置 ⌊n2⌋+1 上的权值。

输入

第 1 行输入两个正整数 n,m (1≤n≤106,1≤m≤106 )，表示结点数量和边的数量。

第 2 行输入 n 个由空格隔开的整数 Ai (0≤Ai≤109 )，表示点权。

接下来 m 行，每行输入两个整数 x,y (1≤x,y≤n )，表示有一条 x 指向 y 的单向边，保证给出的图是联通的，可能存在重边。

输出

输出一行包含一个整数，表示最大的中位数。如果不存在任何一条起点为 1 ，终点为 n 的路径，则输出 −1 。

样例

Input

5 5 1 2 3 4 5 1 2 2 3 3 5 2 4 4 5

Output

4

解题报告：

考虑二分答案，我们需要验证路径最大的中位数是否 ≥mid 。

我们把所有的点权做 −1/1 变换，即 ≥mid 的点权变为 1 ，否则变为 −1 。

根据题面路径中位数的定义，我们可以发现，如果这条路径的中位数 ≥mid ，那么做了 −1/1 变换以后这条路径上的点权和 ≥0 。

而我们现在需要知道的问题是路径最大的中位数是否 ≥mid ，也就是说，最大的路径点权是否 ≥0 。

跑一遍最长路就好了。而对于 DAG ，最长路只要 dp 一下，复杂度是保证 O(m) 。

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e6 + 5; ll val[MAX],b[MAX],a[MAX]; int head[MAX]; ll dis[MAX]; int tot,flag; bool vis[MAX]; int n,m; struct Node {int to;int ne; } e[MAX]; void add(int u,int v) {e[++tot].ne = head[u];e[tot].to = v;head[u] = tot; } void dfs(int cur,int rt) {if(vis[cur]) return ;vis[cur] = 1;if(cur == n) {flag = 1;dis[n] = val[n];return ;}dis[cur] = -0x3f3f3f3f;for(int i = head[cur]; i!=-1; i=e[i].ne) {int v = e[i].to;if(v == rt) continue;dfs(v,cur);dis[cur] = max(dis[cur],dis[v]);}dis[cur] += val[cur]; } bool ok(ll x) {for(int i = 1; i<=n; i++) {if(a[i] >= x) val[i] = 1;else val[i] = -1;}memset(vis,0,sizeof vis);dfs(1,-1);return dis[1] >= 0; } int main() {cin>>n>>m;memset(head,-1,sizeof head);for(int i = 1; i<=n; i++) scanf("%lld",val + i),a[i] = b[i] = val[i];//注意本题中点权为正 for(int u,v,i = 1; i<=m; i++) {scanf("%d%d",&u,&v);add(u,v);}memset(vis,0,sizeof vis);dfs(1,-1);if(flag == 0) {puts("-1");return 0 ;}sort(b+1,b+n+1);int x = unique(b+1,b+n+1) - b - 1;ll l = 1,r = x,mid,ans;while(l<=r) {mid = (l+r)>>1;if(ok(b[mid])) {ans = mid;l = mid+1;}else r = mid-1;}printf("%lld\n",b[ans]);return 0 ;}

为啥这样就超时。。：（有没有大佬来解释一下这样记忆化为啥不对啊，，欢迎留言区讨论）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e6 + 5; ll val[MAX],b[MAX],a[MAX]; int head[MAX]; ll dis[MAX]; int tot,flag; int n,m; struct Node {int to;int ne; } e[MAX]; void add(int u,int v) {e[++tot].ne = head[u];e[tot].to = v;head[u] = tot; } ll dfs(int cur,int rt) {if(dis[cur] != -0x3f3f3f3f) return dis[cur];if(cur == n) {flag = 1;dis[n] = val[n];return dis[n];}for(int i = head[cur]; i!=-1; i=e[i].ne) {int v = e[i].to;if(v == rt) continue;ll tmp = dfs(v,cur);dis[cur] = max(dis[cur],tmp);}dis[cur] += val[cur];return dis[cur]; } bool ok(ll x) {for(int i = 1; i<=n; i++) {if(a[i] >= x) val[i] = 1;else val[i] = -1;}for(int i = 1; i<=n; i++) dis[i] = -0x3f3f3f3f;dfs(1,-1);return dis[1] >= 0; } int main() {cin>>n>>m;memset(head,-1,sizeof head);for(int i = 1; i<=n; i++) scanf("%lld",val + i),a[i] = b[i] = val[i];//注意本题中点权为正 for(int u,v,i = 1; i<=m; i++) {scanf("%d%d",&u,&v);add(u,v);}for(int i = 1; i<=n; i++) dis[i] = -0x3f3f3f3f;dfs(1,-1);if(flag == 0) {puts("-1");return 0 ;}sort(b+1,b+n+1);int x = unique(b+1,b+n+1) - b - 1;ll l = 1,r = x,mid,ans;while(l<=r) {mid = (l+r)>>1;if(ok(b[mid])) {ans = mid;l = mid+1;}else r = mid-1;}printf("%lld\n",b[ans]);return 0 ;}

补充：如果要求：排在位置上的数。

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e6 + 5; ll val[MAX],b[MAX],a[MAX]; int head[MAX]; ll dis[MAX]; int tot,flag; bool vis[MAX]; int n,m; struct Node {int to;int ne; } e[MAX]; void add(int u,int v) {e[++tot].ne = head[u];e[tot].to = v;head[u] = tot; } void dfs(int cur,int rt) {if(vis[cur]) return ;vis[cur] = 1;if(cur == n) {flag = 1;dis[n] = val[n];return ;}dis[cur] = -0x3f3f3f3f;for(int i = head[cur]; i!=-1; i=e[i].ne) {int v = e[i].to;if(v == rt) continue;dfs(v,cur);dis[cur] = max(dis[cur],dis[v]);}dis[cur] += val[cur]; } bool ok(ll x) {for(int i = 1; i<=n; i++) {if(a[i] > x) val[i] = 1;else val[i] = -1;}memset(vis,0,sizeof vis);dfs(1,-1);return dis[1] <= 0; } int main() {cin>>n>>m;memset(head,-1,sizeof head);for(int i = 1; i<=n; i++) scanf("%lld",val + i),a[i] = b[i] = val[i];//注意本题中点权为正 for(int u,v,i = 1; i<=m; i++) {scanf("%d%d",&u,&v);add(u,v);}memset(vis,0,sizeof vis);dfs(1,-1);if(flag == 0) {puts("-1");return 0 ;}sort(b+1,b+n+1);int x = unique(b+1,b+n+1) - b - 1;ll l = 1,r = x,mid,ans;while(l<=r) {mid = (l+r)>>1;if(ok(b[mid])) {ans = mid;r = mid-1;}else l = mid+1;}printf("%lld\n",b[ans]);return 0 ;}/* 4 3 1 2 3 4 1 2 2 3 3 4*/

另一种求DAG最长路的方法： 

#pragma GCC optimize(3,"Ofast","inline") #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAX=1000006; int n,m,v[MAX],d[MAX],g[MAX],p[MAX],t[MAX],vis[MAX]; vector<int>G[MAX]; inline int check(int x) {for(int i=1; i<=n; ++i)p[i]=v[i]>=x?1:-1,t[i]=-1e9,g[i]=d[i];t[1]=p[1];queue<int>q;q.push(1);for(int u; !q.empty(); q.pop())for(auto v:G[u=q.front()]) {if(t[v]<t[u]+p[v]) t[v]=t[u]+p[v];if(!--g[v]) q.push(v);}return t[n]>=0; } int main() {cin>>n>>m;for(int i=1; i<=n; ++i)scanf("%d",v+i);if(n==1)return 0*printf("%d\n",v[1]);for(int i=1,x,y; i<=m; ++i) {scanf("%d%d",&x,&y);G[x].push_back(y),++d[y];}queue<int>q;q.push(1),vis[1]=1;for(int u; !q.empty(); q.pop())for(auto v:G[u=q.front()])if(!vis[v]) vis[v]=1,q.push(v);for(int i=1; i<=n; ++i)if(!vis[i])for(auto v:G[i]) d[v]--;int l=0,r=1e9,mid,ans=-1;while(l<=r) {mid=(l+r)>>1;if(check(mid))ans=mid,l=mid+1;elser=mid-1;}printf("%d\n",ans); }

 

总结

以上是生活随笔为你收集整理的【EOJ Monthly 2019.02 - E】中位数（二分 ，中位数 ，−1/1变换，dp求解DAG最长路）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。