[Usaco2015 Jan]Grass Cownoisseur

发表于 | 分类于

题目大意

给一个有向图，然后选一条路径起点终点都为1的路径出来，有一次机会可以沿某条边逆方向走，问最多有多少个点可以被经过？
（一个点在路径中无论出现多少正整数次对答案的贡献均为1）

INPUT

The first line of input contains N and M, giving the number of fields and the number of one-way paths (1 <= N, M <= 100,000). The following M lines each describe a one-way cow path. Each line contains two distinct field numbers X and Y, corresponding to a cow path from X to Y. The same cow path will never appear more than once.
N个点，M条有向边，无重边

OUTPUT

A single line indicating the maximum number of distinct fields Bessie
can visit along a route starting and ending at field 1, given that she can
follow at most one path along this route in the wrong direction.

SAMPLE

INPUT

7 10
1 2
3 1
2 5
2 4
3 7
3 5
3 6
6 5
7 2
4 7

OUTPUT

6

解题报告

这道题考试的时候，一看就知道是tarjan，然后就真的傻傻的打了个tarjan+dfs，就A了一个点= =
正解：
tarjan缩点，因为可以逆转一条边，而同一强连通分量里的边逆转是没啥用的，所以我们可以枚举缩点后的边。
首先，跑2遍SPFA，一遍缩点后的正边，一遍反边，处理出正反两个最大的经过权值（每点权值为缩点后强连通分量的点数）。
剩下的就很简单了，思考当一条有向边反过来时，它反边的起点走的是正向的最大权值，而终点则走的是反向的最大权值，那么我们枚举每一条边，两权相加求max即为答案。
注意：特判，两边SPFA若有一遍没有联通这条边对应的强连通分量，这个点就不能跑。

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
    int sum(0);
    char ch(getchar());
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9'){
        sum=sum*10+ch-'0';
        ch=getchar();
    }
    return sum;
}
struct edge{
    int s,e,n;
}k[100001],a[100001],b[100001];
int pre[100001],tot;
inline void insert(int s,int e){
    k[++tot].s=s;
    k[tot].e=e;
    k[tot].n=pre[s];
    pre[s]=tot;
}
int low[100001],dfn[100001],stack[100001],bl[100001],size[100001];
int head,cnt,qlt;
bool vis[100001];
inline int my_min(int a,int b){
    return a<b?a:b;
}
inline int my_max(int a,int b){
    return a>b?a:b;
}
inline void tarjan(int u){
    low[u]=dfn[u]=++cnt;
    vis[u]=1;
    stack[++head]=u;
    for(int i=pre[u];i!=-1;i=k[i].n){
        int e(k[i].e);
        if(!dfn[e]){
            tarjan(e);
            low[u]=my_min(low[u],low[e]);
        }
        else
            if(vis[e])
                low[u]=my_min(low[u],dfn[e]);
    }
    if(low[u]==dfn[u]){
        int tmp;
        qlt++;
        while(1){
            tmp=stack[head--];
            bl[tmp]=qlt;
            vis[tmp]=0;
            if(tmp==u)
                break;
        }
    }
}
int adj[100001],num;
inline void add(int s,int e){
    a[++num].s=s;
    a[num].e=e;
    a[num].n=adj[s];
    adj[s]=num;
}
queue<int>q;
int fz[100001];
inline void spfa1(int x){
    memset(vis,0,sizeof(vis));
    memset(fz,0,sizeof(fz));
    q.push(x);
    fz[x]=size[x];
    vis[x]=1;
    while(!q.empty()){
        int k(q.front());
        q.pop();
        for(int i=adj[k];i!=-1;i=a[i].n){
            int e(a[i].e);
            if(fz[e]<fz[k]+size[e]){
                fz[e]=fz[k]+size[e];
                if(!vis[e]){
                    q.push(e);
                    vis[e]=1;
                }
            }
        }
        vis[k]=0;
    }
}
int hhh,nxt[100001];
inline void init(int s,int e){
    b[++hhh].s=s;
    b[hhh].e=e;
    b[hhh].n=nxt[s];
    nxt[s]=hhh;
}
int ff[100001];
inline void spfa2(int x){
    memset(vis,0,sizeof(vis));
    memset(ff,0,sizeof(ff));
    q.push(x);
    ff[x]=size[x];
    vis[x]=1;
    while(!q.empty()){
        int k(q.front());
        q.pop();
        for(int i=nxt[k];i!=-1;i=b[i].n){
            int e(b[i].e);
            if(ff[e]<ff[k]+size[e]){
                ff[e]=ff[k]+size[e];
                if(!vis[e]){
                    q.push(e);
                    vis[e]=1;
                }
            }
        }
        vis[k]=0;
    }
}
inline int find(int x){
    int s(a[x].e),e(a[x].s);
    if(!fz[s]||!ff[e])
        return 0;
    return fz[s]+ff[e]-size[bl[1]];
}
int n,m;
int main(){
    memset(pre,-1,sizeof(pre));
    memset(adj,-1,sizeof(adj));
    memset(nxt,-1,sizeof(nxt));
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int x(read()),y(read());
        insert(x,y);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=n;i++)
        size[bl[i]]++;
    for(int i=1;i<=tot;i++){
        int s(k[i].s),e(k[i].e);
        if(bl[s]!=bl[e])
            add(bl[s],bl[e]),init(bl[e],bl[s]);
    }
    spfa1(bl[1]);
    spfa2(bl[1]);
    int ans(0);
    for(int i=1;i<=num;i++)
        ans=my_max(ans,find(i));
    printf("%d\n",ans);
}

ps:调了我两个小时，最后发现重新建边的时候我用的原来点的编号，没有用缩完点后的编号，然后就听取蛙声一片了= =