bzoj1512 PRO-Professor Szu

发表于 | 分类于

题目描述

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

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

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

输入输出格式

输入格式：

第1行，两个正整数，n和m（n<=100000,m<=1000000）

第2至m+1行，两个正整数u和v，代表存在一条u通向v的道路

输出格式：

第1行，一个正整数，代表最多的不同到达主建筑楼方式。

第2行，一个正整数，代表有多少个别墅有这么多方式。

第3行，k个正整数，代表拥有最多达到主建筑楼方式的城市编号。

输入输出样例：

样例输入：
3 5
1 2
1 3
2 3
3 4
3 4
样例输出：
4
1
1

分析

我是有多蠢才会想到用SPFAdp
正解是先用Tarjian缩点重新建图
再用拓扑dp
碰到由终点到达环直接赋为最大值

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
const int inf=36501;
stack<int>st;
vector<int>g[210101];
int n,m,num,top,doe;
int pre[1010101],now[210101],son[1010101];
int id[210101],dfn[210101],fid[210101];
int du[210101],size[210101];
int que[510101],f[210101],ans[210101];
bool self[210101];
inline void read(int &x)
{
    int data=0,w=1;
    char ch=0;
    while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if (ch=='-') w=-1,ch=getchar();
    while (ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^'0'),ch=getchar();
    x=data*w;
}
void add(int x,int y)
{
    ++doe;
    pre[doe]=now[x];
    now[x]=doe;
    son[doe]=y;
}
void tarjian(int x)
{
    ++top;
    dfn[x]=fid[x]=top;
    st.push(x);
    int p=now[x];
    while (p)
    {
        int y=son[p];
        if (!dfn[y])
        {
            tarjian(y);
            fid[x]=min(fid[x],fid[y]);
        }
        else if (!id[y])
            fid[x]=min(fid[x],dfn[y]);
            
        p=pre[p];    
    }
    
    if (fid[x]==dfn[x])
    {
        ++num;
        int t;
        while (1)
        {
            t=st.top();
            st.pop();
            id[t]=num;
            ++size[num];
            if (t==x) break;
        }
    }
}
int main()
{
    read(n); read(m);
    ++n;
    int xx,yy;
    for (int i=1;i<=m;++i)
    {
        read(xx); read(yy);
        if (xx==yy) self[xx]=1;
        add(yy,xx);
    }
    for (int i=1;i<=n;++i)
        if (!dfn[i]) tarjian(i);
    for (int i=1;i<=n;++i)
        if (self[i]) ++size[id[i]];        //自环特殊处理 
    for (int i=1;i<=n;++i)
    {
        int p=now[i];
        while (p)
        {
            int y=son[p];
            if (id[i]!=id[y])
            {
                g[id[i]].push_back(id[y]);
                ++du[id[y]];    //拓扑入度 
            }
            p=pre[p];
        }
    }
    
    int head=1,tail=0;
    for (int i=1;i<=num;++i)
        if (du[i]==0) que[++tail]=i;    //开始只想将n加在队首，后来想起这样的话不符合拓扑，所以后面的dp加了特判 
    f[id[n]]=1;
    
    while (head<=tail)
    {
        int x=que[head];
        for (int i=0;i<g[x].size();++i)
        {
            int y=g[x][i];
            f[y]+=f[x];
            if (f[y]>inf || (size[y]>1 && f[y]) ) f[y]=inf;        //在环中的并且可以由终点到此点的也赋inf 
            if (--du[y]==0)
            {
                ++tail;
                que[tail]=y;
            }
        }
        ++head;
    }
    int maxn=-1;
    for (int i=1;i<=num;++i)
        maxn=max(maxn,f[i]);
    if (maxn==inf) printf("zawsze\n");
    else printf("%d\n",maxn);
    
    int k=0;
    for (int i=1;i<=n;++i)
        if (f[id[i]]==maxn) 
            ans[++k]=i;
    printf("%d\n",k);
    printf("%d",ans[1]);
    for (int i=2;i<=k;++i)
        printf(" %d",ans[i]);
    printf("\n");
    return 0;
}
--------------------------