2023NOIP A层联测9-紫罗兰

题目链接

在输入过程中对于一条边的两个点 $x,y$，从 $x$ 做 $BFS$，记录每一个点到 $x$ 的最短路程 $di{s}_x$。显然，最后 $di{s}_y+1$ 就是经过 $x$ 的当前最小环长度。

在这个过程中同时求方案数。
令 $f_x=1$；
当前遍历到点 $u$，先对它的所有邻接点 $nxt$ 更新 $dis$；（因为走的路径不是最短路，方案是无效的）
如果 $di{s}_{nxt}=di{s}_u+1$，则 $f_{nxt}\leftarrow f_{nxt}+f_x$。（走了最短路径）
$BFS$ 做完后，$f_y$ 就是经过 $x$ 的最小环个数，对每个 $f_y$ 求和就是答案。

对于上面的一个过程，可以简单理解成：把图转换为一个 $DAG$（去掉了 $dis$ 值不连续的边），在上面做拓扑排序，求了方案数。

如果 $di{s}_y+1<num$，就是最小环的长度可以被更新，那么前面求的答案都无效了，将其清零。

#include
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,num=1e9,dis[3001],f[3001],ans;
int head[3001],nxt[12001],to[12001],cnt;
vector<int> v;
void add(int u,int v)
{
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
void bfs(int st)
{
    queue<int> q;
    memset(dis,0x3f,sizeof(dis));
    memset(f,0,sizeof(f));
    dis[st]=0;
    f[st]=1;
    q.push(st);
    while(q.size()){
        int k=q.front();
        q.pop();
        for(int i=head[k];i;i=nxt[i]){
            if(dis[to[i]]>dis[k]+1){
                q.push(to[i]);
                dis[to[i]]=dis[k]+1;
            }
            if(dis[to[i]]==dis[k]+1){
                f[to[i]]+=f[k];
            }
        }
    }
}
int main()
{
    freopen("B.in","r",stdin);
    freopen("B.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        bfs(x);
        if(dis[y]<num) num=dis[y],ans=0;
        if(dis[y]==num) ans+=f[y];
        add(x,y),add(y,x);
    }
    cout<<ans;
}
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