信仰类型的企业网站,证书兼职网,东莞网络推广培训,房价查询网那个问一下有人可以解释以下这个做法嘛#xff0c;看不太懂QwQ~ Description 有一个n个点n条边的有向图#xff0c;点的编号为从1到n。 给出一个数组p#xff0c;表明有#xff08;p1#xff0c;1#xff09;#xff0c;#xff08;p2#xff0c;2#xff09;#x…那个问一下有人可以解释以下这个做法嘛看不太懂QwQ~ Description 有一个n个点n条边的有向图点的编号为从1到n。 给出一个数组p表明有p11p22…pnn这n条单向边这n条边必定构成弱连通图。 每个点均有一个权值ai满足以下性质 1所有ai均为非负整数 2对于任意边ij有ai≠aj 3对于任意ix0≤xai均有ij满足ajai。 判断这样的图是否存在。“POSSIBLE”/“IMPOSSIBLE” Solution 早上花了三个小时还打挫了心态爆炸 弱连通图若该有向图所有边为双向边时满足该图为连通图则该有向图为弱连通图。 我们容易发现当一个点的出度为0时它的权值也为0。我们可以对每一条边建反向边然后进行拓扑排序每次对新图中入度为0的点求出权值然后删去。 若最后有剩余的点由于原图中每个点的入度均为1则这些点形成一个环取其中任意一个点开始遍历即可。特别地若原图n个点构成环则偶环存在而奇环不存在。 下面讲一下如何求出每个点的权值 拓扑排序 若该点在原图中为叶子节点则权值为0 若不为叶子节点则权值为原图子节点权值中未出现的数的最小值。 环 记录原图中该点不在环上的子节点权值中未出现的数的最小值a与次小值b。若该点权值为a则下一点无限制若该点权值为b则下一点权值必为a。在跑环的时候注意判断相邻两点权值不相等以及子节点权值满足条件23即可。 Code 1 #includecstdio2 #includecstring3 #includealgorithm4 #includequeue5 #includestack6 using namespace std;7 #define next _next8 struct edge{9 int to,next;10 }e[200010],g[200010];11 int n,ehead[200010],ghead[200010];12 int m0,a[200010]{0},out[200010]{0};13 int val[200010];14 bool vis[200010]{false};15 queueintq;16 stackints[200010];17 bool dfs(int u,int w,int cannot){18 for(int iehead[u];~i;ie[i].next)19 if(vis[e[i].to])20 s[val[e[i].to]].push(u);21 int v-1;22 for(int iehead[u];~i;ie[i].next)23 if(!vis[e[i].to]){24 ve[i].to;25 break;26 }27 if(v-1){28 if(w-1){29 for(int i0;;i)30 if(s[i].top()!u){31 val[u]i;32 break;33 }34 }35 else{36 val[u]w;37 for(int i0;iw;i)38 if(s[i].top()!u){39 for(int iehead[u];~i;ie[i].next)40 if(vis[e[i].to])41 s[val[e[i].to]].pop();42 return false;43 }44 }45 bool ret(val[u]!cannots[val[u]].top()!u);46 for(int iehead[u];~i;ie[i].next)47 if(vis[e[i].to])48 s[val[e[i].to]].pop();49 return ret;50 }51 if(w-1){52 int flag-1;53 bool retfalse;54 for(int i0;;i)55 if(s[i].top()!u){56 vis[u]true;57 if(i!cannot)58 ret|dfs(v,flag,val[u]i);59 vis[u]false;60 if(flag-1)61 break;62 flagi;63 }64 for(int iehead[u];~i;ie[i].next)65 if(vis[e[i].to])66 s[val[e[i].to]].pop();67 return ret;68 }69 int flag-1;70 for(int i0;iw;i)71 if(s[i].top()!u){72 if(flag-1){73 for(int iehead[u];~i;ie[i].next)74 if(vis[e[i].to])75 s[val[e[i].to]].pop();76 return false;77 }78 flagi;79 }80 bool ret(w!cannots[w].top()!udfs(v,flag,val[u]w));81 for(int iehead[u];~i;ie[i].next)82 if(vis[e[i].to])83 s[val[e[i].to]].pop();84 return ret;85 }86 int main(){87 memset(ehead,-1,sizeof(ehead));88 memset(ghead,-1,sizeof(ghead));89 memset(val,-1,sizeof(val));90 while(!q.empty())q.pop();91 scanf(%d,n);92 for(int i0;in;i){93 while(!s[i].empty())94 s[i].pop();95 s[i].push(0x3f3f3f3f);96 }97 for(int i1,x;in;i){98 scanf(%d,x);99 e[i](edge){i,ehead[x]};
100 g[i](edge){x,ghead[i]};
101 ehead[x]ghead[i]i;
102 a[x];out[x];
103 }
104 for(int i1;in;i)
105 if(out[i]0){
106 vis[i]true;
107 q.push(i);
108 }
109 while(!q.empty()){
110 int uq.front();
111 q.pop();m;
112 for(int iehead[u];~i;ie[i].next)
113 s[val[e[i].to]].push(u);
114 for(int i0;;i)
115 if(s[i].top()!u){
116 val[u]i;
117 break;
118 }
119 for(int iehead[u];~i;ie[i].next)
120 s[val[e[i].to]].pop();
121 for(int ighead[u];~i;ig[i].next)
122 out[g[i].to]--;
123 for(int ighead[u];~i;ig[i].next)
124 if(out[g[i].to]0){
125 vis[g[i].to]true;
126 q.push(g[i].to);
127 }
128 }
129 if(mn){
130 puts(POSSIBLE);
131 return 0;
132 }
133 if(m0){
134 puts(n1?IMPOSSIBLE:POSSIBLE);
135 return 0;
136 }
137 for(int i1;in;i)
138 if(!vis[i]){
139 puts(dfs(i,-1,-1)?POSSIBLE:IMPOSSIBLE);
140 return 0;
141 }
142 return 0;
143 } 话说环套树的题是真的烦[○Д´ ○]转载于:https://www.cnblogs.com/gzez181027/p/agc004f.html
