Untitled

mail@pastecode.io avatarunknown
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();
	}
}