良精企业网站管理系统,电脑游戏排行榜前十名,建立健全,请教 网站建设价格一般多少钱正题
题目链接:https://www.luogu.com.cn/problem/P3573 题目大意 nnn个点mmm条边的DAGDAGDAG#xff0c;删掉一个点使得最长路最短。 解题思路
先跑一遍拓扑排序 dsids_idsi表示以iii结尾的最长路#xff0c;dtidt_idti表示以iii开头的最长路#xff0c;用拓扑序dp可…正题
题目链接:https://www.luogu.com.cn/problem/P3573 题目大意
nnn个点mmm条边的DAGDAGDAG删掉一个点使得最长路最短。 解题思路
先跑一遍拓扑排序 dsids_idsi表示以iii结尾的最长路dtidt_idti表示以iii开头的最长路用拓扑序dp可以搞定
定义两个点集SSS和TTT我们先将所有所有点放入TTT集合并且把dtdtdt放入一个数据结构里。
然后按照拓扑序枚举从小到大删除哪个点枚举到的点xxx我们把dtxdt_xdtx从数据结构里删除对于y−xy-xy−x我们可以把dsydtx1ds_ydt_x1dsydtx1从数据结构里删除。
然后查询最小值统计答案
之后把dsxds_xdsx和对于x−yx-yx−y我们有dsxdty1ds_xdt_y1dsxdty1都丢进数据结构里。
这里用树状数组二分统计答案。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includevector
#includequeue
#define lowbit(x) (x-x)
using namespace std;
const int N1e610;
struct node{int to,next;
}a[N];
queueint q;
int n,m,cnt,ans,id;
int in[N],top[N],ds[N],dt[N],ls[N];
vectorint init[N];
struct Tree_Array{int t[N];void Change(int x,int val){if(!x) return;while(xm){t[x]val;xlowbit(x);}return;}int Ask(int x){int ans0;while(x){anst[x];x-lowbit(x);}return ans;}int Maxs(){int zAsk(m);int l0,rm;while(lr){int mid(lr)1;if(Ask(mid)z)rmid-1;else lmid1;}return l;}
}T;
void Top_Sort(){for(int i1;in;i)if(!in[i])q.push(i),top[cnt]i;while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;in[y]--;if(!in[y])q.push(y),top[cnt]y;}}return;
}
void Get_Dis(){for(int i1;in;i){int xtop[i];for(int jls[x];j;ja[j].next){int ya[j].to;ds[y]max(ds[y],ds[x]1);}}for(int in;i1;i--){int xtop[i];for(int j0;jinit[x].size();j){int yinit[x][j];dt[y]max(dt[y],dt[x]1);}}return;
}
void Solve(){ans2147483647;for(int i1;in;i)T.Change(dt[i],1);for(int k1;kn;k){int xtop[k];T.Change(dt[x],-1);for(int i0;iinit[x].size();i){int yinit[x][i];T.Change(ds[y]dt[x]1,-1);}int zT.Maxs();if(zans) ansz,idx;T.Change(ds[x],1);for(int ils[x];i;ia[i].next){int ya[i].to;T.Change(ds[x]dt[y]1,1);}}return;
}
int main()
{scanf(%d%d,n,m);for(int i1;im;i){int x,y;scanf(%d%d,x,y);a[i].toy;a[i].nextls[x];ls[x]i;in[y];init[y].push_back(x);}Top_Sort();Get_Dis();Solve();printf(%d %d,id,ans);
}
