商丘家居网站建设,网页设计与网站建设+pdf,公司内部网站建设奖励办法,女生网站开发被支配树支配的恐惧 定义 显然#xff0c;这个支配关系是一个树#xff08;或者如果有的点不能从r到达#xff0c;就是一个树一堆点#xff09;。 首先不会成环#xff0c;其次也不会是DAG 即如果A支配C#xff0c;B支配C#xff0c;那么A和B之间必然有支配关系 解法 首…被支配树支配的恐惧 定义 显然这个支配关系是一个树或者如果有的点不能从r到达就是一个树一堆点。 首先不会成环其次也不会是DAG 即如果A支配CB支配C那么A和B之间必然有支配关系 解法 首先是DAG很好做 [ZJOI2012]灾难 一般有向图有环的存在不能topo 方法分三步 转化为找半支配点 idom[x]表示x的支配点编号 sdom[x]表示x的半支配点编号 先找到原图一个生成树找到每个点的dfn序 定义半支配关系为 定义半支配点为 即满足支配关系dfn最小的点 一些认识 A对于dfs树 B对于支配和半支配 半支配点也一定是x在dfs树上的祖先 请大量运用反证法和dfs算法的深度优先性质进行证明 虽然sdom[x]可能不是idom[x] 但是可以断言 证明 实在不懂可以画图感性理解 所以如果知道sdom[x],现在已经可以专化为求DAG的支配树了 如何找半支配点 这个做法就是前面两个认识的两种情况。 dfn[z]dfn[y]启发我们倒序处理 这样x在T的祖先z一定都是之前加入的一定比y的dfn大直接取即可。 实现维护T 改进同时找支配点 fix每个点从一个祖先连过来恰好一条边 证明略 直接看算法流程吧 从简化之后的G角度进行考虑基本上就是一个树形结构了就很好理解了。 补充 第5步之所以找fa[y]因为先有第4步使得当前的根是fa[y]4/5两步交换就可以直接处理sdom[x]y的点x了 第6步的标记还原必须dfs序正序处理。打标记如果没有idom[x]sdom[x]那么进行处理。 开始时候令sdom[x]x可以省去很多麻烦 Code 注意比较函数的书写。argmin与argmax #includebits/stdc.h
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define numb (ch^0)
#define pb push_back
#define solid const auto
#define enter coutendl
#define pii pairint,int
using namespace std;
typedef long long ll;
templateclass Til void rd(T x){char ch;x0;bool flfalse;while(!isdigit(chgetchar()))(ch-)(fltrue);for(xnumb;isdigit(chgetchar());xx*10numb);(fltrue)(x-x);
}
templateclass Til void output(T x){if(x/10)output(x/10);putchar(x%100);}
templateclass Til void ot(T x){if(x0) putchar(-),x-x;output(x);putchar( );}
templateclass Til void prt(T a[],int st,int nd){for(reg ist;ind;i) ot(a[i]);putchar(\n);}namespace Miracle{
const int N2e55;
const int M3e55;
int n,m;
struct node{int nxt,to;
}e[M];
int hd[N],cnt;
void add(int x,int y){e[cnt].nxthd[x];e[cnt].toy;hd[x]cnt;
}
vectorintmem[N],fr[N];
int fa[N],dfn[N],fdfn[N],idom[N],sdom[N],df;
int gf[N],val[N];
bool cmp(int x,int y){//xy?return dfn[sdom[x]]dfn[sdom[y]];
}
int chm(int x,int y){return dfn[x]dfn[y]?x:y;
}
int fin(int x){if(gf[x]x) return x;int rtfin(gf[x]);val[x]cmp(val[x],val[gf[x]])?val[x]:val[gf[x]];return gf[x]rt;
}
void dfs(int x){dfn[x]df;fdfn[df]x;for(reg ihd[x];i;ie[i].nxt){int ye[i].to;if(dfn[y]) continue;fa[y]x;dfs(y);}
}
void wrk(){for(reg in;i2;--i){int xfdfn[i];for(reg j0;j(int)fr[x].size();j){int yfr[x][j];if(dfn[y]dfn[x]){sdom[x]chm(y,sdom[x]);}else{int hahafin(y);sdom[x]chm(sdom[val[y]],sdom[x]);}}mem[sdom[x]].push_back(x);gf[x]fa[x];xfa[x];for(reg j0;j(int)mem[x].size();j){int ymem[x][j];int hahafin(y);if(sdom[val[y]]sdom[y]) idom[y]sdom[y];else idom[y]val[y];}}for(reg i2;in;i){int xfdfn[i];if(idom[x]!sdom[x]) idom[x]idom[idom[x]];}
}
int sz[N];
void sol(int x){sz[x]1;for(reg ihd[x];i;ie[i].nxt){int ye[i].to;sol(y);sz[x]sz[y];}
}
int main(){rd(n);rd(m);int x,y;for(reg i1;im;i){rd(x);rd(y);add(x,y);fr[y].push_back(x);}dfs(1); for(reg i1;in;i){sdom[i]i,val[i]i,gf[i]i;}wrk();memset(hd,0,sizeof hd);cnt0;for(reg i2;in;i){add(idom[i],i);}// prt(dfn,1,n);// prt(fa,1,n);// prt(sdom,1,n);// prt(idom,1,n);sol(1);prt(sz,1,n);return 0;
}}
signed main(){Miracle::main();return 0;
}/*Author: *Miracle*
*/ 例题 其实就是[ZJOI2012]灾难 别的没什么题目。。。。转载于:https://www.cnblogs.com/Miracevin/p/10819686.html
