题目链接: hdu 3072
题目大意: 给定有权值有向图,并且题意满足缩点之后只有一个入度为0的点
从该点出发,传递到所有的顶点的最小权值
联通分量内的点之间互相传递且不需要计算权值
解题思路: 缩点后的是DAG,并且唯一入度为0的顶点
顶点入度的边至少存在一条,记录每个顶点入度边权值最小的
顶点的入度边另外一点必定是图中的顶点
取权值最小的边依然可以起点出发能遍历完所有的顶点
代码(Tarjan):
//Final Tarjan强联通分量+缩点 #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 50100 #define INF 0x3f3f3f #define Min(a,b) a<b?a:b struct snode{ int to,w,next; }edge[MAX*20],edge2[MAX*20]; int n,high,numn,Index,num[MAX],pre[MAX],dnf[MAX],low[MAX],visit[MAX]; int Stack[MAX<<3],father[MAX],pre2[MAX],Index2,Top; void Add_edge(int a,int b,int w) { edge[Index].to=b,edge[Index].next=pre[a]; edge[Index].w=w,pre[a]=Index++; } void Tarjan(int u) //Tarjan搜索强联通分量,不需要father { int i,j,v; visit[u]=1; //*** Stack[Top++]=u; for(i=pre[u];i!=-1;i=edge[i].next) { v=edge[i].to; if(!dnf[v]) { dnf[v]=low[v]=++high; Tarjan(v); low[u]=Min(low[u],low[v]); } else if(visit[v]) //***不需要father low[u]=Min(low[u],dnf[v]); } if(low[u]==dnf[u]) //dnf[u]==low[u]则是强联通分量 { numn++; do { if(Top<=0) break; j=Stack[--Top]; visit[j]=0; //*** father[j]=numn; }while(j!=u); } } int main() { int m,i,j,a,b,c; while(scanf("%d%d",&n,&m)!=EOF) { Index=Index2=high=numn=Top=0; memset(dnf,0,sizeof(dnf)); memset(pre,-1,sizeof(pre)); memset(num,INF,sizeof(num)); memset(pre2,-1,sizeof(pre2)); memset(visit,0,sizeof(visit)); memset(father,0,sizeof(father)); for(i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); Add_edge(a+1,b+1,c); } for(i=1;i<=n;i++) //Tarjan搜索强联通分量 { if(!dnf[i]) Tarjan(i); } for(i=1;i<=n;i++) { for(j=pre[i];j!=-1;j=edge[j].next) { if(father[i]!=father[edge[j].to]&&num[father[edge[j].to]]>edge[j].w) { num[father[edge[j].to]]=edge[j].w; //找权值最小的边 } } } for(i=1,m=0;i<=numn;i++) { if(num[i]<INF) //全部相加 m+=num[i]; } printf("%d\n",m); } return 0; }
代码:(Kosaraju):
//Final Kosaraju强联通分量+缩点 #include <stdio.h> #include <string.h> #include <stdlib.h> #define MAX 50100 #define INF 0x3f3f3f3f struct snode{ int to,w,next; }edge1[MAX<<6],edge2[MAX<<6]; int visit[MAX],Index1,Index2,pre1[MAX],pre2[MAX]; int father[MAX],n,k,numn,num[MAX],list[MAX]; void Add_edge1(int a,int b,int c) //建立正向和逆向图 { edge1[Index1].to=b,edge1[Index1].w=c,edge1[Index1].next=pre1[a]; pre1[a]=Index1++; edge2[Index2].to=a,edge2[Index2].w=c,edge2[Index2].next=pre2[b]; pre2[b]=Index2++; } void Kosaraju(int u) //Kosaraju搜索强联通分量 { visit[u]=1; for(int i=pre1[u];i!=-1;i=edge1[i].next) { if(!visit[edge1[i].to]) Kosaraju(edge1[i].to); } list[k++]=u; //*** } void DFS(int u,int Father) //逆向搜索 { visit[u]=2; father[u]=Father; for(int i=pre2[u];i!=-1;i=edge2[i].next) { if(visit[edge2[i].to]==1) DFS(edge2[i].to,Father); } } int main() { int m,i,j,a,b,c; while(scanf("%d%d",&n,&m)!=EOF) { Index1=Index2=numn=0; memset(num,INF,sizeof(num)); memset(pre1,-1,sizeof(pre1)); memset(pre2,-1,sizeof(pre2)); memset(father,0,sizeof(father)); memset(visit,0,sizeof(visit)); for(i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); Add_edge1(a+1,b+1,c); } for(i=1,k=0;i<=n;i++) { if(!visit[i]) { Kosaraju(i); } } for(i=k-1,c=0;i>=0;i--) //逆序搜索 { if(visit[list[i]]==1) { DFS(list[i],++c); //**list[i] } } for(i=1;i<=n;i++) { for(j=pre1[i];j!=-1;j=edge1[j].next) { if(num[father[edge1[j].to]]>edge1[j].w&&father[i]!=father[edge1[j].to]) num[father[edge1[j].to]]=edge1[j].w; } } for(i=1,m=0;i<=c;i++) { if(num[i]<INF) m+=num[i]; } printf("%d\n",m); } return 0; }