• 周日. 11月 27th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

暑假集训Day18 K (反图+dfs剪枝)

admin

11月 28, 2021

题目链接在这里:Problem – K – Codeforces

此题主要学习的一个思想就是建反图,当需要研究的路径最终都汇聚到t点的时候,为了搜索的方便,我们可以考虑建立反图来研究,这样搜索的起点就由多个点变成了一个点t

然后这个题坑了半天的地方就是搜索剪枝的时候一定是先判断vis[x]>1再vis[x]++;

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 const int MAX=1e5+5;
 4 int n,m,s;
 5 int tot,head[MAX],adj[MAX],nxt[MAX];
 6 int vis[MAX],ss[MAX],ans[MAX];
 7 bool vv[MAX];
 8 void addedge(int u,int v){
 9     tot++;
10     adj[tot]=v;
11     nxt[tot]=head[u];
12     head[u]=tot;
13 }
14 void dfs(int x){
15     vv[x]=true;
16     int i,j;
17     if (vis[x]>=2) return;
18     vis[x]++;
19     //cout<<x<<' ';
20     for (i=head[x];i;i=nxt[i]){
21         if (vv[adj[i]] || adj[i]==s) continue;
22         dfs(adj[i]);
23     }
24 }
25 int main(){
26     int i,j,u,v;
27     scanf("%d%d%d",&n,&m,&s);s++;
28     ss[0]=0;
29     for (i=1;i<=m;i++){
30         scanf("%d%d",&u,&v);u++,v++;
31         if (v==s) ss[++ss[0]]=u;
32         addedge(v,u);
33     }//cout<<ss[0]<<endl;
34     memset(vis,0,sizeof(vis));
35     for (i=1;i<=ss[0];i++){
36         for (j=1;j<=n;j++) vv[j]=false;
37         dfs(ss[i]);//cout<<endl;
38     }
39     for (i=1;i<=ss[0];i++)
40         if (vis[ss[i]]<=1) ans[++ans[0]]=ss[i];
41     sort(ans+1,ans+ans[0]+1);
42     printf("%d
",ans[0]);
43     for (i=1;i<=ans[0];i++) printf("%d
",ans[i]-1);
44     return 0;
45 }
未来是什么样,未来会发生什么,谁也不知道。
但是我知道,
起码从今天开始努力,
肯定比从明天开始努力,
要快一天实现梦想。
千里之行,始于足下! ——《那年那兔那些事儿》

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注