生活随笔
收集整理的這篇文章主要介紹了
基环树小记
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
概念
基環(huán)樹(shù)就是有n個(gè)點(diǎn)n條邊的圖（比樹(shù)多出現(xiàn)一個(gè)環(huán)）。
特殊形態(tài)的基環(huán)樹(shù)
無(wú)向樹(shù)(N點(diǎn)N邊無(wú)向圖)
外向樹(shù)(每個(gè)點(diǎn)只有一條入邊)
內(nèi)向樹(shù)(每個(gè)點(diǎn)只有一條出邊)
以上三種樹(shù)有十分優(yōu)秀的性質(zhì)，就是可以直接將環(huán)作為根。就可以對(duì)每個(gè)環(huán)的子樹(shù)進(jìn)行單獨(dú)處理，最后再處理環(huán)
找環(huán)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std
;
const int N
=5010;
struct Edge{int v
,nxt
;}edge
[N
<<1];
struct Line{int u
,v
;}line
[N
<<1];
int n
,m
,cnt
,head
[N
],dfn
[N
],ind
,fa
[N
],loop
[N
],len
;
bool ban
[N
][N
];
int t
,ans
[N
],rec
[N
];
bool cmp(Line a
,Line b
){return a
.v
>b
.v
;}
void addedge(int u
,int v
){edge
[++cnt
].v
=v
;edge
[cnt
].nxt
=head
[u
];head
[u
]=cnt
;
}
void getloop(int u
){dfn
[u
]=++ind
;for(int i
=head
[u
];i
;i
=edge
[i
].nxt
){int v
=edge
[i
].v
;if(v
==fa
[u
]) continue;if(dfn
[v
]){if(dfn
[v
]<dfn
[u
]) continue;for(int x
=v
;x
!=fa
[u
];x
=fa
[x
]) loop
[++len
]=x
;}else{fa
[v
]=u
;getloop(v
);}}
}
void dfs(int u
,int f
){rec
[++t
]=u
;for(int i
=head
[u
];i
;i
=edge
[i
].nxt
){int v
=edge
[i
].v
;if(v
==f
) continue;if(ban
[u
][v
]) continue;dfs(v
,u
);}
}
void getmin(){bool flag
=0;int i
;for(i
=1;i
<=n
;i
++){if(rec
[i
]<ans
[i
]){flag
=1;break;}else if(rec
[i
]>ans
[i
]) return;}if(!flag
) return;for(;i
<=n
;i
++) ans
[i
]=rec
[i
];
}
int main(){memset(ans
,0x7f,sizeof(ans
));scanf("%d%d",&n
,&m
);for(int i
=1;i
<=m
;i
++){int u
,v
;scanf("%d%d",&u
,&v
);line
[i
]=(Line
){u
,v
};line
[i
+m
]=(Line
){v
,u
};}sort(line
+1,line
+2*m
+1,cmp
);for(int i
=1;i
<=2*m
;i
++) addedge(line
[i
].u
,line
[i
].v
);if(m
==n
-1){dfs(1,0);for(int i
=1;i
<=n
;i
++) printf("%d ",rec
[i
]);return 0;}getloop(1);loop
[++len
]=loop
[1];for(int i
=1;i
<len
;i
++){ban
[loop
[i
]][loop
[i
+1]]=ban
[loop
[i
+1]][loop
[i
]]=1;t
=0;dfs(1,0);getmin();ban
[loop
[i
]][loop
[i
+1]]=ban
[loop
[i
+1]][loop
[i
]]=0;}for(int i
=1;i
<=n
;i
++) printf("%d ",ans
[i
]);return 0;
}
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 1000010
#define int long long
using namespace std
;
struct Edge{int v
,nxt
;}edge
[N
];
int w
[N
],n
,ans
,cnt
,f
[N
][2],head
[N
],d
[N
],mark
;
bool vis
[N
];
void add(int u
,int v
){edge
[++cnt
].v
=v
;edge
[cnt
].nxt
=head
[u
];head
[u
]=cnt
;
}
void getloop(int u
){vis
[u
]=true;if(vis
[d
[u
]]) mark
=u
;else getloop(d
[u
]);return;
}
void dp(int u
){vis
[u
]=true;f
[u
][1]=w
[u
];f
[u
][0]=0;for(int i
=head
[u
];i
;i
=edge
[i
].nxt
){int v
=edge
[i
].v
;if(v
!=mark
){dp(v
);f
[u
][0]+=max(f
[v
][1],f
[v
][0]);f
[u
][1]+=f
[v
][0];}else f
[v
][1]=-2147483647/3;}return;
}
signed main(){scanf("%d",&n
);for(int i
=1;i
<=n
;i
++){scanf("%d%d",&w
[i
],&d
[i
]);add(d
[i
],i
);}for(int i
=1;i
<=n
;i
++){if(vis
[i
]) continue;getloop(i
);dp(mark
);int maxn
=max(f
[mark
][0],f
[mark
][1]);mark
=d
[mark
];dp(mark
);ans
+=max(maxn
,max(f
[mark
][0],f
[mark
][1]));}printf("%lld",ans
);
}
一般問(wèn)題解決方法
一般解決方法都是如果是樹(shù)形dp，就對(duì)環(huán)部分進(jìn)行環(huán)形dp的操作。不然可以考慮斷環(huán)法。
- 斷環(huán)法
每次斷開(kāi)環(huán)上的一條邊跑一遍答案，然后取最大值。
適用于：數(shù)據(jù)較小，且環(huán)不會(huì)影響答案的題目
[NOIP2018 提高組] 旅行 - 二次dp法
對(duì)于環(huán)，我們可以像環(huán)形dp一樣將一條邊強(qiáng)行斷開(kāi)處理一遍，然后強(qiáng)行連上再處理一遍
適用于：這樣子跑滿足正確性的
[ZJOI2008]騎士 - 斷環(huán)復(fù)制法
對(duì)于環(huán)，我們可以像環(huán)形dp一樣斷開(kāi)環(huán)，然后再?gòu)?fù)制一遍放在后面
適用于：多個(gè)需要維護(hù)的
[IOI2008] Island
總結(jié)
以上是生活随笔為你收集整理的基环树小记的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
