首页 > 其他 > 详细

【逛公园】

时间:2019-01-01 22:07:58      阅读:23      评论:0      收藏:0      [点我收藏+]

标签:tarjan   ()   cpp   cond   reg   如果   include   main   set   

我在有0环的图里跑了最短路计数

我可能已经是个废物啦

很早之前就想写这道题啦,但是太菜了发现自己不会,今天终于写啦

首先我们建图的时候建出一个正图还有一个反图,我们对着这两个图分别跑两次最短路,求出\(1\)到所有点的最短路,以及所有点到\(n\)的最短路

如果不考虑无解的情况,我们现在就可以大力记搜了

我们设\(dp[x][j]\)表示从\(x\)走到\(n\)相比\(x\)\(n\)的最短路多走了\(j\)的路径条数

之后大力记搜即可,\(ans=\sum_{i=0}^Kdp[1][i]\)

我们去记忆化搜索就行了,比如说从\(dp[i][now]\)转移到\(j\)这个点,我们转移的条件就是从\(i\)\(j\)有一条边相连,之后由于\(dp[i][now]\)这个状态要走的路程是\(dis[i]+now\),之后走了一条\(dis(i,j)\)的路径,到了\(j\)点还要走的就是\(dis[i]+now-dis(i,j)\),相比最短路多走的就是\(dis[i]+now-dis(i,j)-dis[j]\),于是我们直接在记搜里这样转移就好了

之后边界条件就是\(dp[n][0]=1\)

再来考虑一下如何判断无解的情况

显然如果有\(0\)环,而且环里有一个点到\(1\)\(n\)的最短路的和走的冤枉路小于\(K\),那么就可以在这个环里一直绕下去,就会出现无解了

显然我们只需要考虑\(0\)环的话,我们只需要建一张只有\(0\)边的图就行了,对这张图跑一个\(topsort\)或者\(tarjan\),之后判断环里是否有这种点就可以啦

其实不不是非常难,主要就是\(dp\)的思想还有最简单的图论

但是我非常sb,我对于存在\(0\)环的图跑了最短路计数,显然这种图的最短路条数是无限的,这样跑出来显然是错的

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define re register
#define maxn 100005
#define LL long long
#define mp std::make_pair
int n,m,K,num[2],cnt;
int mod;
typedef std::pair<int,int> pii;
std::priority_queue<pii,std::vector<pii>,std::greater<pii> > q;
struct node
{
    int v,nxt,w;
}e[2][maxn<<1];
struct ZE
{
    int v,nxt;
}E[maxn<<1];
int Head[maxn];
inline void write(int x) 
{
     if(x>9) write(x/10);
     putchar(x%10+‘0‘);
}
inline void add(int x,int y)
{
    E[++cnt].v=y;
    E[cnt].nxt=Head[x];
    Head[x]=cnt;
}
int dp[maxn][51],Q[maxn],r[maxn];
int head[2][maxn],dis[2][maxn];
int f[maxn];
inline int read()
{
    char c=getchar();
    int x=0;
    while(c<‘0‘||c>‘9‘) c=getchar();
    while(c>=‘0‘&&c<=‘9‘)
      x=(x<<3)+(x<<1)+c-48,c=getchar();
    return x;
}
inline void add_edge(int x,int y,int z,int opt)
{
    e[opt][++num[opt]].v=y;
    e[opt][num[opt]].nxt=head[opt][x];
    e[opt][num[opt]].w=z;
    head[opt][x]=num[opt];
}
inline void dij(int s,int o)
{
    memset(f,0,sizeof(f));
    while(!q.empty()) q.pop();
    dis[o][s]=0;
    if(o) dp[s][0]=1;
    q.push(mp(dis[o][s],s));
    while(!q.empty())
    {
        int k=q.top().second;
        q.pop();
        if(f[k]) continue;
        f[k]=1;
        for(re int i=head[o][k];i;i=e[o][i].nxt)
        if(dis[o][e[o][i].v]>dis[o][k]+e[o][i].w)
        {
            dis[o][e[o][i].v]=dis[o][k]+e[o][i].w;
            q.push(mp(dis[o][e[o][i].v],e[o][i].v));
        }
    }
}
int dfs(int x,int now)
{
    if(dp[x][now]) return dp[x][now]%mod;
    for(re int i=head[0][x];i;i=e[0][i].nxt)
    if(dis[1][x]-dis[1][e[0][i].v]-e[0][i].w+now>=0)
        dp[x][now]=(dp[x][now]+dfs(e[0][i].v,dis[1][x]-dis[1][e[0][i].v]-e[0][i].w+now))%mod;
    return dp[x][now]%mod;
}
int main()
{
    int T=read();
    while(T--)
    {
        cnt=num[0]=num[1]=0;
        memset(Head,0,sizeof(Head));
        memset(head,0,sizeof(head));
        memset(dis,0x7f,sizeof(dis));
        memset(dp,0,sizeof(dp));
        memset(Q,0,sizeof(Q));
        memset(r,0,sizeof(r));
        n=read(),m=read(),K=read(),mod=read();
        int x,y,z;
        for(re int i=1;i<=m;i++)
        {
            x=read(),y=read(),z=read();
            if(!z) add(x,y),r[y]++;
            add_edge(x,y,z,0),add_edge(y,x,z,1);
        }
        dij(1,0),dij(n,1);
        int tot=0;
        for(re int i=1;i<=n;i++)
            if(!r[i]) Q[++tot]=i;
        for(re int i=1;i<=tot;i++)
        {
            int t=Q[i];
            for(re int j=Head[t];j;j=E[j].nxt)
            {
                r[E[j].v]--;
                if(!r[E[j].v]) Q[++tot]=E[j].v;
            }
        }
        int flag=0;
        for(re int i=1;i<=n;i++)
        if(r[i]&&dis[0][i]+dis[1][i]<=dis[0][n]+K)
        {
            puts("-1");
            flag=1;
            break;
        }
        if(flag) continue;
        int ans=0;
        for(re int i=0;i<=K;i++) ans=(ans+dfs(1,i))%mod;
        write(ans),putchar(10);
    }
    return 0;
}

【逛公园】

标签:tarjan   ()   cpp   cond   reg   如果   include   main   set   

原文:https://www.cnblogs.com/asuldb/p/10206236.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 designnerd.net 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号