本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-11-11 21:31:34
P3958 [NOIP2017 提高组] 奶酪
难度：$\color{orange}\text{普及/提高-}$
$\color{green}\text{AC算法：dfs}$
题目分析：
数据范围较小，可以dfs所有通向下面的点，看看是否可以到达上面即可
解题流程：
一、预处理所有通向上面的洞，使用一个map容器来记录某个洞是不是通向上面的洞。
二、从所有通向下面的点出发dfs，如果最终到达通向上面的洞，则输出Yes，否则输出No，此部分代码：
bool flag = 0;
for (register auto i = 1;i<=n; i++)
{
\/\/ memset(vis, 0, sizeof(vis));
if(ball[i].z<=r){
if(dfs(i)==1){
printf("Yes\n");
flag = 1;
break;
}
}
if (!flag)
{
printf("No\n");
}
}
总体AC代码就是：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int maxn = 1005;
#define int long long
struct Ball
{
int x, y, z;
} ball[maxn];
inline double dis(Ball a,Ball b)
{
register int _1 = a.x - b.x;
register int _2 = a.y - b.y;
register int _3 = a.z - b.z;
return sqrt((_1 * _1) + (_2 * _2) + (_3 * _3));
}
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 << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int t,n,h,r;
bool vis[maxn];
map<int, bool> im;
bool dfs(int x)
{
if(im[x]!=0)
{
return 1;
}
vis[x] = 1;
for (register int i = 1; i <= n;i++)
{
if(i==x)continue;
if(dis(ball[i],ball[x])>(r<<1))
continue;
register int to = i;
if(!vis[to])
{
if(dfs(to)==1)
{
return 1;
}
}
}
return 0;
}
signed main()
{
t = read();
map<int, bool> imt;\/\/是不是与上面相交的洞
while(t--)
{
memset(vis, 0, sizeof(vis));
imt.clear();
n = read(), h = read(), r = read();
for (register int i = 1; i <= n;i++)
{
ball[i].x = read();
ball[i].y = read();
ball[i].z = read();
if(h-ball[i].z<=r)
{
imt[i] = 1;
}
}
im = imt;
bool flag = 0;
for (register auto i = 1;i<=n; i++)
{
\/\/ memset(vis, 0, sizeof(vis));
if(ball[i].z<=r){
if(dfs(i)==1){
printf("Yes\n");
flag = 1;
break;
}}
}
if (!flag)
{
printf("No\n");
}
}
return 0;
}
[NOIP2013 提高组] 货车运输 | P1967
难度：$\color{blue}\text{提高+/省选-}$
$\color{green}\text{AC算法：lca,kruscal}$
题目分析：
可以发现，对于图中一个点到另一个点的最大限重，就是两个点之间最小边权最大的路径，其他的路径都不会走。此处例如样例中的一个例子:
1$\rightarrow$3有两条路径，一个是 1$\rightarrow$2$\rightarrow$3；另一个是1$\rightarrow$3。第一条路径限重3,第二条路径限重1。显然，不会走第二条路径。
如何解决这个问题我先想到了网络流的最大流，但是显然在这个数据范围下AC不了。可以构建一个最大生成树来存储要走的路径，使用kruscal算法即可。
接下来使用lca来查询路径即可(可以理解为将根节点作为中点）。
解体流程：
一、使用前向星存图
二、构建最大生成树
三、处理每个节点的深度，父子信息
四、更新每个节点的祖先、关系
五、lca查询
注意：
预处理 $lca$ 时一定要这样写，不然会出现处理当前节点时祖先未处理的情况：
for(int i=0; i<20; i++)
{
for(int j=1; j<=n; j++)
{
fa[j][i+1]=fa[fa[j][i]][i];
w[j][i+1]=min(w[j][i], w[fa[j][i]][i]);
}
}
AC代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define int long long
const int inf=0xffffffffff;
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<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
const signed maxn=1e4+5;
const signed maxm=5e4+5;
int tot,tot2,n,m,q,f[maxn]\/*骞舵煡闆?*\/,fa[maxn][21*2]\/*lca*\/,dep[maxn];
int w[maxn][21*2];
bool vis[maxn];
int head[maxn];
struct EDGE
{
int u,to,val;
}edge[maxm];
inline void add_edge(int u,int to,int val)
{
edge[++tot].to=to;
edge[tot].val=val;
edge[tot].u=u;
}
struct EDGE2
{
int to,nxt,val;
}edge2[maxm];
inline void add_edge2(int u,int to,int val)
{
edge2[++tot2].to=to;
edge2[tot2].val=val;
edge2[tot2].nxt=head[u];
head[u]=tot2;
}
int find(int x)
{
return x==f[x]?x:f[x]=find(f[x]);
}
bool cmp(EDGE a,EDGE b)
{
return a.val>b.val;
}
inline void kruscal()
{
for(register int i=1;i<=m;i++)
{
if(find(edge[i].u)!=find(edge[i].to))
{
f[find(edge[i].u)]=find(edge[i].to);
\/\/ cout<<"u: "<<edge[i].u<<" to: "<<edge[i].to<<endl;
add_edge2(edge[i].u,edge[i].to,edge[i].val);
add_edge2(edge[i].to,edge[i].u,edge[i].val);
}
}
}
void dfs(int u,int father)
{
\/\/ cout<<"node: "<<u<<endl;
dep[u]=dep[father]+1;
vis[u]=1;
for(register int i=head[u];i;i=edge2[i].nxt)
{
int to=edge2[i].to;
if(vis[to])continue;
fa[to][0]=u;
w[to][0]=edge2[i].val;
dfs(to,u);
}
}
inline int lca(int x,int y)
{
if(find(x)!=find(y))return -1;
int ans=inf;
if(dep[x]<dep[y])swap(x,y);
for(register int i=20;i>=0;i--)
{
if(dep[fa[x][i]]>=dep[y])
{
ans=min(ans,w[x][i]);
x=fa[x][i];
}
}
if(x==y)return ans;
for(register int i=20;i>=0;i--)
{
if(fa[x][i]!=fa[y][i])
{
ans=min(ans,w[x][i]);
ans=min(ans,w[y][i]);
x=fa[x][i];
y=fa[y][i];
}
}
ans=min(ans,min(w[x][0],w[y][0]));
return ans;
}
signed main()
{
int x,y,z;
n=read();
m=read();
for(register int i=1;i<=m;i++)
{
x=read();
y=read();
z=read();
add_edge(x,y,z);
}
sort(edge+1,edge+m+1,cmp);
for(register int i=1;i<=n;i++)f[i]=i;
kruscal();
for(register int i=1;i<=n;i++)
{
if(vis[i])continue;
dfs(i,0);
w[i][0]=inf;
fa[i][0]=i;
}
for(int i=0; i<20; i++)
{
for(int j=1; j<=n; j++)
{
fa[j][i+1]=fa[fa[j][i]][i];
w[j][i+1]=min(w[j][i], w[fa[j][i]][i]);
}
}
q=read();
for(register int i=1;i<=q;i++)
{
x=read();
y=read();
printf("%lld\n",lca(x,y));
}
return 0;
}
P3959 [NOIP2017 提高组] 宝藏
AC算法：dfs+状压
分析：
可以知道，每个点必然要算一次深度以及路径。所以可以通过已经更新的点u来推导未更新的点to，所以需要dfs。具体更新过程如下：
$Dep[to]=dep[u]+1$
F[to][当前点集][当前深度+1]=中间答案$cur+dis(u,to) * dep[u]$
那么点集如何表示呢？可以使用状压来解决，定义一个整数$dj$，初始默认为$1<<(i-1)$，这样它的第$i-1$位就是1，表示$i$存在于这个点集里。如果想要向其加入一个数$s$，就表示为： $dj |=(s-1)$，判断是否在点集里可以用if(($1<<(s-1)&dj$))来判断。
那么如何设状态呢？
可以用三维数组f，分别为当前点，当前点集，当前深度。
最后，就是边界条件的处理：
可以发现，每个点都更新完之后，肯定是dj的二进制每一位都是1。这个恰好等于(1<<n)-1，所以如果dj==(1<<n)-1，那么更新答案退出。
调了一个下午的AC代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,m;
const int inf=0x3f3f3f3f;
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<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
const int maxn=15;
int imap[maxn][maxn];
int ndep[maxn];\/\/记录从起点到路径开始
int ans=inf;
int f[maxn][8193][maxn];\/\/当前点，点集，深度
inline int min(int a,int b)
{
return a<b?a:b;
}
void dfs(int dj\/*点集*\/,int dep\/*深度*\/,int cur\/*当前解*\/)
{
if(cur>=ans)return;
if(dj==((1<<n)-1))\/\/边界条件
{
ans = cur;
return;
}
for(register int u=1;u<=n;u++)
{
if(!(1<<(u-1)&dj))continue;\/\/不在点集里，不能通过它更新其他点
for(register int to=1;to<=n;to++)
{
if(!(1<<(to-1)&dj)&&imap[u][to]<inf)
{
\/\/如果需要更新，且可以通过u更新
if(f[to][dj|(1<<(to-1))][dep+1]<=cur+imap[u][to]*ndep[u])
{\/\/如果下一步不是最优解，剪枝
continue;
}
f[to][dj|(1<<(to-1))][dep+1]=cur+imap[u][to]*ndep[u];
ndep[to]=ndep[u]+1;
dfs(1<<to-1|dj,dep+1,f[to][1<<(to-1)|dj][dep+1]);
}
}
}
}
int main()
{
memset(imap, 0x3f3f3f3f, sizeof(imap));
n = read();
m=read();
int x,y,v;
for(register int i=1;i<=m;i++)
{
x=read();
y=read();
v=read();
imap[x][y]=imap[y][x]=min(imap[x][y],v);
}
for(register int i=1;i<=n;i++)
{
memset(ndep,0,sizeof(ndep));
memset(f,0x3f3f3f3f,sizeof(f));
ndep[i] = 1;
dfs(1<<(i-1),0,0);
}
printf("%d",ans);
return 0;
}
如果是纯dfs呢，可以加两个剪枝就过了。第一个当然就 if(cur>ans)return;。这样就能获得70分的好成绩。第二个可以仿照状压dp的思路，定义一个三维数组f，代表当前点，当前深度，当前点数量（其实就相当于状压做法的点集），加上这句话：
if(f[to][sd[u]+1][tot+1]<cur+sd[u]*imap[u][to])
continue;
然后将更新点的部分改成这个：
f[to][sd[u] + 1][tot+1] = cur + sd[u] * imap[u][to];
sd[to]=sd[u]+1;
cur+=sd[u]*imap[u][to];
sd[to]=sd[u]+1;
tot++;
dfs(to,step+1,cur);
tot--;
cur-=sd[u]*imap[u][to];
sd[to]=0;
但是真的这样就行了吗？如果你交了这份代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,m;
const int inf=0x3f3f3f3f;
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<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
const int maxn=13;
int imap[maxn][maxn];
int sd[maxn];\/\/记录从起点到路径开始
int ans=inf;
int tot = 1;
int f[maxn] \/*第几个点*\/[maxn]\/*深度*\/[maxn]\/*tot*\/;
inline void memset()
{
for(int i=0;i<13;i++)
for(int j=0;j<13;j++)imap[i][j]=inf;
}
inline void memset2()
{
for(int j=0;j<13;j++)sd[j]=0;
}
inline int min(int a,int b)
{
return a<b?a:b;
}
void dfs(int x,int step,int cur)
{
if(cur>ans)return;
\/\/ cout<<"step: "<<step<<endl;
if(step==n)
{
ans=min(ans,cur);
\/\/ cout<<"cur: "<<cur<<endl;
return;
}
for(register int to=1;to<=n;to++)
{
if(!sd[to])\/\/ mod zgc
{
for(register int u=1;u<=n;u++)
{
if(imap[u][to]!=inf&&sd[u]!=0)
{
if(f[to][sd[u]+1][tot+1]<cur+sd[u]*imap[u][to])
continue;
if(cur+sd[u]*imap[u][to]>ans)continue;
f[to][sd[u] + 1][tot+1] = cur + sd[u] * imap[u][to];
sd[to]=sd[u]+1;
cur+=sd[u]*imap[u][to];
sd[to]=sd[u]+1;
tot++;
dfs(to,step+1,cur);
tot--;
cur-=sd[u]*imap[u][to];
sd[to]=0;
}
}
}
}
}
int main()
{
memset();
n=read();
m=read();
int x,y,v;
for(register int i=1;i<=m;i++)
{
x=read();
y=read();
v=read();
imap[x][y]=imap[y][x]=min(imap[x][y],v);
}
for(register int i=1;i<=n;i++)
{
tot = 1;
memset(f, 0x3f, sizeof(f));
sd[i]=1;
dfs(i,1,0);
sd[i]=0;
}
printf("%d",ans);
return 0;
}
将会收获：95分。
计算一下可以发现原来的不加第二个剪枝的算法可以在n=10的时候挺住。所以可以在n>10时使用剪枝，n<=10时使用原来的搜索。提交这份代码就可以AC。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,m;
const int inf=0x3f3f3f3f;
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<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
const int maxn=13;
bool vis[maxn][maxn];
int imap[maxn][maxn];
int sd[maxn];\/\/记录从起点到路径开始
int ans=inf;
int tot = 1;
int f[maxn] \/*第几个点*\/[maxn]\/*深度*\/[maxn]\/*tot*\/;
inline void memset()
{
for(int i=0;i<13;i++)
for(int j=0;j<13;j++)imap[i][j]=inf;
}
inline void memset2()
{
for(int j=0;j<13;j++)sd[j]=0;
}
inline int min(int a,int b)
{
return a<b?a:b;
}
void dfs(int x,int step,int cur)
{
if(cur>ans)return;
\/\/ cout<<"step: "<<step<<endl;
if(step==n)
{
ans=min(ans,cur);
\/\/ cout<<"cur: "<<cur<<endl;
return;
}
for(register int to=1;to<=n;to++)
{
if(!sd[to])\/\/ mod zgc
{
for(register int u=1;u<=n;u++)
{
if(imap[u][to]!=inf&&sd[u]!=0)
{
if(f[to][sd[u]+1][tot+1]<cur+sd[u]*imap[u][to])
continue;
if(cur+sd[u]*imap[u][to]>ans)continue;
f[to][sd[u] + 1][tot+1] = cur + sd[u] * imap[u][to];
sd[to]=sd[u]+1;
cur+=sd[u]*imap[u][to];
sd[to]=sd[u]+1;
tot++;
dfs(to,step+1,cur);
tot--;
cur-=sd[u]*imap[u][to];
sd[to]=0;
}
}
}
}
}
void dfs_henman(int x,int step,int cur)
{
if(cur>ans)return;
if(step==n)
{
ans=min(ans,cur);
return;
}
for(register int to=1;to<=n;to++)
{
if(!sd[to])\/\/ mod zgc
{
for(register int u=1;u<=n;u++)
{
if(imap[u][to]!=inf&&sd[u]!=0)
{
if(cur+sd[u]*imap[u][to]>ans)continue;
sd[to]=sd[u]+1;
cur+=sd[u]*imap[u][to];
sd[to]=sd[u]+1;
dfs_henman(to,step+1,cur);
cur-=sd[u]*imap[u][to];
sd[to]=0;
}
}
}
}
}
int main()
{
memset();
n=read();
m=read();
int x,y,v;
for(register int i=1;i<=m;i++)
{
x=read();
y=read();
v=read();
imap[x][y]=imap[y][x]=min(imap[x][y],v);
}
if(n>10)
{
for(register int i=1;i<=n;i++)
{
tot = 1;
memset(f, 0x3f, sizeof(f));
sd[i]=1;
dfs(i,1,0);
sd[i]=0;
}
}
if(n<=10)
{
for(register int i=1;i<=n;i++)
{
sd[i]=1;
dfs_henman(i,1,0);
sd[i]=0;
}
}
printf("%d",ans);
return 0;
}
此时对比一下：dfs解法提交记录和状态压缩解法提交记录，dfs用了102ms，状压用了405ms，dfs比状压快了5倍！！！！！！
CF1137C Museums Tour
$\color{green}\text{AC算法：}$tarjan缩点+dfn最长路
难度：$\color{purple}\text{省选/NOI-}$
题目内容：
有 $n$ 个城市，$m$ 条边，每周有 $d$ 天，每个城市都会在每周特定的时间开放博物馆，旅行者可以无限走，也可以随时停下来。求参观的不同博物馆数量尽量多。
题目分析
难点就在于每周都有一个轮回，每个城市都在特定时间开放，可以看作题目提供的图 $G1$ 中的点有时候有点权有时没点权。所以可以将每个点拆成 $d$ 个点，每个点 $u$ 连接明天的点 $v$，如果当前 $u$ 已经是第 $d$ 天，那么连接第 $1$ 天的 $v$。这样每条边都有了明确的点权。然后就是如何处理题目中的环，可以用 tarjan 算法将每个环缩成一个强连通分量，每个强连通分量（新的点）的点权就是其中所有原来点权的和。最后将所有强连通分量建边就构成了一张新的图 $G2$，在 $G2$中用 dfs 求最长路即可。
鲁ICP备2025150228号