吴文虎的图论算法上写的比较清楚
还有wywcqs博客上也有很详细的解说了
http://hi.baidu.com/wywcgs/blog/item/a1ce10f4a8fa366fdcc47462.html
写了下O（VE）版本的，uva 11183
| Ranking | Submission | Run Time | Language | Submission Date |
| 10 | 5923090 | 0.390 | C++ | 2007-09-17 14:16:18 |
//uva 11183#include <cstdio>#include <cstring>#include <cmath>#include <vector>#include <algorithm>using namespace std;const int NMAX = 1500;const int INF = 0x7f7f7f7f;
struct LINKT ...{
int ls; int adj[NMAX];
void clear() ...{ls = 0;} int operator [] (const int pos) ...{return adj[pos];} int size() ...{return ls;} void push_back(const int pos) ...{adj[ls ++] = pos;}
};int n;int path[NMAX][NMAX];LINKT epath[NMAX], nepath[NMAX];int pre[NMAX];bool vis[NMAX], del[NMAX];int min_cost;int fold[NMAX], fpre[NMAX];void dfs(int pos) ...{ int i; vis[pos] = true; for(i=0;i<epath[pos].ls;i++) ...{ if(!vis[ epath[pos].adj[i] ]) dfs(epath[pos].adj[i]);
}}bool is_connect(int root) ...{ int i; memset(vis, 0, sizeof(vis)); dfs(root); for(i=1;i<=n;i++) ...{ if(!vis[i]) return false; } return true;}//O(VE)bool min_tree_graph(int root) ...{ int i,j,k; //make sure every node(except root) have in-arc if(!is_connect(root)) return false; memset(del, 0, sizeof(del)); min_cost = 0; for(i=0;i<=n;i++) fold[i] = fpre[i] = i; while(true) ...{ for(i=1;i<=n;i++) ...{ if(del[i] || i == root) continue; pre[i] = i; path[i][i] = INF;//delete self-cycle for(j=0;j<nepath[i].ls;j++) ...{ int t = nepath[i].adj[j]; if(del[t]) continue; if(path[t][i] < path[ pre[i] ][i]) pre[i] = fpre[fold[i]] = t; } }//find min in-arc for(i=1;i<=n;i++) ...{ if(del[i] || i == root) continue; j = i; memset(vis, 0, sizeof(vis)); while(!vis[j] && j != root) ...{ vis[j] = true; j = pre[j]; } if(j == root) continue;//no cycle i = j;//cycle begin node min_cost += path[ pre[i] ][i]; for(j=pre[i]; j != i ;j=pre[j]) ...{ del[j] = true;//fold cycle min_cost += path[ pre[j] ][j];//add cycle cost } for(j=0;j<nepath[i].ls;j++) ...{ int t = nepath[i].adj[j]; if(del[t]) continue; path[t][i] -= path[ pre[i] ][i]; }//i is new fold node for(j=pre[i]; j != i ;j=pre[j]) ...{ for(k=0;k<epath[j].ls;k++) ...{ int t = epath[j].adj[k]; if(del[t]) continue; if(path[i][t] == INF) ...{ epath[i].push_back(t); nepath[t].push_back(i); } path[i][t] = min(path[i][t], path[j][t]); } for(k=0;k<nepath[j].ls;k++) ...{ int t = nepath[j].adj[k]; if(del[t]) continue; if(path[t][i] == INF) ...{ epath[t].push_back(i); nepath[i].push_back(t); } if(path[t][i] > path[t][j] - path[ pre[j] ][j]) ...{ path[t][i] = path[t][j] - path[ pre[j] ][j]; fold[i] = j;//record fold node } } }//make new graph break; } if(i > n) ...{ for(i=1;i<=n;i++) ...{ if(del[i] || i == root) continue; min_cost += path[ pre[i] ][i]; } break; }//graph no cycle }//while have cycle return true;}int main() ...{ int i,j,m,t; scanf("%d", &t); for(i=1;i<=t;i++) ...{ scanf("%d %d", &n,&m); memset(path, 0x7f