洛谷4201 [NOI2008]道路设计

Luogu

BZOJ

分析

首先,每个点只能被修一次,代表它最多与两条铁路相连。

然后,发现答案不会太大,大概在$\log$级别。

于是设$f[i][j][k]\ (k\in\{0,1,2\})$表示以$i$为根的子树,答案为$j$,与$k$条铁路相连的方案数。

转移枚举子节点修还是不修即可,比较简单 。

最后答案怎么搞见代码。

还有,因为把未计算过的状态标为$0$,所以最好取膜后不要出现$0$,也就是让$Q$取膜后还是$Q$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

struct Edge { int v,nxt; };
Edge e[N<<1];
int head[N],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}

int n,m,Q,tot=0;
int f[N][20][3];

inline void dfs(int u,int fa) {
    ++tot;
    for (re int i=0;i<20;++i) f[u][i][0]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs(v,u);
        for (re int j=0;j<20;++j) {
            int A=0,B=0;
            if (j) A=(1ll*f[v][j-1][0]+f[v][j-1][1]+f[v][j-1][2]-1)%Q+1;
            B=(1ll*f[v][j][0]+f[v][j][1]-1)%Q+1;
            f[u][j][2]=(1ll*f[u][j][2]*A+1ll*f[u][j][1]*B-1)%Q+1;
            f[u][j][1]=(1ll*f[u][j][1]*A+1ll*f[u][j][0]*B-1)%Q+1;
            f[u][j][0]=(1ll*f[u][j][0]*A-1)%Q+1;
        }
    }
}

int main() {
    n=read(),m=read(),Q=read();
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs(1,0); if (tot<n) { puts("-1\n-1"); return 0; }
    int ans=0x3f3f3f3f,sum=0;
    for (re int i=0;i<20;++i)
        if (f[1][i][0]||f[1][i][1]||f[1][i][2]) { ans=i; break; }
    sum=(1ll*f[1][ans][0]+f[1][ans][1]+f[1][ans][2])%Q;
    printf("%d\n%d\n",ans,sum);
    return 0;
}
最后修改:2019 年 09 月 24 日 10 : 17 PM

4 条评论

  1. smy

    怎么就Bzoj200AC了
    %%%%%%%%%%

    1. M_sea
      @smy

      您又不把以前的题交上来qwq

      1. smy
        @M_sea

        交了也没200qwq

        1. M_sea
          @smy

          假死了 您可是LuoguAC900的神仙

发表评论