最小树形图

说明

最小树形图就是处理一个确定起点有向有权图的最小生成树问题

解决的方法为朱刘算法

使用方法

  1. 修改mytype为边权的类型
  2. init(m)表示初始化m条边
  3. ans = Directed_MST(1, n, m);起点为1n个点,m条边
  4. bool ok = judge(ans);ok为true表示存在该树,false表示不存在

Tips

待写

模版

typedef int mytype;
const int Vmax=105;
const int Emax=Vmax*Vmax;
struct edge//有向边
{
    int u,v;    //起点 终点
    mytype l;   //权值
} e[Emax];
int pre[Vmax],ID[Vmax],vis[Vmax];
mytype In[Vmax];
void init(int m)
{
    for(int i=1; i<=m; i++){
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].l);
    }
}
mytype Directed_MST(int root,int NV,int NE)
{
    //    memset(pre,0,sizeof(pre));
    mytype ret = 0;
    while(1)
    {
        //1.找最小入边
        for(int i=1; i<=NV; i++)
            In[i] = INF;
        for(int i=1; i<=NE; i++)
        {
            int u = e[i].u;
            int v = e[i].v;
            if(e[i].l < In[v] && u != v)
            {
                pre[v] = u;
                In[v] = e[i].l;
            }
        }
        for(int i=1; i<=NV; i++)
        {
            if(i == root)
                continue;
            if(fabs(In[i]-INF)<eps)
                return -1;//除了跟以外有点没有入边,则根无法到达它
        }
        //2.找环
        int cntnode = 0;
        memset(ID,-1,sizeof(ID));
        memset(vis,-1,sizeof(vis));
        In[root] = 0;
        for(int i=1; i<=NV; i++) //标记每个环
        {
            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)
            {
                ID[v] = ++cntnode;
                for(int u = pre[v] ; u != v ; u = pre[u])
                    ID[u] = cntnode;
            }
        }
        if(cntnode == 0)
            break;//无环
        for(int i=1; i<=NV; i++)
            if(ID[i] == -1)
                ID[i] = ++cntnode;
        //3.缩点,重新标记
        for(int i=1; i<=NE; i++)
        {
            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].l -= In[v];
            }
        }
        NV = cntnode;
        root = ID[root];
    }
    return ret;
}
bool judge(mytype ans)  //判断能否成树
{
    return fabs(ans+1)>eps;
}

results matching ""

    No results matching ""