最小树形图

其实就是有向的最小生成树

写了一个下午,因为不想写矩阵,V*V的空间不适用V大的题目,所以改来改去,改成存边的形式,其实想想存边的复杂度也是O(VE),图大的话也是需要挺高复杂度的,而且矩阵虽然说是O(V3),但是有很多地方continue的,所以一般矩阵形式也就够用了- -

算法说白了比较简单,分三步,如下:

1. 每个点找其最小的入边In[v] ? 如果有除跟节点以外的点找不到入边,则无解 : 否则答案累加In[v]
2. 看看有没有环 ? 无环则已经找到解,返回答案 : 将环缩点
3. 重新构图,每条边[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