Tan cong thanh tri krukal
unknown
plain_text
a year ago
1.6 kB
8
Indexable
// Tan cong thanh tri krukal #include<iostream> using namespace std; #define N 100 int T, soThanhTri, soHieu, soMay, soLienKet, adj[N][N]; int st[N*N], en[N*N], dist[N*N], parent[N*N], edge; void makeSet(int x) { parent[x]=x; } int findSet(int x) { if(x==parent[x]) return x; return findSet(parent[x]); } void join(int x, int y) { parent[findSet(y)]=findSet(x); } void swap(int i, int j) { int tmp=st[i]; st[i]=st[j]; st[j]=tmp; tmp=en[i]; en[i]=en[j]; en[j]=tmp; tmp=dist[i]; dist[i]=dist[j]; dist[j]=tmp; } void sort() { for(int i=0;i<edge-1;i++) for(int j=i+1;j<edge;j++) if(dist[i]<dist[j]) swap(i,j); } int main() { freopen("a.txt","r",stdin); cin>>T; int v; for(int tc=1;tc<=T;tc++) { for(int i=0;i<N;i++) for(int j=0;j<N;j++) adj[i][j]=0; edge=0; cin>>soThanhTri; for(int t=0;t<soThanhTri;t++) { cin>>soHieu>>soMay>>soLienKet; makeSet(soHieu); for(int i=0;i<soLienKet;i++) { cin>>v; adj[soHieu][v] += soMay; adj[v][soHieu] = adj[soHieu][v]; } } for(int i=0;i<soThanhTri;i++) { for(int j=i+1;j<soThanhTri;j++) { if(adj[i][j]) { dist[edge]=adj[i][j]; st[edge]=i; en[edge++]=j; } } } sort(); int ans=0; for(int i=0;i<edge;i++) { int u=findSet(st[i]); int v=findSet(en[i]); if(u==v) ans+=dist[i]; else { join(u,v); } } for(int i=0;i<edge;i++) { dist[i]=0; parent[i]=0; st[i]=0; en[i]=0; } cout<<ans<<endl; } return 0; }
Editor is loading...
Leave a Comment