首页 > 代码库 > hdu 3072 有向图缩点成最小树形图计算最小权
hdu 3072 有向图缩点成最小树形图计算最小权
题意,从0点出发,遍历所有点,遍历边时候要付出代价,在一个SCC中的边不要付费。求最小费用。
有向图缩点(无需建立新图,,n《=50000,建则超时),遍历边,若不在一个SCC中,用一个数组更新记录最小到达该连通分量的最小边权即可。。。边聊天,边1A,哈哈。。。
#include<iostream> #include<stack> #include<queue> #include<cstdio> #include<cstring> using namespace std; const int inf=0x3f3f3f3f; const int maxv=50005,maxe=100005; int nume=0;int head[maxv];int e[maxe][3]; void inline adde(int i,int j,int c) { e[nume][0]=j;e[nume][1]=head[i];head[i]=nume; e[nume++][2]=c; } int dfn[maxv];int low[maxv];int vis[maxv];int ins[maxv]; stack<int>sta; int scc[maxv];int numb=0;int times=0; int n,m; void tarjan(int u) { dfn[u]=low[u]=times++; ins[u]=1; sta.push(u); for(int i=head[u];i!=-1;i=e[i][1]) { int v=e[i][0]; if(!vis[v]) { vis[v]=1; tarjan(v); if(low[v]<low[u])low[u]=low[v]; } else if(ins[v]&&dfn[v]<low[u]) { low[u]=dfn[v]; } } if(low[u]==dfn[u]) { numb++; int cur; do { cur=sta.top(); sta.pop(); ins[cur]=0; scc[cur]=numb; }while(cur!=u); } } int mincost_to_v[maxv]; //记录 void solve() { vis[0]=1; tarjan(0); for(int i=0;i<n;i++) for(int j=head[i];j!=-1;j=e[j][1]) { int v=e[j][0]; if(scc[i]!=scc[v]) { if(e[j][2]<mincost_to_v[scc[v]]) { mincost_to_v[scc[v]]=e[j][2]; } } } int sums=0; for(int i=1;i<=numb;i++) { if(mincost_to_v[i]!=inf) //起点 sums+=mincost_to_v[i]; } printf("%d\n",sums); } void read_build() { int aa,bb,cc; for(int i=0;i<m;i++) { scanf("%d%d%d",&aa,&bb,&cc); adde(aa,bb,cc); } } void init() { numb=times=nume=0; for(int i=0;i<maxv;i++) { head[i]=-1; ins[i]=dfn[i]=low[i]=scc[i]=vis[i]=0; mincost_to_v[i]=inf; } } int main() { while(~scanf("%d%d",&n,&m)) { init(); read_build(); solve(); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。