Minimum Weighted Aborescence (Directed MST)
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
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
... 