CUGB图论专场：J - Transfer water（最小树形图）

2 10 20 30
1 3 2
2 4 1
1 2
2 1 2
0 0 0 0

30

In  3?dimensional  space  Manhattan  distance  of  point  A  (x1,  y1,  z1)  and  B(x2,  y2,  z2)  is |x2?x1|+|y2?y1|+|z2?z1|. 
 

这题和D题都是最小树形图，主要会处理数据，把所有的边的可能加入树形图，然后求出最小值。在输入数据处理的时候刚开始处理得不好，T了几发，然后改用初始化列表水过了，虽然还是1587ms这么多的时间……

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define M 1002
#define INF 10000000
using namespace std;
typedef long long ll;
struct node
{
    int u,v,w;   //边的两端结点
    node() {}
    node(int u1,int v1,int w1):u(u1),v(v1),w(w1) {} //初始化值值列表
}e[M*M];
int pre[M],newnode[M],in[M],visit[M],a[M],b[M],c[M],n,t; //前向结点数组，新结点指向数组,边权值数组，访问数组
inline int dist(int i,int j)  //坐标两点之间的距离
{
    return abs(a[i]-a[j])+abs(b[i]-b[j])+abs(c[i]-c[j]);
}
int zhuliu(int root)
{
    int u,v,i,ans=0;  //因为把环删除后其边权值是当前和与原先和之和，所以得在循环外定义
    n++;
    while(1)
    {
        //(1).找最小边放入集合
        for(i=0;i<n;i++)
            in[i]=INF;
        for(i=0;i<t;i++)
        {
            u=e[i].u; v=e[i].v;
            if(e[i].w<in[v]&&u!=v)
            {
                pre[v]=u;  //每次都找最小边进入集合，以达最优解
                in[v]=e[i].w;
            }
        }
        in[root]=0;
        for(i=0;i<n;i++)
            if(in[i]==INF) return -1; //除了根以外还有别的结点没有入边，则说明没有连通，无最小树形图
        //(2).找环，若有环，则生成新结点，强连通分量，即环
        int New=0; //新结点还是从0开始
        mem(newnode,-1);
        mem(visit,-1);
        for(i=0;i<n;i++)  //寻找每个结点是否有环
        {
            ans+=in[i]; v=i;
            while(visit[v]!=i&&newnode[v]==-1&&v!=root) //每个点寻找其前向点，要么最终寻找至根部，要么找到一个环
            {
                visit[v]=i;
                v=pre[v];
            }
            if(v!=root&&newnode[v]==-1)  //把环缩成一个点，缩点法
            {
                for(u=pre[v];u!=v;u=pre[u])
                    newnode[u]=New;
                newnode[v]=New++;
            }
        }
        if(New==0) break;  //如果New无变化，当然就无环啦
        for(i=0;i<n;i++)
            if(newnode[i]==-1) newnode[i]=New++;
        //(3).建立新图，即把环缩成点，然后指向和边权值也随之改变
        for(i=0;i<t;i++)
        {
            u=e[i].u; v=e[i].v;
            e[i].u=newnode[u];
            e[i].v=newnode[v];
            if(newnode[u]!=newnode[v]) e[i].w-=in[v]; //两个不同的结点之间的边权值改变
        }
        n=New;
        root=newnode[root];  //结点更新之后，根结点可能有环而改变，所以根结点也要更新
    }
    return ans;
}
int main()
{
    int i,j,x,y,z,m,ab; //把所有可能的结点与边都加入最小树形图中
    while(scanf("%d%d%d%d",&n,&x,&y,&z)&&(n||x||y||z))
    {
        for(i=1,t=0;i<=n;i++) //结点从1开始
        {
            scanf("%d%d%d",&a[i],&b[i],&c[i]);
            e[t++]=node(0,i,c[i]*x);
        }
        for(i=1;i<=n;i++)
        {
            for(j=0,sca(m);j<m;j++)
            {
                sca(ab);
                if(ab==i) continue;  //下一句：结点从1开始
                int d=dist(i,ab)*y;
                e[t++]=(c[i]>=c[ab]?node(i,ab,d):node(i,ab,d+z));
            }
        }
        int ans=zhuliu(0);
        ans==-1?printf("poor XiaoA\n"):pri(ans);
    }
    return 0;
}

CUGB图论专场：J - Transfer water（最小树形图）

原文：http://blog.csdn.net/u011466175/article/details/18922983