asp网站连接access数据库工商企业注册网上核名

asp网站连接access数据库,工商企业注册网上核名,青岛网站优化多少钱,计算机基础网页制作教程【题目描述】给出 N 个点#xff0c;M 条边的有向图#xff0c;对于每个点 v#xff0c;求 A(v) 表示从点 v 出发#xff0c;能到达的编号最大的点。【输入】第 1 行 2 个整数 N,M#xff0c;表示点数和边数。接下来 M 行#xff0c;每行 2 个整数 Ui,Vi#xff0c;表示…【题目描述】给出 N 个点M 条边的有向图对于每个点 v求 A(v) 表示从点 v 出发能到达的编号最大的点。【输入】第 1 行 2 个整数 N,M表示点数和边数。接下来 M 行每行 2 个整数 Ui,Vi表示边 (Ui,Vi)。点用 1,2,…,N 编号。【输出】一行 N 个整数 A(1),A(2),…,A(N)。【输入样例】4 3 1 2 2 4 4 3【输出样例】4 4 3 4【提示】对于 60% 的数据1≤N,M≤2000。对于 100% 的数据1≤N,M≤105。1. 问题分析题目要求对于图中的每个点i求出它能到达的所有点中编号最大的那个点。最直观的暴力做法我下面代码中第一个做法是对1--N的每一个点分别进行一次 DFS。时间复杂度O(N*(NM))。结果当 N10^5时计算量达到百亿级必定TLE。痛点正向搜索时为了防止死循环每轮都要清空vis数组导致大量重复访问相同的路径。2. 优化思路正难则反如果我们正向寻找“u能去哪”不知道终点是谁必须走到底。不妨换个角度看“编号最大的点”能反向走到谁。如果在反向图中点Target能走到点 u那么在原图中u一定能走到Target。3. 算法核心策略利用反向建图配合贪心策略只需遍历一次图即可求解。反向建图对于输入的每条边 u - v我们建立反向边 v - u。从大到小枚举贪心我们从编号最大的点N开始倒序遍历到1。DFS当我们在反向图中从点i出发搜索时凡是能被i访问到的点且之前未被访问过它们在原图中能到达的编号最大的点就是i。关键点因为我们要找最大值且外层循环是从大到小进行的。所以一个点第一次被访问时标记它的那个起点i一定是它能接触到的最大编号。剪枝既然第一次访问就是最大值那么后续如果再遇到已访问的点直接跳过无需重复计算。通过这种方式每个点和每条边只会被访问一次时间复杂度降为O(NM)。4. 完整代码/* //这道题正向建图会超时 #include iostream using namespace std; int h[100010];//头指针数组 int vtex[100010];//存放节点 int nxt[100010]; int idx; int cnt;//从自身出发能到达的编号最大的点 int vis[100010]; int n,m; void dfs(int k){ cntmax(cnt,k); if(cntn) return;//当能到达的点为n时就不可能更大了 int ph[k]; while(p!-1){ if(vis[vtex[p]]0){ vis[vtex[p]]1; dfs(vtex[p]); } pnxt[p]; } } void addedge(int x,int y){ vtex[idx]y; nxt[idx]h[x]; h[x]idx; } int main(){ ios::sync_with_stdio(false); cin.tie(0); scanf(%d%d,n,m); //因为点数是10^5量级所以我们选用邻接表形式存图 memset(h,-1,sizeof(h));//初始化h数组 for(int i1;im;i){ int u,v; scanf(%d%d,u,v); addedge(u,v); } //接下来输出 for(int i1;in;i){//挨个点找能到达的编号最大的点 memset(vis,0,sizeof(vis));//每轮要初始化vis数组 cnti;//从点i出发能到达的最大的点初始为自身 vis[i]1;//标记这个点已经走过不再次走 dfs(i);//找从自身出发能到达的最大的点 printf(%d ,cnt); } return 0; } */ //所以这道题我们需要反向建图,反向建图 我们从最大点i去递归然后他能到达的点 //能去到的编号最大的点就是i且如果i-1已经被i经过了那i-1就无需计算了因为 //i能到i-1i就能到i-1所能去的所有点但ii-1,所以肯定以大数为准 #include iostream #include cstring using namespace std; int h[100010];//头指针 int vtex[100010]; int nxt[100010]; int idx; int ma[100010];//存每个点能到达的最大点 void dfs(int k,int x){//现在递归到k点 起始点x最大值 int ph[k]; while(p!-1){ if(ma[vtex[p]]0){//如果这个点前面没有别的数经过那x就是它能到达的最大点 ma[vtex[p]]x; dfs(vtex[p],x); } pnxt[p]; } } void addedge(int x,int y){ vtex[idx]y; nxt[idx]h[x]; h[x]idx; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m; cinnm; memset(h,-1,sizeof(h));//初始化h数组为每个点都没有头指针 //点数为10^5量级所以要用邻接表 for(int i1;im;i){ int u,v; cinuv; addedge(v,u);//反向建图 } //接下来从最大点n开始遍历我们从最大点i去递归然后他能到达的点 //能去到的编号最大的点就是n且如果n-1能被n经过n-1就无需计算了因为 //n能到n-1i就能到n-1所能去的所有点但n大于n-1,所以肯定以大数为准用一个 //数组去存每个点能到的最大值 for(int in;i1;i--){ if(ma[i]0){//如果这个数目前没有被更大数经过就要去递归 dfs(i,i); ma[i]i;//然后它能去到的最大点就是自身 } //否则就是能被更大数经过就不需要去搜索这个数的沿途路径了它能经过的点 //都被更大点赋值了 } //输出 for(int i1;in;i){ coutma[i] ; } return 0; }