题解 P3436 【[POI2006]PRO-Professor Szu】

2017-10-02 16:56:38


【POI补全计划#20 POI2006 PRO】

首先为了方便,把“从别墅走到主建筑楼”视为“从主建筑楼走到别墅”,然后把所有边反向(为了方便dfs),这样对题目答案没有影响

接下来记录主建筑能走到那些建筑,把走不到的建筑(和它们的出边)从图中去掉

然后在能走到的建筑中记录每个点的入度(不包含从“走不到的建筑”连向“能走道的建筑”的边),进行拓扑排序

在拓扑排序的过程中记录方案数,如果排到一半发现没有待处理的,入度为0的点时说明剩下的点中存在环,可以有无限种方案走向剩余的点

在记录方案的过程中如果遇到方案数>36500的点则设为一个固定的,略大于36500的数,防止爆int

最后输出一下方案就好了,注意无限种方案和方案数>36500的点都需要输出

贴代码:

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=1000010;
struct edge
{
    int v;
    edge *next;
}*h[MAXN],pool[MAXN];
int deg[MAXN],top,cnt;
inline void addedge(int v,int u)
{
    edge *tmp=&pool[++top];tmp->v=v;tmp->next=h[u];h[u]=tmp;deg[v]++;
}
int dp[MAXN],vis[MAXN];
vector<int> ans;
void dfs(int u)
{
    vis[u]=1;cnt++;
    for(edge *tmp=h[u];tmp;tmp=tmp->next)
    {
        if(!vis[tmp->v])dfs(tmp->v);
    }
}
queue<int> q;
int main()
{
    int n,m,a,b;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        addedge(a,b);
    }
    dfs(n+1);
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            for(edge *tmp=h[i];tmp;tmp=tmp->next)
            {
                deg[tmp->v]--;
            }
        }
    }
    q.push(n+1);
    dp[n+1]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        cnt--;vis[u]=0;
        for(edge *tmp=h[u];tmp;tmp=tmp->next)
        {
            dp[tmp->v]+=dp[u];
            deg[tmp->v]--;
            if(deg[tmp->v]==0)
            {
                if(dp[tmp->v]>36500)
                {
                    dp[tmp->v]=36501;
                    ans.push_back(tmp->v);
                    cnt++;
                }
                q.push(tmp->v);
            }
        }
    }
    if(cnt==0)
    {
        int maxx=0;
        for(int i=1;i<=n;i++)
        {
            if(dp[i]>maxx)
            {
                maxx=dp[i];
                ans.clear();
                ans.push_back(i);
            }
            else if(dp[i]==maxx)ans.push_back(i);
        }
        sort(ans.begin(),ans.end());
        printf("%d\n%d\n",maxx,ans.size());
        for(auto x:ans)printf("%d ",x);
        return 0;
    }
    for(int i=1;i<=n;i++)if(vis[i])ans.push_back(i);
    sort(ans.begin(),ans.end());
    printf("zawsze\n%d\n",ans.size());
    for(auto x:ans)printf("%d ",x);
    return 0;
}