最小樹形圖
其實就是有向的最小生成樹
寫了一個下午,因為不想寫矩陣,V*V的空間不适用V大的題目,是以改來改去,改成存邊的形式,其實想想存邊的複雜度也是O(VE),圖大的話也是需要挺高複雜度的,而且矩陣雖然說是O(V3),但是有很多地方continue的,是以一般矩陣形式也就夠用了- -
算法說白了比較簡單,分三步,如下:
- 每個點找其最小的入邊In[v] ? 如果有除跟節點以外的點找不到入邊,則無解 : 否則答案累加In[v]
- 看看有沒有環 ? 無環則已經找到解,傳回答案 : 将環縮點
- 重新構圖,每條邊[u->v]的權值減去In[v],然後重複第一步
模闆如下
?[Copy to clipboard] View Code CPP
#define M 101
#define type int
#define inf INT_MAX
struct Node{
int u , v;
type cost;
}E[M*M];
int pre[M],ID[M],vis[M];
type In[M];
type Directed_MST(int root,int NV,int NE) {
type ret = 0;
while(true) {
//1.找最小入邊
FF(i,NV) In[i] = inf;
FF(i,NE) {
int u = E[i].u;
int v = E[i].v;
if(E[i].cost < In[v] && u != v) {
pre[v] = u;
In[v] = E[i].cost;
}
}
FF(i,NV) {
if(i == root) continue;
if(In[i] == inf) return -1;//除了跟以外有點沒有入邊,則根無法到達它
}
//2.找環
int cntnode = 0;
CC(ID,-1);
CC(vis,-1);
In[root] = 0;
FF(i,NV) {//标記每個環
ret += In[i];
int v = i;
while(vis[v] != i && ID[v] == -1 && v != root) {
vis[v] = i;
v = pre[v];
}
if(v != root && ID[v] == -1) {
for(int u = pre[v] ; u != v ; u = pre[u]) {
ID[u] = cntnode;
}
ID[v] = cntnode ++;
}
}
if(cntnode == 0) break;//無環
FF(i,NV) if(ID[i] == -1) {
ID[i] = cntnode ++;
}
//3.縮點,重新标記
FF(i,NE) {
int v = E[i].v;
E[i].u = ID[E[i].u];
E[i].v = ID[E[i].v];
if(E[i].u != E[i].v) {
E[i].cost -= In[v];
}
}
NV = cntnode;
root = ID[root];
}
return ret;
} |
模闆題:
TJU2248 Channel Design
pku3164 Command Network
uva11183 Teen Girl Squad
沒有定根的題:
hdu2121 Ice_cream’s world II
解法:
由于沒有根,是以我們可以虛拟一個根,到每個點的權值很大很大(所有權值+1即可),權值很大可以保證最後隻有一個點連這個虛拟根,然後最大答案減去這個很大的權值,而要輸出最小的根的話則有點惡心- -由于我的做法會改變點的ID号,是以要儲存原來的ID,如果和最初的跟節點連得話,那麼更新一下最小的ID(也可不用儲存,根據資料的儲存順序直接算出來)
hdu3072 Intelligence System
有人說這題縮點後最小樹形圖,其實縮點後已經沒有環了,直接找入邊最小的集合加起來就可以構成最小樹形圖..
hdu4009 Transfer water