生活随笔
收集整理的这篇文章主要介绍了
hdu6832（2020hdu多校6t6）
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
题解
所有最短路肯定都出现在最小生成树上。因为克鲁斯卡尔按顺序连边，前面已经连上的肯定最优，所有加起来比当前的还小。
这个我感觉求单源多汇最短路后的剩余图其实和最小生成树其实是一样的。因为如果最小生成树的结论是对的，那么源点到所有点的最短路一定都在树上，剩余图就是这个最小生成树。我试了试都是可以AC的。
开始初始化错了，少初始化了一堆东西，dfs停不下来，MLE。后来wa，因为枚举边端点dp计数没想清。
AC代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std
;
const int modd
=1e9+7;
const int oo
=1e9+10;
const int NN
=100100;
const int MM
=200100;
int n
,m
;
int vis
[NN
],dis
[NN
];
struct edge
{int to
,cost
,from
;
}e
[MM
*2];
vector
<int> con
[NN
];
int a
[NN
];
struct point
{int id
;long long d
;
};
struct point_cmp
{bool
operator() (const point
&x
,const point
&y
)const{if(x
.d
>y
.d
)return 1;if(x
.d
==y
.d
&& x
.id
>y
.id
)return 1;return 0;}
};
priority_queue
<point
,vector
<point
> , point_cmp
> q
;
int pre
[NN
];
void dij(int origin
){for(int i
=0;i
<=n
+1;i
++)dis
[i
]=oo
;dis
[origin
]=0;point st
;st
.id
=origin
;st
.d
=0;q
.push(st
);while(!q
.empty()){point root
=q
.top();q
.pop();if(dis
[root
.id
]!=root
.d
)continue;for(int i
=0;i
<con
[root
.id
].size();i
++){edge ed
=e
[con
[root
.id
][i
]];int nex
=ed
.to
;if(dis
[nex
]>max(dis
[root
.id
],ed
.cost
) ){pre
[nex
]=con
[root
.id
][i
];dis
[nex
]=max(dis
[root
.id
],ed
.cost
);point neww
;neww
.id
=nex
;neww
.d
=dis
[nex
];q
.push(neww
);}}}
}
long long siz
[NN
],sizfa
[NN
],numson1
[NN
],numfa1
[NN
],num1
;
int f
[MM
];
void dfs(int cur
,int fa
){int up
=con
[cur
].size();numson1
[cur
]=(a
[cur
]==1);siz
[cur
]=1;for(int i
=0;i
<up
;i
++){edge ed
=e
[con
[cur
][i
]];int nex
=ed
.to
;if(f
[con
[cur
][i
]]&&nex
!=fa
){dfs(nex
,cur
);siz
[cur
]+=siz
[nex
];numson1
[cur
]+=numson1
[nex
];}}
}
long long ans
=0;
long long quan
[MM
];
void dfsfa(int cur
,int fa
,int co
){int up
=con
[cur
].size();numfa1
[cur
]=num1
-numson1
[cur
];sizfa
[cur
]=n
-siz
[cur
];if(cur
!=1){ans
+=quan
[co
]*(1ll*numfa1
[cur
]*(siz
[cur
]-numson1
[cur
])%modd
+1ll*(sizfa
[cur
]-numfa1
[cur
])*numson1
[cur
]%modd
)%modd
;ans
%=modd
;}for(int i
=0;i
<up
;i
++){edge ed
=e
[con
[cur
][i
]];int nex
=ed
.to
;if(f
[con
[cur
][i
]]&&nex
!=fa
){dfsfa(nex
,cur
,ed
.cost
);}}
}
int fa
[NN
];
int getf(int x
){if(fa
[x
]==x
)return x
;return (fa
[x
]=getf(fa
[x
]));
}
int main(){quan
[0]=1;for(int i
=1;i
<=200000;i
++){quan
[i
]=(quan
[i
-1]<<1)%modd
;}int t
;scanf("%d",&t
);while(t
--){scanf("%d%d",&n
,&m
);if(n
==0)break;for(int i
=1;i
<=n
;i
++)con
[i
].clear(),fa
[i
]=i
;for(int i
=0;i
<=m
*2;i
++)f
[i
]=0;num1
=0;for(int i
=1;i
<=n
;i
++){scanf("%d",a
+i
);num1
+=(a
[i
]==1);}int nume
=-1;for(int i
=1;i
<=m
;i
++){int x
,y
;scanf("%d%d",&x
,&y
);e
[++nume
].to
=y
;e
[nume
].cost
=i
;e
[nume
].from
=x
;con
[x
].push_back(nume
);e
[++nume
].to
=x
;e
[nume
].cost
=i
;e
[nume
].from
=y
;con
[y
].push_back(nume
);}dij(1);for(int i
=1;i
<=n
;i
++){f
[pre
[i
]]=1;f
[pre
[i
]^1]=1;}dfs(1,-1);ans
=0;dfsfa(1,-1,0);printf("%lld\n",ans
);}return 0;
}
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std
;
const int modd
=1e9+7;
const int oo
=1e9+10;
const int NN
=100100;
const int MM
=200100;
int n
,m
;
struct edge
{int to
,cost
,from
;
}e
[MM
*2];
vector
<int> con
[NN
];
int a
[NN
];
long long siz
[NN
],sizfa
[NN
],numson1
[NN
],numfa1
[NN
],num1
;
int f
[MM
];
void dfs(int cur
,int fa
){int up
=con
[cur
].size();numson1
[cur
]=(a
[cur
]==1);siz
[cur
]=1;for(int i
=0;i
<up
;i
++){edge ed
=e
[con
[cur
][i
]];int nex
=ed
.to
;if(f
[con
[cur
][i
]]&&nex
!=fa
){dfs(nex
,cur
);siz
[cur
]+=siz
[nex
];numson1
[cur
]+=numson1
[nex
];}}
}
long long ans
=0;
long long quan
[MM
];
void dfsfa(int cur
,int fa
,int co
){int up
=con
[cur
].size();numfa1
[cur
]=num1
-numson1
[cur
];sizfa
[cur
]=n
-siz
[cur
];if(cur
!=1){ans
+=quan
[co
]*(1ll*numfa1
[cur
]*(siz
[cur
]-numson1
[cur
])%modd
+1ll*(sizfa
[cur
]-numfa1
[cur
])*numson1
[cur
]%modd
)%modd
;ans
%=modd
;}for(int i
=0;i
<up
;i
++){edge ed
=e
[con
[cur
][i
]];int nex
=ed
.to
;if(f
[con
[cur
][i
]]&&nex
!=fa
){dfsfa(nex
,cur
,ed
.cost
);}}
}
int fa
[NN
];
int getf(int x
){if(fa
[x
]==x
)return x
;return (fa
[x
]=getf(fa
[x
]));
}
int main(){quan
[0]=1;for(int i
=1;i
<=200000;i
++){quan
[i
]=(quan
[i
-1]<<1)%modd
;}int t
;scanf("%d",&t
);while(t
--){scanf("%d%d",&n
,&m
);if(n
==0)break;for(int i
=1;i
<=n
;i
++)con
[i
].clear(),fa
[i
]=i
;for(int i
=0;i
<=m
*2;i
++)f
[i
]=0;num1
=0;for(int i
=1;i
<=n
;i
++){scanf("%d",a
+i
);num1
+=(a
[i
]==1);}int nume
=-1;for(int i
=1;i
<=m
;i
++){int x
,y
;scanf("%d%d",&x
,&y
);e
[++nume
].to
=y
;e
[nume
].cost
=i
;e
[nume
].from
=x
;con
[x
].push_back(nume
);e
[++nume
].to
=x
;e
[nume
].cost
=i
;e
[nume
].from
=y
;con
[y
].push_back(nume
);}for(int i
=0;i
<=nume
;i
+=2){int fx
=getf(e
[i
].from
);int fy
=getf(e
[i
].to
);if(fx
!=fy
){fa
[fx
]=fy
;f
[i
]=1;f
[i
^1]=1;}}dfs(1,-1);ans
=0;dfsfa(1,-1,0);printf("%lld\n",ans
);}return 0;
}
总结
以上是生活随笔为你收集整理的hdu6832（2020hdu多校6t6）的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
