Minimum Weighted Aborescence (Directed MST)

Posted on August 13, 2008. Filed under: Algorithm, Graph, UVA | Tags: , , |

Source code for my AC solution to UVA 11183 with 0.14s which is an implementation of directed minimum spanning tree algorithm from here.


using namespace std;

#define N 1002

int pred[N],mins[N],parent[N];
int adjc[N],radjc[N];
int adj[N][N],radj[N][N],cost[N][N];
bool visit[N],cycle[N];
int mine;

int find(int u){
return parent[u]==u?u:parent[u]=find(parent[u]);

void join(int u,int v){

bool dfs(int r,int u){
if(visit[u])return r==u;visit[u]=true;
for(int i=0;i=0){
int k=pred[i]; adj[k][adjc[k]++]=i;
if(first) mc+=mins[i];
first = false;
int inc=mine=0x7fffffff;
bool hc=false;
for(int i=0;i


Make a Comment

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Liked it here?
Why not try sites on the blogroll...

%d bloggers like this: