TIOJ::1698 . Problem H 神殿裡的觸手

http://tioj.ck.tp.edu.tw/problems/1698
圖論題,有趣的題目,雖然感覺做起來很煩…..但是其實也還好。

題目是你有一張圖,你要對他們做最小生成樹MST(或是生成森林),但是有些邊不一定會被加到MST裡,因為權重一樣所以也許可以取代(比如一個權重都是k的三角形)。題目問哪些邊一定會在MST裡

解法其實滿漂亮的。
我們會發現,會有多種MST代表一定有兩條以上的邊權重一樣。所以我們可以在做Kruskal’s Algorithm的時候,每舉權重一樣的邊加進MST裡。

當然不可能是這樣啦~~~。

不過我們會發現,Kruskal’s Algorithm做的事是合併一些MST成為新的MST,所以如果我們把MST當作一個點這些權重一樣的邊和這些點就可以建出一張圖,一定在最終的MST裡的邊就是這張圖的!!!!

所以就先做Kruskal’s Algorithm,一次處理權重一樣的邊(因為排序過,所以會在一個連續的區間),每次先不要把這些邊拿去合併,先建圖,找橋,把橋標記一下,然後再合併MST繼續Kruskal’s Algorithm。

找橋的時候要注意重邊,其實可以開一個bool陣列紀錄這條邊用過沒有,建圖用邊去建,一條邊只能走一次。比較有問題的是dfs id和low還有建圖的vector這些跟點編號有關係的變數,要是直接初始化複雜度會掉回N^2,不過我們可以在建圖之前,先跑一次所有邊,把所有會用到的點的相關變數初始化

真心覺得找橋的Tarjan比找割點的好寫多了QQ。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cstdio>
#include <algorithm>
#include <cstring>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define N 100010
using namespace std;
struct e{
int i,a,b,c;
}E[4*N];
int F[N],dfs[N],low[N],EE[4*N],dfsn,ans;
bool ANS[4*N],wed[4*N];
vector<int>G[N];
int find(int x){
return x==F[x]?x:F[x]=find(F[x]);
}
void Tarjan(int now){
// printf("GG %d %d\n",now,G[now].size());
dfs[now]=low[now]=++dfsn;
for(int p:G[now])if(!wed[p]){
wed[p]=1;
int t=EE[p]-now;
if(dfs[t])low[now]=min(low[now],dfs[t]);
else{
Tarjan(t);
low[now]=min(low[now],low[t]);
if(low[t]>dfs[now])ANS[p]=1,ans++;
}
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
F(m)scanf("%d%d%d",&E[i].a,&E[i].b,&E[i].c),E[i].i=i;
sort(E,E+m,[](const e&a,const e&b){return a.c<b.c;});
F(n)F[i+1]=i+1;
F(m){
int k=E[i].c,p=i;
while(p<m&&E[p].c==k){
int a=find(E[p].a),b=find(E[p].b);
if(a==b){
wed[E[p++].i]=1;
continue;
}
G[a].push_back(E[p].i);
G[b].push_back(E[p].i);
EE[E[p++].i]=a+b;
}
Fl(j,i,p)if(!wed[E[j].i])
Tarjan(F[E[j].a]);
Fl(j,i,p){
int a=F[E[j].a],b=F[E[j].b];
dfs[a]=dfs[b]=0;
G[a].clear();
G[b].clear();
}
Fl(j,i,p)F[find(E[j].a)]=find(E[j].b);
i=p-1;
}
printf("%d\n",ans);
if(ans){
F(m)if(ANS[i])printf("%d ",i+1);
}
else printf("0");
puts("");
scanf("%*d");
}