UVA

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.

#include
#include
#include
#include

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){
parent[find(v)]=find(u);
}

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;
memset(cycle,0,sizeof(cycle));
memset(visit,0,sizeof(visit));
int inc=mine=0x7fffffff;
bool hc=false;
for(int i=0;i Read Full Post | Make a Comment ( None so far )


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