1009 I am your Father! （最小树形图-朱刘算法）
题目链接 HDU6141 I am your Father!
求有向图最大生成树，要求n的父节点尽量小。
我们将所有wi变为-wi，这题就变成了有向图最小生成树的模板题。对于f(n)尽可能小的要求，可以令所有wi扩大1000倍，然后 对于yi=n的点将1000-xi计入wi中，这样就保证了在W尽可能大的情况下f(n)尽可能小。有向图最小生成树的部分我们可以 O(nm)解决，大体思路是先找到每个点边权最小的父向边，然后这样连边可能会构成一些环，我们把这些环缩成一个点，然后把这个环向外连的边的权值减去向内连的边的权值，然后将这个图缩小，重复上述操作直至不再构成环。由于每次点数至少会减1，所以这样的操作至多做O(n)次，因此时间复杂度就是O(n*m)。
朱刘算法中不能记录路径，其中的fa[i]对应缩点后的下标。不过没关系，父节点非常好求，就是答案对1000取模。
#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=1001;
const int M=10001;
const int INF=0x3f3f3f3f;
struct edge{int u,v,w;}e[M];
int fa[N],id[N],vis[N],in[N];
int n,m;
int zhuliu(int rt){
int res=0,u,v;
while(1){
for(int i=0;i<n;i++)in[i]=INF;
for(int i=0;i<m;i++)
if(e[i].u!=e[i].v&&e[i].w<in[e[i].v]){
fa[e[i].v]=e[i].u; in[e[i].v]=e[i].w;
}
for(int i=0;i<n;i++)if(i!=rt&&in[i]==INF)return -1;
int cnt=0;
mem(id,-1);mem(vis,-1);
in[rt]=0;
for(int i=0;i<n;i++){
res+=in[i];v=i;
while(vis[v]!=i&&id[v]==-1&&v!=rt){
vis[v]=i;v=fa[v];
}
if(v!=rt&&id[v]==-1){//有环
for(u=fa[v];u!=v;u=fa[u])id[u]=cnt;//缩点
id[v]=cnt++;
}
}
if(cnt==0)break;
for(int i=0;i<n;i++)if(id[i]==-1)id[i]=cnt++;
for(int i=0;i<m;i++){
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].w -= in[v];
}
n=cnt;rt=id[rt];
}
return res;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
c*=1000;
if(v==n)c+=1000-u;
e[i]=(edge){u-1,v-1,-c};
}
int ans = zhuliu(0);
printf("%d %d
", -ans/1000, 1000-(-ans%1000));
}
return 0;
}