[POI2006] PRO-Professor Szu

Description

\(n\) 个别墅以及一个主建筑楼，从每个别墅都有很多种不同方式走到主建筑楼，其中不同的定义是（每条边可以走多次，如果走边的顺序有一条不同即称两方式不同）。

询问最多的不同方式是多少，以及有多少个别墅有这么多方式，按照顺序输出别墅编号。

如果最多不同方式超过了 \(36500\) 那么都视作 \(zawsze\)

Solution

因为统计其它 \(n\) 个点到主建筑楼的方案数有点困难，我们转化一下问题，反向建边，变成求从主建筑楼到其它 \(n\) 个点的方案数，这样源点就只有一个了。

先 \(Tarjan\) 消环，然后拓扑求出从起点所在联通块到每个点所在联通块的方案数。注意到起点不一定是度数为零的点，所以不能直接将起点 \(push\) 进队列里，而是应该像常规的拓扑排序一样将所有度数为零的点 \(push\) 进去。

还有要注意的是如果当前联通块有环并且能从起点走到该联通块的话，就应该让起点到这个联通块的方案数等于 \(36501\)，然后继续向下处理。（这里特别要注意能否走到该联通块）

Code

#include<queue>

#include<vector>

#include<cstdio>

#include<cctype>

#include<algorithm>

#define N 1000005

#define min(A,B) ((A)<(B)?(A):(B))

#define max(A,B) ((A)>(B)?(A):(B))

int dis[N];

int deg[N];

int n,m,pos;

int sum,tot;

int print[N];

int belong[N];

int stk[N],top;

bool in[N],is[N];

int dfn[N],low[N];

int cnt,head[N],head2[N];

std::vector<int> v[N],vans;

struct Edge{

    int to,nxt;

}edge[N<<1],edge2[N<<1];

void add(int x,int y){

    edge[++cnt].to=y;

    edge[cnt].nxt=head[x];

    head[x]=cnt;

}

void add2(int x,int y){

    edge2[++cnt].to=y;

    edge2[cnt].nxt=head2[x];

    head2[x]=cnt;

}

int getint(){

    int x=0;char ch=getchar();

    while(!isdigit(ch)) ch=getchar();

    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

    return x;

}

void tarjan(int now){

    dfn[now]=low[now]=++tot;

    stk[++top]=now,in[now]=1;

    for(int i=head[now];i;i=edge[i].nxt){

        int to=edge[i].to;

        if(!dfn[to]){

            tarjan(to);

            low[now]=min(low[now],low[to]);

        }

        else if(in[to])

            low[now]=min(low[now],dfn[to]);

    }

    if(low[now]==dfn[now]){

        int y; sum++;

        if(stk[top]!=now) is[sum]=1;

        do{

            y=stk[top--];

            v[sum].push_back(y);

            belong[y]=sum;

            in[y]=0;

        }while(y!=now);

    }

}

signed main(){

    n=getint(),m=getint();

    for(int i=1;i<=m;i++){

        int x=getint(),y=getint();

        add(y,x);

    }

    cnt=0;

    for(int i=1;i<=n+1;i++){

        if(!dfn[i])

            tarjan(i);

    }

    for(int x=1;x<=n+1;x++){

        for(int i=head[x];i;i=edge[i].nxt){

            int to=edge[i].to;

            if(belong[to]==belong[x]){

                is[belong[x]]=1;

                continue;

            }

            add2(belong[x],belong[to]);

            deg[belong[to]]++;

        }

    }

    std::queue<int> topo;

    for(int i=1;i<=sum;i++){

        if(!deg[i])

            topo.push(i);

    }

    dis[belong[n+1]]=1;

    while(topo.size()){

        int u=topo.front();topo.pop();

        if(is[u] and dis[u]) dis[u]=36501;

        for(int i=head2[u];i;i=edge2[i].nxt){

            int to=edge2[i].to;

            dis[to]=min(dis[to]+dis[u],36501);

            deg[to]--;

            if(!deg[to])

                topo.push(to);

        }

    }

    int ans=0;

    for(int i=1;i<=sum;i++){

        dis[i]=min(dis[i],36501);

        ans=max(ans,dis[i]);

    }

    if(ans==36501) printf("zawsze\n");

    else printf("%d\n",ans);

    for(int i=1;i<=n;i++){

        if(dis[belong[i]]==ans)

            print[++pos]=i;

    }

    printf("%d\n",pos);

    for(int i=1;i<=pos;i++)

        printf("%d ",print[i]);

    puts("");

    return 0;

}

巴特西

[POI2006] PRO-Professor Szu

Description

Solution

Code

最新文章

热门文章