Untitled
plain_text
2 months ago
1.8 kB
3
Indexable
Never
import java.util.Scanner; public class CopyOfTancongthanhtri { static long res; static int last; static void dfs2(boolean[] M2,int[][] g,int m,int u){ M2[u]=true; for(int v=0;v<m;++v) if(!M2[v] && g[u][v]>0) dfs2(M2,g,m,v); } static void dfs(boolean[] M,int[][] g,int[] par,int m,int u,int prev){ M[u]=true; for(int v=0;v<m;++v){ if(g[u][v]>0){ if(!M[v]){ par[v]=u; dfs(M,g,par,m,v,u); } else if(v!=prev){ int curr=u; int mine=g[u][v],ex=u,ey=v; while(curr!=v){ if(g[curr][par[curr]]<mine){ mine=g[curr][par[curr]]; ex=curr; ey=par[curr]; } curr=par[curr]; } last=u; res+=mine; g[ex][ey]=g[ey][ex]=0; } } if(last!=-1) return; } } public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int t=Integer.parseInt(scanner.next()); for(int test=1;test<=t;++test){ int m=Integer.parseInt(scanner.next()); int[][] g=new int[m][m]; for(int i=0;i<m;++i){ int sh=Integer.parseInt(scanner.next()); int smbd=Integer.parseInt(scanner.next()); int stl=Integer.parseInt(scanner.next()); for(int j=0;j<stl;++j){ int next=Integer.parseInt(scanner.next()); g[sh][next]+=smbd; g[next][sh]+=smbd; } } res=0; boolean[] M2=new boolean[m]; for(int u=0;u<m;++u){ if(!M2[u]){ dfs2(M2,g,m,u); last=u; while(last!=-1){ int tmp=last; last=-1; boolean[] M=new boolean[m]; int par[]=new int[m]; dfs(M,g,par,m,tmp,-1); } } } System.out.printf("Case #%d\n%d\n",test,res); } scanner.close(); } }