题目大意：https://www.cnblogs.com/Juve/articles/11220105.html
那是寒假里的一天，我们......行啦，不要脑补画面了，我们来正经的题解
我们发现我们可以把与1号节点相连的所有节点取出,如果我们把最小环在1号节点处断开,那么最小环断成的链一定是以这些节点中的某一个节点作为起点,另一个节点作为终点的一条路路径。
如果不考虑时间复杂度,我们完全可以枚举作为起点的节点,每次都跑一遍最短路来更新答案。
但是上面的做法肯定会爆炸,所以我们考虑如何降低复杂度。
我们考虑把所有的节点分为两组,一组中的所有点作为起点,另一组中的所有点作为终点,一起跑最短路,更新答案。
如此我们发现只要我们能够保证真正贡献答案的一对节点会在某一次分组当中被分到不同组,我们就可以保证算法的正确性。
因为起点与终点的编号肯定不相同,于是我们可以按照二进制分组,枚举每个二进制位,按照当前二进制位的0/1情况来进行分组。
我看好像没有人用这种方法的，其实dij就可以过，用dij求1号节点开始的最小环
别告诉我你不会求最小环。
我们枚举1号点连接的每一条边，先把这条边权变成0x3f3f3f3f，跑dij，更新答案：ans=min(dis[to[i]]+w[i]);
就是在把fr[i]和to[i]间的边断开后两点间的最短路加上原来两点间的距离取最小值
原来博主想用tarjan求边双，然后在1号节点所在的边双中跑dij，但时间并没有下去
还有注意给边编号从2开始，这样i和i^1是一对双向边
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#define ll long long#define MAXN 10005#define MAXM 40005using namespace std;ll t,n,m,ans=0x3f3f3f3f;ll pre[MAXN],tot_e=1,to[MAXM<<1],nxt[MAXM<<1],w[MAXM<<1];voID add(ll u,ll v,ll d){ tot_e++,to[tot_e]=v,nxt[tot_e]=pre[u],pre[u]=tot_e,w[tot_e]=d;}ll dis[MAXN];priority_queue< pair<ll,ll> > q;bool visit[MAXN];voID dijkstra(ll x){ memset(dis,0x3f,sizeof(dis)); dis[x]=0; memset(visit,sizeof(visit)); q.push(make_pair(-dis[x],x)); while(!q.empty()){ ll y=q.top().second;q.pop(); if(visit[y]) continue; visit[y]=1; for(ll i=pre[y];i;i=nxt[i]){ ll v=to[i],z=w[i]; if(dis[v]>dis[y]+z){ dis[v]=dis[y]+z; q.push(make_pair(-dis[v],v)); } } }}int main(){ scanf("%lld",&t); while(t--){ scanf("%lld%lld",&n,&m); for(ll i=1,u,v,d;i<=m;i++){ scanf("%lld%lld%lld",&u,&v,&d); add(u,d),add(v,d); } for(ll i=pre[1];i;i=nxt[i]){ ll temp=w[i]; w[i]=w[i^1]=0x3f3f3f3f; dijkstra(1); ans=min(ans,dis[to[i]]+temp); w[i]=w[i^1]=temp; } if(ans==0x3f3f3f3f) ans=-1; printf("%lld\n",ans); ans=0x3f3f3f3f; tot_e=1; memset(pre,sizeof(pre)); } return 0;}
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #define ll long long 6 #define MAXN 10005 7 #define MAXM 40005 8 using namespace@H_419_113@ std; 9 ll t,ans=0x3f3f3f3f@H_419_113@; 10 ll pre[MAXN],tot_e=1,to[MAXM<<1],nxt[MAXM<<1],w[MAXM<<1@H_419_113@]; 11 voID@H_419_113@ add(ll u,ll d){ 12 tot_e++,w[tot_e]=@H_419_113@d; 13 @H_419_113@} 14 bool vis[MAXM<<1@H_419_113@]; 15 voID@H_419_113@ dfs(ll x,ll res){ 16 if(res>ans) return@H_419_113@ ; 17 if(x==1@H_419_113@){ 18 if(res!=0@H_419_113@){ 19 ans=@H_419_113@min(ans,res); 20 return@H_419_113@ ; 21 @H_419_113@ } 22 @H_419_113@ } 23 for(ll i=pre[x];i;i=@H_419_113@nxt[i]){ 24 if(!@H_419_113@vis[i]){ 25 vis[i]=1,vis[i^1]=1@H_419_113@; 26 dfs(to[i],res+@H_419_113@w[i]); 27 vis[i]=0,vis[i^1]=0@H_419_113@; 28 @H_419_113@ } 29 @H_419_113@ } 30 @H_419_113@} 31 ll dfn[MAXN],low[MAXN],dfs_order=0@H_419_113@; 32 bool is_brIDge[MAXM<<1@H_419_113@]; 33 voID@H_419_113@ tarjan(ll x,ll in_edge){ 34 dfn[x]=low[x]=++@H_419_113@dfs_order; 35 for(ll i=pre[x];i;i=@H_419_113@nxt[i]){ 36 ll y=@H_419_113@to[i]; 37 if(!@H_419_113@dfn[y]){ 38 @H_419_113@ tarjan(y,i); 39 low[x]=@H_419_113@min(low[x],low[y]); 40 if(low[y]>@H_419_113@low[x]) 41 is_brIDge[i]=is_brIDge[i^1]=1@H_419_113@; 42 @H_419_113@ } 43 else if(i!=(in_edge^1@H_419_113@)) 44 low[x]=@H_419_113@min(low[x],dfn[y]); 45 @H_419_113@ } 46 @H_419_113@} 47 bool@H_419_113@ belong[MAXN]; 48 voID DFS(int@H_419_113@ x){ 49 belong[x]=1@H_419_113@; 50 for(int i=pre[x];i;i=@H_419_113@nxt[i]){ 51 int y=@H_419_113@to[i]; 52 if(belong[y]||is_brIDge[i]) continue@H_419_113@; 53 @H_419_113@ DFS(y); 54 @H_419_113@ } 55 @H_419_113@} 56 @H_419_113@ll dis[MAXN]; 57 priority_queue< pair<ll,ll> >@H_419_113@ q; 58 bool@H_419_113@ visit[MAXN]; 59 voID@H_419_113@ dijkstra(ll x){ 60 memset(dis,0x3f,sizeof@H_419_113@(dis)); 61 dis[x]=0@H_419_113@; 62 memset(visit,0,sizeof@H_419_113@(visit)); 63 q.push(make_pair(-@H_419_113@dis[x],x)); 64 while(!@[email protected]()){ 65 ll y=@[email protected]().second;q.pop(); 66 if(visit[y]) continue@H_419_113@; 67 visit[y]=1@H_419_113@; 68 for(ll i=pre[y];i;i=@H_419_113@nxt[i]){ 69 ll v=to[i],z=@H_419_113@w[i]; 70 if(dis[v]>dis[y]+@H_419_113@z){ 71 dis[v]=dis[y]+@H_419_113@z; 72 q.push(make_pair(-@H_419_113@dis[v],v)); 73 @H_419_113@ } 74 @H_419_113@ } 75 @H_419_113@ } 76 @H_419_113@} 77 int@H_419_113@ main(){ 78 scanf("%lld",&@H_419_113@t); 79 while(t--@H_419_113@){ 80 scanf("%lld%lld",&@H_419_113@m); 81 if(n==@H_419_113@m){ 82 for(ll i=1,d;i<=m;i++@H_419_113@){ 83 scanf("%lld%lld%lld",&@H_419_113@d); 84 @H_419_113@ add(u,d); 85 @H_419_113@ } 86 dfs(1,0@H_419_113@); 87 if(ans==0x3f3f3f3f) ans=-1@H_419_113@; 88 printf("%lld\n"@H_419_113@,ans); 89 ans=0x3f3f3f3f@H_419_113@; 90 memset(pre,sizeof@H_419_113@(pre)); 91 tot_e=1@H_419_113@; 92 }else@H_419_113@{ 93 for(ll i=1,d;i<=m;i++@H_419_113@){ 94 scanf("%lld%lld%lld",&@H_419_113@d); 95 @H_419_113@ add(u,d); 96 @H_419_113@ } 97 for(ll i=1;i<=n;i++@H_419_113@){ 98 if(!dfn[i]) tarjan(i,0@H_419_113@); 99 @H_419_113@ }100 DFS(1@H_419_113@);101 for(ll i=pre[1];i;i=@H_419_113@nxt[i]){102 if(is_brIDge[i]||!belong[to[i]]) continue@H_419_113@;103 ll temp=@H_419_113@w[i];104 w[i]=w[i^1]=0x3f3f3f3f@H_419_113@;105 dijkstra(1@H_419_113@);106 ans=min(ans,dis[to[i]]+@H_419_113@temp);107 w[i]=w[i^1]=@H_419_113@temp;108 @H_419_113@ }109 if(ans==0x3f3f3f3f) ans=-1@H_419_113@;110 printf("%lld\n"@H_419_113@,ans);111 ans=0x3f3f3f3f@H_419_113@;112 tot_e=1,dfs_order=0@H_419_113@;113 memset(pre,sizeof@H_419_113@(pre));114 memset(dfn,sizeof@H_419_113@(dfn));115 memset(is_brIDge,sizeof@H_419_113@(is_brIDge));116 @H_419_113@ }117 @H_419_113@ }118 return 0@H_419_113@;119 }tarjan的复杂算法 总结
以上是内存溢出为你收集整理的HZOI2019 B. 那一天她离我而去 最小环全部内容，希望文章能够帮你解决HZOI2019 B. 那一天她离我而去 最小环所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）