P9504题解

· · 题解

传送门

思路分析

看到这个题第一眼时，我想到了暴力枚举（深搜）。

因为一共有 m 条边，所以魔法值肯定是不大于 m 的（就算每条边都走一次，魔法值也只会减 m）。我们循环枚举魔法值，从 1 枚举到 m，再依次开始深搜。

深搜的过程是，因为一共有 n 个节点，我们枚举每个节点可以到达哪些节点，如果可以到达，则向此节点深搜，直到到达终点为止。需要注意的是，当魔法值小于 0 时，或者此节点已经搜索过，那么返回上个搜索。如果刚好到达了终点且魔法值为 0，则更新答案。

Code

#include<iostream>
#include<algorithm>
using namespace std;
struct tu
{
    int a,b,c;
}s[40005];
int ans;
int vis[40005];
int k[40005];
int n,m,ss,t;
bool cmp(tu l,tu r)
{
    if(l.a!=r.a)
        return l.a<r.a;
    return l.b<r.b;
}
int an=1000000000;
void dfs(int num,int sum,int ww)
{
    if(ww<0)
        return;
    if(num==t)
    {
        if(sum<an&&ww==0)
            an=sum;
        return;
    }
    if(ww<=0)
        return;
    for(int i=k[num];i<=2*m;i++)
    {
        if(s[i].a!=num)
            break;
        if(vis[s[i].b]==0&&ww<=s[i].c)
        {
            vis[s[i].b]=1;
            dfs(s[i].b,sum+(s[i].c/ww),ww-1);
            vis[s[i].b]=0;
        }
    }
}
int main()
{
    cin>>n>>m>>ss>>t;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        ans++;
        s[ans].a=x;
        s[ans].b=y;
        s[ans].c=z;
        ans++;
        s[ans].a=y;
        s[ans].b=x;
        s[ans].c=z;
    }
    sort(s+1,s+1+ans,cmp);
    for(int i=1;i<=ans;i++)
    {
        if(s[i].a!=s[i-1].a)
        {
            k[s[i].a]=i;
        }
    }
    vis[ss]=1;
    long long tmp=10000000000;
    for(int i=1;i<=m;i++)
    {
        an=100000000;
        dfs(ss,0,i);
        if(an<tmp)
        tmp=an;
    }
    cout<<tmp;
}

当然，在正常情况下，暴力枚举是会超时的，不出意外，这份代码只能通过第一个捆绑测试点。那有什么更好的方法呢？

本人发现，可以用深搜来做的题一般也可以用背包做。仔细思考一下，转移方程还是很好构造的。我们用一个二维背包来记录当每个点拥有每个魔法值时，需要多少生命到达终点。

不难发现，我们枚举每条边，边上的其中一个点要到达终点，可以经过边上的另一个点到达终点。那么我们得出了方程（用背包的第一位记录这是哪个节点，用第二维来记录魔法值）：dp[u[i]][j]=\min(dp[u[i]][j],dp[v[i]][j-1]+w[j]/i)

数组 u 记录的是每条边上的其中一个点，而数组 v 记录的则是另一个点，数组 w 记录的是每条边上魔兽的攻击力，可以看成每条边的边权。

对于方程，我们可以这样理解：因为没从一个点到另一个点，生命值都会减去边权除以当前魔法值，所以，为了保证生命尽可能小而又不会小于 0，所以，如果要经过这条边，那么生命值就要加上边权除以当前魔法值。

需要注意的是，我们尽可能将背包的初始值设大，但因为从终点到达终点的生命值只需要 0，所以将 dp[t][0] 的值设为 0 即可（t 指的是终点）。

因为每只魔兽的攻击力是不超过 100 的，所以魔力值也不会超过 100。最后，我们只需要循环枚举每个魔力值，求出其中的最小值即可（数组的第一维是起点，第二维是枚举的魔力值）。

AC 代码

#include<iostream>
#include<algorithm>
using namespace std;
int a[80005][105];
int u[80005],v[80005],w[80005];
int main()
{
    int n,m,s,t;
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        cin>>u[i]>>v[i]>>w[i];
        u[i+m]=v[i];
        v[i+m]=u[i];
        w[i+m]=w[i];
    }
    for(int i=1;i<=n;i++)
        for(int j=0;j<=100;j++)
        a[i][j]=100000000;
    a[t][0]=0;
    for(int i=1;i<=100;i++)
        for(int j=1;j<=2*m;j++)
        {
            a[u[j]][i]=min(a[u[j]][i],a[v[j]][i-1]+(w[j]/i));
        }
    int ans=100000000;
    for(int i=1;i<=100;i++)
        ans=min(ans,a[s][i]);
    for(int i=1;i<=n;i++)
        ans=min(ans,a[i][100]);
    cout<<ans;
}

注意，之所以在读入时增加了三行，是因为，我们读入的第一个点可以到达第二个点，而第二个点也可以到达第一个点。我们将每条边看为一条有向边，则一共有 m 条无向边，也就有 2 \times m 条有向边。在创建第二条有向边时，数组下标设为 i+m 便不会和其他边发生冲突。