1. CF1163F. Indecisive Taxi Fee
2. P2619 [国家集训队] Tree I
wqs 二分。
3. P5633 最小度限制生成树
4. P4180 [BJWC2010] 严格次小生成树
典。先随便求一颗最小生成树，一颗严格次小生成树一定是在它的基础上替换了一条边，因为多替换几次要么没影响等于没替换，要么会使得权值大于只替换一条的。枚举加上去的非树边，它与原树形成一个环，找这个环上除了它之外最大的且边权不同的边即可。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int fa[100005];
int find(int x){
return ((x==fa[x])?x:fa[x]=find(fa[x]));
}
struct Node{
int u,v,w;
bool operator <(const Node &b)const{
return w<b.w;
}
}E[300005];
struct edge{
int v,w,nxt;
}e[200005];
int tot,head[100005];
void add(int u,int v,int w){
e[++tot]=(edge){v,w,head[u]},head[u]=tot;
}
struct Info{
int x,y;
Info():x(-inf),y(-inf){};
Info(int _x,int _y):x(_x),y(_y){};
Info operator +(const Info &b)const{
if(x!=b.x)return (Info){max(x,b.x),max(max(y,b.y),min(x,b.x))};
if(y!=b.y)return (Info){x,max(y,b.y)};
return (Info){x,y};
}
}f[22][100005];
int dep[100005],val[100005],pa[22][100005],used[300005];
void dfs(int u,int fa){
dep[u]=dep[fa]+1,pa[0][u]=fa,f[0][u]=(Info){val[u],-inf};
for(int i=1;i<=20;i++)pa[i][u]=pa[i-1][pa[i-1][u]];
for(int i=1;i<=20;i++)f[i][u]=f[i-1][u]+f[i-1][pa[i-1][u]];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;if(v==fa)continue;
val[v]=w;dfs(v,u);
}
}
Info ask(int u,int v){
if(dep[u]>dep[v])swap(u,v);
Info ans=(Info){-inf,-inf};
for(int i=20;i>=0;i--){
if(dep[v]-dep[u]>=(1ll<<i))ans=ans+f[i][v],v=pa[i][v];
}
if(u==v)return ans;
for(int i=20;i>=0;i--){
if(pa[i][u]!=pa[i][v])ans=ans+f[i][u],ans=ans+f[i][v],u=pa[i][u],v=pa[i][v];
}
ans=ans+f[0][u],ans=ans+f[0][v];
return ans;
}
signed main(){
int n=read(),m=read();
for(int i=1,u,v,w;i<=m;i++){
u=read(),v=read(),w=read();
E[i]=(Node){u,v,w};
}
sort(E+1,E+m+1);
for(int i=1;i<=n;i++)fa[i]=i;
int cnt=0,sum=0;
for(int i=1;i<=m;i++){
int u=E[i].u,v=E[i].v,w=E[i].w;
int fu=find(u),fv=find(v);
if(fu==fv)continue;
fa[fu]=fv,sum+=w,used[i]=1;
add(u,v,w),add(v,u,w);
if((++cnt)==n-1)break;
}
val[1]=-inf;dfs(1,0);
int ans=inf;
for(int i=1;i<=m;i++){
if(used[i])continue;
int u=E[i].u,v=E[i].v,w=E[i].w;
Info tmp=ask(u,v);
if(tmp.x==-inf)continue;
if(tmp.x!=w)ans=min(ans,sum-tmp.x+w);
else if(tmp.y!=-inf)ans=min(ans,sum-tmp.y+w);
}
printf("%lld\n",ans);
return 0;
}
5. CF152E. Garden
比较板的斯坦纳树。
问题就是有 \(k\) 个关键点，需要通过一些点把这些关键点连起来，选一个点需要代价，求最小代价。显然最后图一定会连成一棵树，令 \(f_{i,j,S}\) 表示 \((i,j)\) 为所在连通块的根，连通块内包含 \(S\) 点集内的关键点的最小代价。转移分两种：
-
\((i,j)\) 只选了一个儿子。即 \(f_{i,j,S}\gets f_{x,y,S}+a_{i,j}\)。
-
\((i,j)\) 选了多个儿子。即 \(f_{i,j,S+T}\gets f_{i,j,S}+f_{i,j,T}-a_{i,j}(S\cap T=\varnothing)\)。
解释一下。虽然第一种转移似乎没有考虑 \((i,j)\) 是关键点，且 \(S\) 不包含 \((i,j)\) 的情况。但第二种转移是可以得到一个对的最小值的，且第一种转移也没有使答案错误的变小，所以这样还是没问题的。
第二种转移是简单的，只需要枚举子集。发现第一种转移会有环，无法确定转移顺序。但第一种转移不会改变点集，只需要从小到大枚举 \(S\)，跑 dij/spfa 即可。复杂度 \(\mathcal{O}(3^knm+2^knm\log nm)\) 或 \(\mathcal{O}(3^knm+2^kn^2m^2)\)，似乎在一般图上 spfa 会有更小的常数。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define mk make_pair
#define fi first
#define se second
using namespace std;
typedef pair<int,int>pii;
const int inf=1e18;
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,m,k,vis[205],f[205][155],a[105][105];pii p[205][155];
int id(int x,int y){
return (x-1)*m+y;
}
int getx(int v){
return (v-1+m)/m;
}
int gety(int v){
return v-((v-1)/m)*m;
}
int in(int x,int y){
return (x>=1&&x<=n&&y>=1&&y<=m);
}
void spfa(int msk){
queue<pii>q;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
vis[id(i,j)]=1,q.push(mk(i,j));
}
}
while(!q.empty()){
int x=q.front().fi,y=q.front().se;q.pop();vis[id(x,y)]=0;
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(!in(nx,ny))continue;
if(f[id(nx,ny)][msk]>f[id(x,y)][msk]+a[nx][ny]){
f[id(nx,ny)][msk]=f[id(x,y)][msk]+a[nx][ny];
p[id(nx,ny)][msk]=mk(2,id(x,y));
if(!vis[id(nx,ny)])q.push(mk(nx,ny)),vis[id(nx,ny)]=1;
}
}
}
}
int res[105][105];
void solve(int i,int msk){
int I=p[i][msk].fi,MSK=p[i][msk].se;
if(I==-1){
if(msk!=-1)res[getx(i)][gety(i)]=1;
return;
}
if(I==1)solve(i,MSK),solve(i,msk-MSK);
else res[getx(i)][gety(i)]=1,solve(MSK,msk);
}
signed main(){
n=read(),m=read(),k=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[i][j]=read();
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int t=0;t<(1ll<<k);t++){
f[id(i,j)][t]=inf,p[id(i,j)][t]=mk(-1,-1);
}
}
}
for(int i=0,x,y;i<k;i++){
x=read(),y=read();f[id(x,y)][1ll<<i]=a[x][y],p[id(x,y)][1ll<<i]=mk(-1,0);
}
for(int msk=1;msk<(1ll<<k);msk++){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int t=(msk-1)&msk;t;t=(t-1)&msk){
if(f[id(i,j)][t]+f[id(i,j)][msk-t]-a[i][j]<f[id(i,j)][msk]){
f[id(i,j)][msk]=f[id(i,j)][t]+f[id(i,j)][msk-t]-a[i][j];
p[id(i,j)][msk]=mk(1,t);
}
}
}
}
spfa(msk);
}
int ans=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(f[ans][(1ll<<k)-1]>f[id(i,j)][(1ll<<k)-1])ans=id(i,j);
}
}
printf("%lld\n",f[ans][(1ll<<k)-1]);
solve(ans,(1ll<<k)-1);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(res[i][j])putchar('X');
else putchar('.');
}
puts("");
}
return 0;
}