【朱-刘算法】【最小树形图】hdu6141 I am your Father!

题意：给你一张带权有向图，让你求最大树形图。并在此前提下令n号结点父亲的编号最小。

比赛的时候套了个二分，TLE了。

实际上可以给每个边的权值乘1000，对于n号结点的父边，加上(999-父结点编号)大小的权值，这样即可保证最大树形图的前提下，n号结点父亲的编号最小。

网上找了个朱-刘算法的板子，把边权取负就能跑最大树形图了。

#include <cstdio>

#include <string>

#include <cstring>

#define MAXN 1005

#define MAXM 10005

using namespace std;

struct node

{

    int u, v;

    int w;

}edge[MAXM];

int pre[MAXN], id[MAXN], vis[MAXN], n, m;

int in[MAXN];

typedef int type;

#define INF 2000000000

type Directed_MST(int root, int V, int E)

{

    type ret = 0;

    while(true)

    {

        //1.?????

        for(int i = 0; i < V; i++) in[i] = INF;

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

        {

            int u = edge[i].u;

            int v = edge[i].v;

            if(edge[i].w < in[v] && u != v) {pre[v] = u; in[v] = edge[i].w;}

        }

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

        {

            if(i == root) continue;

            if(in[i] == INF) return -1;//???????????,???????

        }

        //2.??

        int cnt = 0;

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

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

        in[root] = 0;

        for(int i = 0; i < V; 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)//??

            {

                for(int u = pre[v]; u != v; u = pre[u]) id[u] = cnt;

                id[v] = cnt++;

            }

        }

        if(cnt == 0) break; //??   ?break

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

            if(id[i] == -1) id[i] = cnt++;

              //3.????

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

        {

            int u = edge[i].u;

            int v = edge[i].v;

            edge[i].u = id[u];

            edge[i].v = id[v];

            if(id[u] != id[v]) edge[i].w -= in[v];

        }

        V = cnt;

        root = id[root];

    }

    return ret;

}

int zu,xs[10005],ys[10005],zs[10005];

int main()

{

//	freopen("1009.in","r",stdin);

//	freopen("1009.out","w",stdout);

	scanf("%d",&zu);

    for(;zu;--zu)

    {

    	scanf("%d%d", &n, &m);

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

        {

            scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);

            edge[i].u--;

            edge[i].v--;

            edge[i].w*=1000;

            if(edge[i].v==n-1){

            	edge[i].w+=(999-edge[i].u);

            }

            edge[i].w=-edge[i].w;

            xs[i]=edge[i].u;

            ys[i]=edge[i].v;

            zs[i]=edge[i].w;

            if(edge[i].u == edge[i].v){

            	edge[i].w = INF;

            	zs[i] = INF;

            }

        }

        int ans = Directed_MST(0, n, m);

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

    }

    return 0;

}