题解：AT_abc372_f [ABC372F] Teleporting Takahashi 2

· · 题解

有点诈骗感的题，可惜赛时没改出来。

思路

发现 m\le 50，而和这 m 条边无关的其他点只有一条路能走，这意味着到这些点时只有一种选择，那么我们完全可以将这些点合并到其他有价值的点上去，这样缩完图之后最多只有 101 个点，范围很小，思路就容易出了。

方案这类问题一般采取 dp 的办法。设 f_{i,j} 表示在点 i 花费为 j 的方案数，外层枚举花费，内层枚举缩完后的每个点，根据连边情况转移，状态转移方程为：

f_{v,i}+=f_{j,i-w}\ \ \ (i\ge w)

其中 v 为与 j 连接的边的终点，w 为边权，复杂度 \mathcal{O(km)}。

发现最后有可能停在被合并的点上，于是我们记录每条有缩点的边的边权，最后特殊处理一下即可。

细节

缩点上，考虑记录每条边的出度入度，都为 0 的就合并掉，遇到其他的点就遇上一个缩完的点连边，记得连最后一个点和起点 1 的那条边！

dp 边界 f_{1,0}=1，比较易得，其他就是取模问题等小事了。

实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
    char ch=getchar();lx x=0,f=1;
    for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=2e5+5,NN=105;
const int mod=998244353;
int n,m,k,tot=1;// 缩后图中点个数
int ds[N],rpre[N],ff[NN];
// 每点度数 映射：原点->缩后点 缩点边权
ll f[NN][N],ans;
struct edge{int u,v;}e[55];
int hh[NN],ne[NN<<1],to[NN<<1],w[NN<<1],cnt;
namespace Wisadel
{
    void Wadd(int u,int v,int va)
    {
        to[++cnt]=v;
        w[cnt]=va;
        ne[cnt]=hh[u];
        hh[u]=cnt;
    }
    short main()
    {
        memset(hh,-1,sizeof hh);
        n=qr,m=qr,k=qr;
        for(int i(1);i<=m;i++) e[i].u=qr,e[i].v=qr,ds[e[i].u]++,ds[e[i].v]++;
        rpre[1]=1;
        int ddd=1,las=1;
        for(int i(2);i<=n;i++)
        {
            if(!ds[i]) ddd++;// 没用的点使边权++
            else rpre[i]=++tot,ff[las]=ddd,Wadd(las,tot,ddd),las=tot,ddd=1;
            // 记录有关变量 连边
        }
        Wadd(las,1,ddd),ff[las]=ddd;
        // 处理最后一个点和边
        for(int i(1);i<=m;i++)
        {
            int u=rpre[e[i].u],v=rpre[e[i].v];
            Wadd(u,v,1);
        }
        f[1][0]=1;
        for(int i(1);i<=k;i++) for(int j(1);j<=tot;j++)
        {// dp
            for(int ee=hh[j];ee!=-1;ee=ne[ee])
            {
                int v=to[ee],va=w[ee];
                if(i>=va)
                    f[v][i]=(f[v][i]+f[j][i-va])%mod;
            }
        }
        for(int i(1);i<=tot;i++)
        {
            ans=(ans+f[i][k])%mod;
            for(int j=1;j<=ff[i]-1;j++) ans=(ans+f[i][k-j])%mod;
            // 计算没到缩点的情况的答案
        }
        printf("%lld\n",ans);
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

完结撒花~