AtCoder ABC 235E - MST + 1 解題心得( 題目 )
解題概念:Kruskal's algorithm
解題方法:看似很麻煩，感覺像是要跑q次最小生成樹，但這樣複雜度顯然不佳，可是我們可以把這題的所有邊依照權重sort，不管是原邊還新邊都加入，也就是總共m+q個邊。
接著我們可利用Kruskal's algorithm，當我們加入一個邊(目前剩下最少權重)首先判斷他是否是新邊，如果是就利用disjoint set判斷是否屬MST，必須就答案為true，但因為查詢獨立這裡不union
反之若為原邊一樣需要判斷，但是如果判斷結果屬MST要union。
Java參考程式碼(有更好意見可留言於下方，謝謝!)
//Author:En Chi Tsung(欉恩祁)
//Date:2022/01/20
import java.io.*;
import java.util.*;
public class Main {
public static int ret,r,top;
public static int ta,tb;
public static int[] dsu=new int[200005];
public static boolean[] ans=new boolean[200005];
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws Exception{
final int n=readint();
final int m=readint();
final int q=readint();
E[] ed=new E[m+q];
Arrays.fill(dsu,-1);
for(int i=0;i<m;i++) {
ed[i]=new E(readint(),readint(),readint());
}
for(int i=m;i<m+q;i++) {
ed[i]=new E(readint(),readint(),readint(),i-m);
}
Arrays.sort(ed,new Comparator<E>() {
public int compare(E f,E s) {
return f.w-s.w;
}
});
for(E i:ed) {
if(i.id==-1) {
if(!check(i))dsu[ta]=tb;
}
else {
if(check(i))ans[i.id]=false;
else ans[i.id]=true;
}
}
for(int i=0;i<q;i++) {
bw.write((ans[i])?"Yes\n":"No\n");
}
bw.flush();
}
public static boolean check(E i) {
query(i.a);
ta=top;
query(i.b);
tb=top;
return (ta==tb);
}
public static void query(int x) {
if(dsu[x]==-1) {
top=x;
return;
}
query(dsu[x]);
dsu[x]=top;
}
public static int readint() throws Exception {
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class E{
int a,b,w,id;
E(int x,int y,int z){
a=x;
b=y;
w=z;
id=-1;
}
E(int x,int y,int z,int i){
a=x;
b=y;
w=z;
id=i;
}
}
文章標籤
全站熱搜
留言列表
