一道模版题（就是这个算法有点偏……）
这道题就是在一个有向图中，求出一个定根的有根树，使其边权之和最小，其实就是有向图的最小生成树。
其实挺简单的……没我想象的那么高深。就是在改边权的地方有点不好理解，正确性可以用数学归纳法证明。
一次次缩点直到这个图不再有环为止。
代码：
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<climits> using namespace std; #define maxn 20000 #define inf 999999999 struct node { int from,to,w; } edge[maxn]; int in[maxn],pre[maxn],id[maxn]; int vis[maxn]; int n,m,root,cnt; void add(int a,int b,int w) { edge[++cnt].to=b; edge[cnt].from=a; edge[cnt].w=w; } int zhuliu() { int ans=0; while(1) { for(int i=1; i<=n; i++) in[i]=inf; for(int i=1; i<=m; i++) { int u=edge[i].from; int v=edge[i].to; if(u!=v&&edge[i].w<in[v]) { in[v]=edge[i].w; pre[v]=u; } } for(int i=1; i<=n; i++) if(i!=root&&in[i]==inf) return -1; int num=0; memset(vis,0,sizeof(vis)); memset(id,0,sizeof(id)); for(int i=1;i<=n;i++) { if(i==root) continue; ans+=in[i]; int v=i; while(vis[v]!=i&&id[v]==0&&v!=root) { vis[v]=i; v=pre[v]; } if(v!=root&&id[v]==0) { id[v]=++num; for(int j=pre[v];j!=v;j=pre[j]) id[j]=num; } } if(!num) break; for(int i=1;i<=n;i++) if(!id[i]) id[i]=++num; for(int i=1;i<=m;i++) { int u=edge[i].from; int v=edge[i].to; edge[i].from=id[u]; edge[i].to=id[v]; if(id[u]!=id[v]) edge[i].w-=in[v]; } root=id[root]; n=num; } return ans; } int main() { scanf("%d%d%d",&n,&m,&root); for(int i=1; i<=m; i++) { int a,b,w; scanf("%d%d%d",&a,&b,&w); add(a,b,w); } printf("%d ",zhuliu()); return 0; }
补充：
有几个地方很重要不可以丢掉，比如找环的时候判断id和根节点。判断id是因为这条边可能会连到一个环里，而这个环已经被染色，不能再染一遍。判断根是因为我们认为根节点没有入边，因为根节点是被指定的树根。并且不用担心从不属于这个环的点连到环里使解错误，因为就算回到环里，也不会回到这个点而是会会到与这个点直接相连的那个环里的点，从这个点反而把环处理了一遍。而这个帮别人忙的点，我们一会儿整体扫一遍的时候会发现到，将被视为单点一个环。