填很久以前的坑。
旅行
给一棵 n 个点的基环树，求字典序最小的DFS序。
n ≤ 5000
题解
O(n2) 做法非常显然，枚举断掉环上哪条边然后贪心即可。当然我去年的骚操作只能得88分。
O(n log n) 做法，推荐duoluoluo的博客。
环上要删的边是固定的，我们在环上走的时候，只有当其出边连向的点中，环上点编号最大，且比回溯到父亲后第一个走的点还大，这时候才回溯，其他时候就正常跑DFS。
#include<bits/stdc++.h>
using namespace std;
template<class T> T read(){
T x=0,w=1;char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-') w=-w;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*w;
}
template<class T> T read(T&x){
return x=read<T>();
}
#define co const
#define il inline
typedef long long LL;
co int N=500000+10;
int n,m;
struct edge {int x,y;}eg[N*2];
il bool operator<(co edge&a,co edge&b){
return a.y<b.y;
}
vector<int> to[N];
namespace T1{
int vis[N],ans[N],num;
void dfs(int x){
vis[x]=1,ans[++num]=x;
for(int i=0;i<(int)to[x].size();++i){
int y=to[x][i];
if(!vis[y]) dfs(y);
}
}
void main(){
dfs(1);
for(int i=1;i<=n;++i) printf("%d ",ans[i]);
}
}
namespace T2{
int circle,f[N],rings[N];
int vis[N],ans[N],num;
int comp,recur;
void dfs_ring(int x,int fa){
if(circle) return;
if(!f[x]) f[x]=fa;
else if(f[x]!=fa){
for(;fa!=x;fa=f[fa]) rings[fa]=1;
rings[x]=1,circle=1;
return;
}
for(int i=0;i<(int)to[x].size();++i){
int y=to[x][i];
if(y==fa) continue;
dfs_ring(y,x);
}
}
void dfs_ans(int x){
vis[x]=1,ans[++num]=x;
if(!rings[x]){
for(int i=0;i<(int)to[x].size();++i){
int y=to[x][i];
if(vis[y]) continue;
dfs_ans(y);
}
return;
}
int found=0;
for(int i=0;i<(int)to[x].size();++i){
if(recur) break;
int y=to[x][i];
if(vis[y]) continue;
if(rings[y]){
int j=i+1;
while(j<(int)to[x].size() and vis[to[x][j]]) ++j;
if(j<(int)to[x].size()) comp=to[x][j];
else if(y>comp) found=1,recur=1;
break;
}
}
for(int i=0;i<(int)to[x].size();++i){
int y=to[x][i];
if(vis[y]) continue;
if(rings[y] and found) continue;
dfs_ans(y);
}
}
void main(){
dfs_ring(1,1);
comp=INT_MAX,dfs_ans(1);
for(int i=1;i<=n;++i) printf("%d ",ans[i]);
}
}
int main(){
read(n),read(m);
for(int i=1;i<=m;++i){
int x=read<int>(),y=read<int>();
eg[2*i-1]=(edge){x,y},eg[2*i]=(edge){y,x};
}
sort(eg+1,eg+2*m+1);
for(int i=1;i<=2*m;++i) to[eg[i].x].push_back(eg[i].y);
if(m==n-1) T1::main();
else T2::main();
return 0;
}
赛道修建
给一棵 n 个点带权无向树，要求找出 m 条不相交的简单路径，使得路径长度最小值最大。
n ≤ 50000
题解
二分答案判可行性。推荐owencodeisking的博客。
对于每个结点，把所有传上来的值 val 放进一个 multiset ，其实这些值对答案有贡献就两种情况：
- val≥k
- vala+valb≥k
那么第一种情况可以不用放进 multiset，直接答案 +1 就好了。第二种情况就可以对于每一个最小的元素，在 multiset 中找到第一个 ≥k的数，将两个数同时删去，最后把剩下最大的值传到那个结点的父亲
我出考场后想为什么这种解法是正确的，有没有可能对于有些情况直接传最大的数会使答案更大？
当然不会。这个数即使很大也只能对答案贡献加 1，在其没传上去的时候可以跟原来结点的值配对，也只能对答案贡献加 1。
时间复杂度 O(n log2 n)。
#include<bits/stdc++.h>
using namespace std;
template<class T> T read(){
T x=0,w=1;char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-') w=-w;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*w;
}
template<class T> T read(T&x){
return x=read<T>();
}
#define co const
#define il inline
typedef long long LL;
co int N=50000+10;
vector<int> to[N],we[N];
int diameter;
int pretreat(int x,int fa){
int maxd=0;
for(int i=0;i<(int)to[x].size();++i){
int y=to[x][i];
if(y==fa) continue;
int len=pretreat(y,x)+we[x][i];
diameter=max(diameter,maxd+len);
maxd=max(maxd,len);
}
return maxd;
}
int ans;
multiset<int> s[N];
typedef multiset<int>::iterator iter;
int dfs(int x,int fa,int k){
s[x].clear();
for(int i=0;i<(int)to[x].size();++i){
int y=to[x][i];
if(y==fa) continue;
int val=dfs(y,x,k)+we[x][i];
if(val>=k) ++ans;
else s[x].insert(val);
}
int len=0;
while(s[x].size()){
if(s[x].size()==1) return max(len,*s[x].begin());
iter i=s[x].lower_bound(k-*s[x].begin());
if(i==s[x].begin() and s[x].count(*i)==1) ++i;
if(i==s[x].end()){
len=max(len,*s[x].begin());
s[x].erase(s[x].begin());
}
else{
++ans;
s[x].erase(s[x].begin()),s[x].erase(s[x].find(*i)); // edit 1: find
}
}
return len;
}
int check(int k){
ans=0;
dfs(1,0,k);
return ans;
}
int main(){
// freopen("testdata.in","r",stdin);
int n=read<int>(),m=read<int>();
for(int i=1;i<n;++i){
int x=read<int>(),y=read<int>(),w=read<int>();
to[x].push_back(y),we[x].push_back(w);
to[y].push_back(x),we[y].push_back(w);
}
pretreat(1,0);
int l=1,r=diameter;
while(l<r){
// cerr<<"l="<<l<<" r="<<r<<endl;
int mid=(l+r+1)>>1;
check(mid)>=m?l=mid:r=mid-1;
}
printf("%d\n",l);
return 0;
}