有向图的最小生成树 --- 最小树形图模板

模板题 . UVA--- 11183传送

还有这道 POJ 3164 点这传送

举个例子：某个图的部分图中， 1->2权值为3， 2->1权值为4， 3->1权值为9， 4->2权值为7。 那么可以看到，结点1和结点2是形成了一个环的。我们仅从其大小不知道删除哪条边比较好，这时看到3->1权值为9， 如果走这条边，那么接下来只能删除掉2->1这条边，同理走4->2的话就要删除掉1->2这条边。 那么就不妨建立新图， 将1和2缩成一点，3->1的权值就变成了9-4=5， 4->2的权值变成了7-3=4。 这样的话，就相当于变相删除了不需要走的边了。形成新图后，又变成了最小树形图的求解，就这样循环下去，直到图中的最小边集没有环为止.

裸模板,直接上:

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#define ll long long int
#define db double
using namespace std;
const int maxn=1e3;  //点数[0-n-1]
const int maxm=1e7;  //边数
const int inf=1e9;
int n,m;
struct edge
{
    int u,v,w;
} s[maxn*maxn/2];

int pre[maxn]; //记录前驱.
int id[maxn];
int vis[maxn];
int in[maxn];

void p(int *a,int n)
{
    for(int i=1;i<=n;i++)
        printf("%d%c",a[i],i==n?'\n':' ');
}
int dirMst(int root)   //这种图中根一定是确定的.
{
    int ans=0;
    while(1)
    {
        for(int i=0; i<n; i++)
            in[i]=inf;
        memset(id,-1,sizeof(id));
        memset(vis,-1,sizeof(vis));
        for(int i=0;i<m;i++)
        {
            int u=s[i].u;
            int v=s[i].v;
            int w=s[i].w;
            if(w<in[v] && v != u )
            {
                pre[v] = u;
                in[v] = w;
            }
        }           //求最小入边集
        in[root]=0;
        pre[root]=root;//为之后的遍历做准备，in[]用于存储最小边集
        for(int i=0; i<n; i++)
        {
            if(in[i] == inf)
                return -1;
            ans += in[i];
        }          //此循环判断是否有孤立节点，同时计算当前最小权值和
        int idx = 0;//idx是用来给新的节点赋名称的（新序号）
        for(int i=0;i<n;i++)
        {
            if(vis[i] == -1 )
            {
                int u = i;
                while(vis[u] == -1){
                    vis[u] = i;
                    u = pre[u];
                }       //将vis[u]赋值为i是为了做标记
                if(vis[u] != i || u == root ) continue;     //判断是否形成环,未形成环就直接跳出.
                //只有是环的才能进入for循环.
                for(int v=pre[u];v!=u;v=pre[v] )
                    id[v] = idx;             //给环上的点赋值一个统一的标号，形成一个新的点(id[i]用于存储i点的新标号）
                id[u] = idx++;               //不在环上的新标号跟着另.
            }
        }
        if(idx==0) break;//没有环，跳出循环
        for(int i=0;i<n;i++){
            if(id[i]== -1){
                id[i]=idx++;//在上一个循环给环赋予新的序号，这一步是给非环的点新的序号，保证新图中每个点有相应的标号
            }
        }
        for(int i=0;i<m;i++)   //造新图.
        {
            s[i].w -= in[s[i].v];//把每个点的其他入边看做环的入边，将增值赋给环的入边，作为新图的这个新的点的该条入边的权值
            s[i].u = id[s[i].u];
            s[i].v = id[s[i].v];
        }            //这个循环是修改旧图，把id中存储的映射到图中形成新图
        n = idx;     //这个很重要，要知道把环捏成一个点，那么图中点个数改变了，所以循环次数改变
        root = id[root];//给根新的标号
    }
    return ans;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0; i<m; i++)
        {
            scanf("%d%d%d",&s[i].u,&s[i].v,&s[i].w);
        }
        int res=dirMst(0);    //以0为根开始搜.
        printf("%d\n",res);
    }
}