蒟蒻の图论刷题(更新中)Ⅰ 树/图dp

Dulcea ·

更新时间:2024-11-13

· 881 次阅读

总算来补自己好久前买下的坑了，题目内容均来自洛谷题单

目录[TJOI2017]可乐[ZJOI2006]物流运输[HNOI/AHOI2018]道路[ZJOI2007]时态同步[TJOI2017]城市 [TJOI2017]可乐

tag上是分层图+矩阵优化，但是被我用暴力+滚动数组水过去了（赞美O2！）对每个点有三种状态，0：上一秒已经在这个城市了；1：这一秒刚到；2：自爆。只需要记录最后时刻0、1的和以及所有时刻2的和即可，注意滚动数组的更新。

#include
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
#define mod 2017
#define IOS  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define maxn 40
vector g[40];
const int N = 1e6+5;
int dp[maxn][3][2];int n,m,t;
//0 原地 1 移动 2爆炸
int main(){
    IOS
    cin>>n>>m;
    while(m--){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dp[1][0][0]=1;
    cin>>t;
    int cnt=1;
    ll ans=0;
    for (int i = 1; i <=t ; ++i) {
        for (int j = 1; j <=n ; ++j) {
            int tmp=((cnt-1)%2+2)%2;
            dp[j][0][cnt]=(dp[j][0][tmp]+dp[j][1][tmp])%mod;
            dp[j][2][cnt]=(dp[j][1][tmp]+dp[j][0][tmp])%mod;
            for(auto k:g[j]){
                dp[k][1][cnt]+=(dp[j][1][tmp]+dp[j][0][tmp])%mod;
            }
            dp[j][1][tmp]=0;
            ans=(ans+dp[j][2][cnt])%mod;
        }
        cnt++;
        cnt%=2;
    }
    cnt=((cnt-1)%2+2)%2;
    for (int l = 1; l <=n ; ++l) {
        ans=(ans+dp[l][0][cnt]+dp[l][1][cnt])%mod;
    }
    cout<<ans;
    return 0;
}

[ZJOI2006]物流运输

~~这种数据范围当然直接暴力啦~~
（又是写乱前向星的日常，debug了半天发现是前向星的锅）
一道不错的最短路+dp的题，先记录每个码头不能运输的日子，然后用dp[i][j]记录i到j天的最短路，然后就是从1开始枚举+区间分割了。

#include
#define ll long long
#define fi first
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
#define mod 2017
#define IOS  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define maxn 25
#define int long long
struct edge{
    int u,v,w,nxt;
}E[2010];
int head[maxn],cnt=0;
void addedge(int u,int v,int w){
    E[cnt].nxt=head[u];
    head[u]=cnt;
    E[cnt].u=u;
    E[cnt].v=v;
    E[cnt++].w=w;
}
int n,m,k,e;
int wx[maxn][110],wait[maxn],vis[maxn];
int way[110][110],d[maxn];
int spfa(int x,int y){
    memset(wait,0, sizeof(wait));
    memset(vis,0, sizeof(vis));
    for (int i = 1; i <=m ; ++i){
        d[i]=0x3f3f3f3f3f3f3f;
        for (int j = x; j <=y ; ++j) {
            if(wx[i][j]){wait[i]=1;}
        }
    }
    d[1]=0;
    queue q;
    q.push(1);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        vis[now]=0;
        for (int i = head[now]; i !=-1 ; i=E[i].nxt) {
            int v=E[i].v,w=E[i].w;
            if(wait[v])continue;
            if(d[v]>=d[now]+w){
                d[v]=d[now]+w;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return d[m];
}
int ans[110];
signed main(){
    IOS
    cin>>n>>m>>k>>e;
    memset(head,-1,sizeof head);
    memset(wx,0, sizeof(wx));
    while(e--){
        int u,v,w;
        cin>>u>>v>>w;
        addedge(u,v,w);
        addedge(v,u,w);
    }
    int tmp;
    cin>>tmp;
    while(tmp--){
        int p,a,b;
        cin>>p;
        cin>>a>>b;
        for (int i = a; i <=b ; ++i) {
            wx[p][i]=1;
        }
    }
    for (int i = 1; i <=n ; ++i) {
        for (int j = i; j <=n ; ++j) {
            way[i][j]=spfa(i,j);
        }
        ans[i]=0x3f3f3f3f3f3f3f;
    }
    ans[0]=-k;
    for (int l = 1; l =0 ; --i) {
            ans[l]=min(ans[l],ans[i]+way[i+1][l]*(l-i)+k);
        }
    }
    cout<<ans[n];
    return 0;
}

[HNOI/AHOI2018]道路

本来挺简单的，但是被我日常不看完条件，硬是卡了半天没出QAQ
题目中说的很清楚了，每个城市选一条道路，那我们就可以开一个三维数组，记录到第u个节点时，有i条未翻修公路和j条未翻修铁路的不便利值（由于深度不超过40，后两维开到45就可）。每次向下走，有两种可能，一种是修公路，一种是修铁路。到叶节点时，直接计算，然后向上更新即可。

#include
#define ll long long
using namespace std;
#define mod 2017
#define IOS  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define maxn 40005
int n;
const int N = 20005;
int son[maxn][2];
struct node{
    ll a,b,c;
}v[maxn];
ll dp[N][45][45];
ll dfs(int rt,int x,int y){
    if(son[rt][0]==son[rt][1]){
        return v[rt].c*(v[rt].a+x)*(v[rt].b+y);
    }
    if(dp[rt][x][y]>=9187201950435737000)dp[rt][x][y]=min(dfs(son[rt][0],x+1,y)+dfs(son[rt][1],x,y),dfs(son[rt][1],x,y+1)+dfs(son[rt][0],x,y));
    return dp[rt][x][y];
}
signed main(){
    IOS
    cin>>n;
    memset(dp,0x7f, sizeof(dp));
    for (int i = 1; i >s>>t;
        if(s<0){
            s*=-1;
            s+=n-1;
        }
        if(t<0){
            t*=-1;
            t+=n-1;
        }
        son[i][0]=s;
        son[i][1]=t;
    }
    for (int j = 1; j >v[j+n-1].a>>v[j+n-1].b>>v[j+n-1].c;
    }
    cout<<dfs(1,0,0);
    return 0;
}

[ZJOI2007]时态同步

虽然题意说的很多，但其实就是以s为根，所有的终止节点即为叶节点。那么两遍dfs就能过了这道题。显然最优方案就是将所有叶节点的费用变成初始费用的最大值，那么第一次dfs先求出最大值。第二次dfs时，先求出每个叶节点变成最大值需要增加多少次，找出相同父亲的叶节点中花费的最小值，这个最小值我们就可以通过改变父节点与其父亲的连边来减少次数，多余的就直接加入答案即可，向上同理。

#include
#define ll long long
using namespace std;
#define mod 2017
#define IOS  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define maxn N
int n,s;
ll ans=0,ma=0;
const int N = 5e5+5;
struct edge{
    int u,v,w,nxt;
}e[N*2];
int head[maxn],cnt=0;
void add(int u,int v,int w){e[cnt].u=u;e[cnt].v=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt++;}
ll w[maxn],t[maxn],leave[maxn];
void dfs1(int x,int fa){
    int fl=0;
    for (int i = head[x]; i !=-1 ; i=e[i].nxt) {
        if(e[i].v==fa)continue;
        t[e[i].v]=t[x]+e[i].w;
        dfs1(e[i].v,x);
        fl=1;
    }
    if(!fl){
        leave[x]=1;
        ma=max(ma,t[x]);
    }
}
void dfs2(int x,int fa){
    if(leave[x]){
        w[x]=ma-t[x];
        return ;
    }
    ll mi=0x3f3f3f3f3f3f3f3f;
    for (int i = head[x]; i !=-1 ; i=e[i].nxt) {
        if(e[i].v==fa)continue;
        dfs2(e[i].v,x);
        mi=min(mi,w[e[i].v]);
    }
    for (int i = head[x]; i !=-1 ; i=e[i].nxt) {
        if(e[i].v==fa)continue;
        ans+=w[e[i].v]-mi;
    }
    w[x]=mi;
}
signed main(){
    IOS
    cin>>n>>s;
    memset(head,-1, sizeof(head));
    for (int i = 0; i >u>>v>>we;
        add(u,v,we);
        add(v,u,we);
    }
    dfs1(s,0);
    dfs2(s,0);
    cout<<ans;
    return 0;
}

[TJOI2017]城市

树的直径＋树的半径
由于数据范围比较小，可以直接O(n^2)dfs。枚举删除的边，每次会产生两个联通块，此时的答案有三种可能：

联通块A的直径联通块B的直径联通块A的半径最小值+联通块B的半径最小值+边的权值

直径就很好求了，对于以v为根的子树，设其父亲结点为f，那么半径的值有三种可能：

子树v的最长链子树f中的最长链+v和f的距离子树f外的最长链+v和f的距离

#include
#define ll long long
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
#define IOS  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = 5e3+5;int n,col[N];
struct edge{
    int u,v,w,nxt;
}e[N*2];
struct node{
    int u,v,w;
};
vector t;
int head[N],cnt=0;
void add(int u,int v,int w){e[cnt].u=u;e[cnt].v=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt++;}
int r[N],d_max=0,dm[N],dm_c[N];
void dfs_d(int x,int fa,int c){
    dm[x]=0;
    col[x]=c;
    int ma1=0,ma2=0;
    for (int i = head[x]; i !=-1 ;i=e[i].nxt) {
        int v=e[i].v;
        if(v==fa)continue;
        dfs_d(v,x,c);
        if(dm[v]+e[i].w>ma1){
            ma2=ma1;
            ma1=dm[v]+e[i].w;
        }else{
            if(dm[v]+e[i].w>ma2)ma2=dm[v]+e[i].w;
        }
    }
    dm[x]=ma1;
    dm_c[x]=ma2;
    d_max=max(d_max,ma1+ma2);
}
void dfs_r(int x,int fa,int fr){
    int tmp=0;
    for (int i = head[x]; i !=-1 ; i=e[i].nxt) {
        int v=e[i].v,w=e[i].w;
        if(v==fa)continue;
        if(dm[v]+w==dm[x]){
            r[v]=max(dm[v],w+dm_c[x]);
            tmp=max(fr,dm_c[x]);
        }else{
            r[v]=max(dm[v],dm[x]+w);
            tmp=max(fr,dm[x]);
        }
        r[v]=max(r[v],tmp+w);
        dfs_r(v,x,tmp+w);
    }
}
signed main(){
    IOS
    cin>>n;
    memset(head,-1, sizeof(head));
    for (int i = 0; i >u>>v>>w;
        t.push_back({u,v,w});
        add(u,v,w);
        add(v,u,w);
    }
    ll ans=0x3f3f3f3f3f3f3f3f;
    for(auto i:t){
        int u=i.u,v=i.v,w=i.w;
        d_max=0;
        dfs_d(u,v,1);
        dfs_d(v,u,2);
        r[v]=dm[v];r[u]=dm[u];
        dfs_r(u,v,0);dfs_r(v,u,0);
        for (int j = 1; j <=n ; ++j) {
            if(col[j]==1&&r[j]<r[u])u=j;
            if(col[j]==2&&r[j]<r[v])v=j;
        }
        ans=min(ans,max(d_max,r[u]+r[v]+w)*1ll);
    }
    cout<<ans;
    return 0;
}