称号：

pid=2121" target="_blank">hdoj 2121 Ice_cream’s world II

题意：题目是一道躶题，给n个点，m条边的有向图。然后找一个点。到全部点的距离和最小。找出这个点并输入距离。

分析：非常明显是求一个最小树形图，可是没有说根节点。要找跟节点，我们能够虚拟一个节 点 x 。x 到全部节点连边距离为前面全部距离和+1为 dis 。

然后从x 节点求一次最小树形图为ans，则ans - dis 就是最小树形图的距离。

假设图不连通，或者ans》=2*dis 说明不存在，都则与 x 点出发的边就是结果点

AC代码：

#include <iostream>

#include <algorithm>

#include <string>

#include <math.h>

#include <vector>

#include <cstring>

#include <cstdio>

using namespace std;

const int N = 1100;

const int inf = 0x3f3f3f3f;

int n,m;

struct Node

{

    int from,to,dis;

};

vector<Node> e;

int ha[N],vis[N],father[N],in[N];

int Minroot;

int zhuliu(int root)

{

    int ans = 0;

    while(true)

    {

        for(int i=0;i<n;i++)

            in[i] = inf;

        memset(father,-1,sizeof(father));

        for(int i=0; i<e.size(); i++) //找最小入边

        {

            int to = e[i].to;

            if(e[i].dis<in[to] && e[i].from!=e[i].to)

            {

                in[to] = e[i].dis;

                father[to] = e[i].from;

                if(e[i].from == root) //找最小

                    Minroot = i;

            }

        }

        for(int i=0;i<n;i++)

        {//printf("%d ",in[i]);

            if(i!=root && in[i]==inf)

                return -1;

        }

        int cnt = 0;

        in[root] = 0;

        memset(ha,-1,sizeof(ha));

        memset(vis,-1,sizeof(vis));

        for(int i=0;i<n;i++) //找自环

        {

            ans += in[i];

            int v = i;

            while(v!=root && ha[v]==-1 && vis[v]!=i)

            {

                vis[v] = i;

                v = father[v];

            }

            if(v!=root && ha[v]==-1)

            {

                for(int j = father[v];j != v;j=father[j])

                {

                    ha[j] = cnt;

                }

                ha[v] = cnt++;

            }

        }

        if(cnt == 0) //跳出条件

            break;

        for(int i=0;i<n;i++)

            if(ha[i]==-1)

                ha[i]=cnt++;

        for(int i = 0; i< e.size();i++)

        {

            int tmp = e[i].to;

            e[i].from = ha[e[i].from];

            e[i].to = ha[e[i].to];

            if(e[i].from != e[i].to)

                e[i].dis -= in[tmp];

        }

        n = cnt;

        root = ha[root];

    }

    return ans;

}

int main()

{

    //freopen("Input.txt","r",stdin);

    while(~scanf("%d%d",&n,&m))

    {

        int num = 0;

        for(int i=0;i<m;i++)

        {

            int x,y,s;

            scanf("%d%d%d",&x,&y,&s);

            e.push_back((Node){x,y,s});

            num = num + s;

        }

        num++;

        for(int i=0;i<n;i++)

            e.push_back((Node){n,i,num});

        n++;

        int ans = zhuliu(n-1);

        //printf("%d %d\n",ans,num);

         if(ans==-1||ans>=2*num)

            puts("impossible");

        else

            printf("%d %d\n",ans-num,Minroot-m);

        puts("");

        e.clear();

    }

    return 0;

}