首页 > 代码库 > hdu 5876 (补图BFS) Sparse Graph
hdu 5876 (补图BFS) Sparse Graph
题目：这里
题意：
相当于一开始给一个初始好了的无向完全图给你，然后给让你删除m条边，再给你一个点v，最后问你在剩下的图里从这个点v出发能到达所有边点的最小路径是多少？
一看是所有点的最小路径，一看就觉得是个bfs，记忆化搜一下然后加个优化什么的，由于数据不知道是个什么奇葩而且比赛中还改数据，所以很多人wa的莫名其妙，
过也过的莫名其妙，我虽然过了但觉得有点不靠谱，赛后看了https://async.icpc-camp.org/d/546-2016的题解思路写了一发，总感觉更靠谱一点。
之前自己过的，就是用set记录那删掉的m条边，dis[i]数组记录每个结点的最小路径，当所有的点都搜到过的时候就可以结束了
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<set> 6 #include<queue> 7 using namespace std; 8 9 const int M = 2e5 + 10;10 set<int>s[M];11 int n;bool vis[M];12 int dis[M],ans;13 14 int min(int x,int y){return x<y?x:y;}15 16 struct node{17 int po,dis;18 };19 20 void bfs(int pos)21 {22 memset(vis,false,sizeof(vis));23 queue<node>p;24 node now,next;25 now.po=pos;now.dis=0;26 p.push(now);27 vis[pos]=true;28 while (!p.empty()){29 now=p.front();30 p.pop();31 for (int i=1 ; i<=n ; i++){32 next.po=i;next.dis=now.dis+1;33 if (next.po==now.po) continue;34 if (vis[next.po]) continue;35 bool flag=false;36 if (s[now.po].find(next.po)!=s[now.po].end())37 flag=true;38 if (flag) continue;39 vis[next.po]=true;40 dis[next.po]=min(next.dis,dis[next.po]);41 p.push(next);ans++;42 }43 if (ans==n) return ;44 }45 }46 47 48 49 int main()50 {51 int t;52 scanf("%d",&t);53 while (t--){54 int m;55 scanf("%d%d",&n,&m);56 for (int i=1 ; i<=n ; i++) s[i].clear(),dis[i]=M;57 while (m--){58 int u,v;59 scanf("%d%d",&u,&v);60 s[u].insert(v);61 s[v].insert(u);62 }63 int pos;64 scanf("%d",&pos);65 ans=1;66 bfs(pos);67 if (n!=pos){68 for (int i=1 ; i<=n ; i++){69 if (i==pos) continue;70 if (i!=n) printf("%d ",dis[i]);71 else printf("%d\n",dis[i]);72 }73 }74 else{75 for (int i=1 ; i<n ; i++){76 if (i!=n-1) printf("%d ",dis[i]);77 else printf("%d\n",dis[i]);78 }79 }80 }81 return 0;82 }
后来看了别人的思路自己写的
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<set>#include<queue>using namespace std;const int M = 2e5 + 10;int n,di[M],head[M],cas;struct Edge{ int to,next;}edge[M*2];void add(int u,int v){ edge[++cas].next=head[u]; edge[cas].to=v; head[u]=cas;}int min(int x,int y){return x<y?x:y;}struct node{ int po,dis;};void bfs(int pos){ set<int>s,e; set<int>::iterator it; for (int i=1 ; i<=n ; i++) s.insert(i),di[i]=M; queue<node>p; s.erase(pos); node now,next; now.po=pos;now.dis=0; p.push(now); while (!p.empty()){ now=p.front(); p.pop(); for (int i=head[now.po] ; i ; i=edge[i].next){ int v=edge[i].to; if (s.find(v)==s.end()) continue; s.erase(v); e.insert(v); } for (it=s.begin() ; it!=s.end() ; it++){ next.po=*it;next.dis=now.dis+1; di[next.po]=min(next.dis,di[next.po]); p.push(next); } s.swap(e);e.clear(); }}int main(){ int t; scanf("%d",&t); while (t--){ int m;cas=0; scanf("%d%d",&n,&m); memset(head,0,sizeof(head)); while (m--){ int u,v; scanf("%d%d",&u,&v); add(u,v);add(v,u); } int pos; scanf("%d",&pos); bfs(pos); if (n!=pos){ for (int i=1 ; i<=n ; i++){ if (i==pos) continue; if (i!=n) printf("%d ",di[i]); else printf("%d\n",di[i]); } } else{ for (int i=1 ; i<n ; i++){ if (i!=n-1) printf("%d ",di[i]); else printf("%d\n",di[i]); } } } return 0;}
hdu 5876 (补图BFS) Sparse Graph
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。