CF 1137 C. Museums Tour

r囧r小猫 2022-01-05 04:39 192阅读 0赞

### 题目大意： ###

一个国家有 $n$ 个城市，通过 $m$ 条单向道路相连。有趣的是，在这个国家，每周有 $d$ 天，并且每个城市恰好有一个博物馆。

已知每个博物馆一周的营业情况（开门或关门）和 $m$ 条单向道路，由于道路的设计，每条道路都需要恰好一个晚上的时间通过。你需要设计一条旅游路线，使得从首都：$1$ 号城市开始，并且当天是本周的第一天。每天白天，如果当前城市的博物馆开着门，旅行者可以进入博物馆参观展览，否则什么也做不了，这一天的晚上，旅行者要么结束行程，要么通过一条道路前往下一个城市。当然，旅行者可以多次经过一个城市。

要求让旅行者能够参观的不同博物馆数量尽量多（同一个城市的博物馆参观多次仅算一次），请你求出这个最大值。

### 思路： ###

考虑把每个点拆成 $d$ 个点，可以证明如果把 $d\*n$ 个点跑 $tarjan$ 得到强连通分量，不存在两个相同节点缩完点后在同一条路径里而不在同一个联通块里。

于是我们考虑缩完后，缩点时不重复的算出每个强连通分量里的答案，最后在所处的强连通分量之间 $DP$ 即可。

### 以下代码： ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    #define il inline
    #define _(d) while(d(isdigit(ch=getchar())))
    using namespace std;
    const int N=3e5+5,M=5e5+5;
    bool vis[N];
    int q[N],tot,fa[N];
    int n,m,k,head[N],ne[M<<1],to[M<<1],cnt,d[N];
    il int read(){
       int x,f=1;char ch;
       _(!)ch=='-'?f=-1:f;x=ch^48;
       _()x=(x<<1)+(x<<3)+(ch^48);
       return f*x;
    }
    il void ins(int x,int y){
        ne[++cnt]=head[x];
        head[x]=cnt;to[cnt]=y;
    }
    il void dfs(int x){
        vis[x]=1;
        if(d[x]>=(n+k-1)/k){
            puts("PATH");printf("%d\n",d[x]);
            while(x)printf("%d ",x),x=fa[x];
            exit(0);
        }
        bool pd=0;
        for(int i=head[x];i;i=ne[i]){
            if(fa[x]==to[i]||vis[to[i]])continue;
            fa[to[i]]=x;d[to[i]]=d[x]+1;pd=1;
            dfs(to[i]);
        }
        if(!pd)q[++tot]=x;
    }
    int main()
    {
        n=read();m=read();k=read();
        for(int i=1;i<=m;i++){
            int x=read(),y=read();
            ins(x,y);ins(y,x);
        }
        d[1]=1;dfs(1);
        puts("CYCLES");
        for(int j=1;j<=k;j++){
            int x=q[j],y=0,z=0;
            for(int i=head[x];i;i=ne[i]){
                if(fa[x]==to[i])continue;
                if(!y)y=to[i];else z=to[i];
            }
            int res=d[x]-d[y]+1;
            if(res%3){
                printf("%d\n",res);
                while(x!=y){
                    printf("%d ",x);x=fa[x];
                }
                printf("%d\n",y);continue;
            }
            res=d[x]-d[z]+1;
            if(res%3){
                printf("%d\n",res);
                while(x!=z){
                    printf("%d ",x);x=fa[x];
                }
                printf("%d\n",z);continue;
            }
            if(d[y]<d[z])swap(y,z);
            res=d[y]-d[z]+2;
            printf("%d\n",res);
            while(y!=z){
                printf("%d ",y);y=fa[y];
            }
            printf("%d %d\n",z,x);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Jessie-/p/10544649.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211230/fd15de99b180422caa9cdf7237800fb9.png