// IDEA: for each Jedi find his "connected components" (Jedi he can betray)
// pick the largest connected component and then pick the cheapest Jedi in that
// component

#include <iostream.h>
#include <fstream.h>

int A[100][100];

int vis[100];

int price[100];

int N;

struct jus {
 int cnt;      // # of connected components
 int A[100];   // connected components
} tree[100];

#define min(a,b) (a < b ? a : b)

// breadth-first-search
void BFS (int x)
{
 // don't start with x; only find CAPTURED Jedi!
 memset(vis, 0, sizeof(vis) );

 for (int j=0; j < N; j++)
  if (A[x][j] > 0)
   vis[j] = 1;

 int mod = 1;

 while (mod)
 {
   mod = 0;

   for (int i=0; i < N; i++)
    if (vis[i] == 1)
    {
     vis[i] = 2;

     for (int j=0; j < N; j++)
      if (A[i][j] > 0 && !vis[j])
       vis[j] = 1;

     mod = 1;
    }
 }

 // done

 for (int i=0; i < N; i++)
  if (vis[i])          // only count captured Jedi
   tree[x].A[ tree[x].cnt++ ] = i;
}

// find intersection
int has (int a, int b)
{
 for (int i=0; i < tree[a].cnt; i++)
  for (int j=0; j < tree[b].cnt; j++)
   if (tree[a].A[i] == tree[b].A[j])
    return 1;

 return 0;
}

void main()
{
 ifstream in; in.open("jedi.in");
 ofstream out; out.open("jedi.chk");

 int kk;
 in >> kk;
 for (int i=0; i < kk; i++)
 {
  in >> N;

  memset(tree, 0, sizeof(tree) );

  for (int j=0; j < N; j++)
   for (int k=0; k < N; k++)
    A[j][k] = -1;

  while (1)
  {
   int a, b, c;

   in >> a >> b >> c;
   if (a == 0) break;

   a--; b--;  // compensate for incompetence

   A[a][b] = c;
  }


  // separate the forest into trees
  for (j=0; j < N; j++)
   BFS(j);

  // construct prices
  for (j=0; j < N; j++)
  {
   price[j] = 30000;  // big #
   for (int k=0; k < tree[j].cnt; k++)
    if (A[j][ tree[j].A[k] ] > 0)
     price[j] = min(price[j], A[j][ tree[j].A[k] ]);
  }

  // search each tree
  // to do this, do greedy search

  int cnt = 0;
  int cost = 0;

  while (1)
  {

   // find largest tree
   int ix = -1;

   for (int j=0; j < N; j++)
    if (tree[j].cnt > 0 && (ix < 0 || tree[ix].cnt < tree[j].cnt))
     ix = j;

   if (ix < 0) break;


   // have largest tree, search it for cheapest Jedi
   int best = 0;
   for (j=0; j < tree[ix].cnt; j++)
    if (tree[j].cnt == tree[ix].cnt && price[j] < price[best])
     best = j;

   cnt += tree[best].cnt;
   cost += price[best];

   // now erase other trees
   for (j=0; j < N; j++)
    if (j != ix && has(j, ix))
     tree[j].cnt = -1;

   tree[ix].cnt = -1;
  }

  cout << cnt << " " << cost << endl;

  if (cnt < N)
   out << "IMPOSSIBLE" << endl;
  else
   out << cost << endl;

 }

 in.close();
 out.close();
}
Downloader failed!
Response object
006~ASP 0159~Buffering Off~Buffering must be on.