usaco 4_1_3 fence loops 题解_leokan的blog.mht

美国USACO题库源程序

void update(int loc)
 { /* we've decreased the value of dist[loc] */
   /* change heap to maintain heap order */
  int val;
  int p, t;

  val =3D dist[loc];
  p =3D hloc[loc];
  while (p > 0)
   { /* while the element's not the root of the heap */

    /* check to see if it's less than it's parent */
    t =3D (p-1)/2;
    if (dist[heap[t]] > val)
     { /* if so, move parent down */
      heap[p] =3D heap[t];
      hloc[heap[p]] =3D p;

      /* consider as if updated element is now in parent's prev location =
*/
      p =3D t;
     } else break; /* otherwise, stop */
   }

  /* put element in proper location in heap */
  heap[p] =3D loc;
  hloc[loc] =3D p;
  check_heap(); /* sanity check */
 }

void add_heap(int loc)
 { /* add an element to the heap /*

  if (hloc[loc] =3D=3D -1)
   { /* if it's not in the heap, add to the end (eff value =3D infinity) =
*/
    heap[hsize++] =3D loc;
    hloc[loc] =3D hsize-1;
   }

  /* change the value to the real value */
  update(loc);
 }

void fill_dist(int s)
 {
  int lv;
  int p;
  int t;
  int l;

 /* initialize hloc & dist */
  for (lv =3D 0; lv < npl; lv++) { hloc[lv] =3D -1; dist[lv] =3D =
255*MAXS + 1; }
  dist[s] =3D 0;
  hsize =3D 0;
  add_heap(s);

  while (hsize)
   { /* heap is not empty */

    /* take minimum distance location */
    p =3D heap[0];
    delete_min();
    t =3D dist[p];

    /* try all possible endpoints of other edges at the same location */
    for (lv =3D 0; lv < ccnt[p]; lv++)
     {
      l =3D alist[p][lv];
      if (dist[l] > t)
       { /* found better distance */
        dist[l] =3D t;
 add_heap(l); /* add, if necessary, update otherwise */
       }
     }

    /* consider moving across this edge */
    t =3D dist[p] + length[p/2];=20
    p =3D p ^ 0x1; /* go to the other endpoint */
    if (dist[p] > t)=20
     { /* found a better way to get to the location */
      dist[p] =3D t;
      add_heap(p);
     }
   }
 }

int main(int argc, char **argv)
 {
  FILE *fout, *fin;
  int lv, lv2, lv3;
  int c1, c2;
  int segid, len;
  int p;
  int min;

  if ((fin =3D fopen("fence6.in", "r")) =3D=3D NULL)
   {
    perror ("fopen fin");
    exit(1);
   }
  if ((fout =3D fopen("fence6.out", "w")) =3D=3D NULL)
   {
    perror ("fopen fout");
    exit(1);
   }

  fscanf (fin, "%d\n", &nfence);
  npl =3D nfence*2;

  for (lv =3D 0; lv < nfence; lv++)
   { /* read in edges */
    fscanf (fin, "%d %d %d %d", &segid, &len, &c1, &c2);
    segid--;
    length[segid] =3D len;
    ccnt[2*segid] =3D c1;
    ccnt[2*segid+1] =3D c2;
    while (c1--)
     {
      fscanf (fin, "%d", &p);
      conn[2*segid][c1] =3D p-1;
     }
    while (c2--)
     {
      fscanf (fin, "%d", &p);
      conn[2*segid+1][c2] =3D p-1;
     }
   }

  for (lv =3D 0; lv < npl; lv++)
    for (lv2 =3D 0; lv2 < ccnt[lv]; lv2++)
     { /* for all edges */
      c1 =3D lv/2;
      c2 =3D conn[lv][lv2]*2;

      /* find other occurance of edge */
      for (lv3 =3D 0; lv3 < ccnt[c2]; lv3++)
        if (conn[c2][lv3] =3D=3D c1)
   break;

      /* if no match was found, must be on 'other' side of edge */
      if (lv3 >=3D ccnt[c2]) c2++;

      /* update adjaceny list */
      alist[lv][lv2] =3D c2;
     }

  min =3D 255*MAXS+1; /* higher than we could ever see */

  for (lv =3D 0; lv < nfence; lv++)
   { /* for each fence */
    =20
    /* make edge infinite length, to ensure it's not used */
    len =3D length[lv];
    length[lv] =3D 255*MAXS+1;=20

    /* find distance from one end-point of edge to the other */
    fill_dist(2*lv);

    /* if the cycle (the path plus the edge deleted) is better
       than the best found so far, update min */
    if (dist[2*lv+1] + len < min)
      min =3D dist[2*lv+1] + len;=20

    /* put edge back in */
    /* actually, not necessary, since we've already found the
       best cycle which uses this edge */
    length[lv] =3D len;
   }

  fprintf (fout, "%i\n", min);
  return 0;
 }
</STRONG></PRE>
      <P><STRONG>Bjarke Roune has some improvements: </STRONG></P>
      <P><STRONG>When creating the graph representation, instead of =
searching=20
      through all edges to identy the nodes that corresponds to the =
endspoints=20
      of the edges (fence segments), a signature of each node is =
created. This=20
      signature consists of the two maximal IDs of the edges (fence =
segments)=20
      that connect at that node. These IDs are guarantueed to be unique, =
as the=20
      fence segments are straight, so if two fence segments meet at one =
point,=20
      they cannot meet anywhere else (the fence segments cannot be right =
on top=20
      of each other, as the problem statement says they only meet at =
their=20
      endpoints). </STRONG></P>
      <P><STRONG>When running the Dijkstra algorithm, it is unnecessary =
to=20
      consider any paths anywhere that are equal to or greater than the =
smallest=20
      perimeter found so far. These paths can safely be considered of =
infinite=20
      distance (i.e., they can be ignored). </STRONG></P>
      <P><STRONG>After having found the smallest perimeter that includes =
a=20
      certain node, that node can safely be removed from the graph, =
since we=20
      have already got the smallest perimeter that includes that node. =
(a=20
      comment in the solution also says this, but for some reason the =
node is=20
      put back in anyway). </STRONG></P>
      <P><STRONG><EM>The solution below is blazingly fast...RK</EM>=20
</STRONG></P><PRE><STRONG>#include &lt;fstream.h&gt;

const int Inf =3D 1000 * 1000 * 1000;

ifstream in ("fence6.in");
ofstream out ("fence6.out");

/* The edges are one-way so two edges are neccesary for each fence =
segment. */

struct Edge {
    Edge () { }
    Edge (int _to, int _dist):to (_to), dist (_dist) { }
    int     to, dist;
}       edges[100][8];  /* edges[x][y] =3D edge number y of node
       number x */
int     edgeCo[100];  /* edgeCo[x]   =3D number of edges that
       connect at node x */
int     nodeCo =3D 0;  /* total number of nodes */

/*
 * Each node is given a signature consisting of the two largest fence
 * segment IDs of all the fence segments that connect at that node
 */

int     sigs[100][2];  /* sigs[x] =3D signature of node x.
       sigs[x][0] &gt; sigs[x][1] */

void=20
AddEdge (int from, const Edge &amp; edge)
{
    edges[from][edgeCo[from]++] =3D edge;
}

/* Returns the removed edge */
Edge=20
RemoveEdge (int from, int to)
{
    int     i;
    for (i =3D 0; i &lt; edgeCo[from]; ++i) {
 if (edges[from][i].to =3D=3D to) {
     Edge    tmp =3D edges[from][i];
     edges[from][i] =3D edges[from][--edgeCo[from]];
     return tmp;
 }
    }
}

/*
 * The segs parameter is an array of length len that contains the IDs of =
the
 * fence segments that meet at the sought-for node.
 */

int=20
GetNode (int *segs, int len) {
 /* The signature of the node is calculated by retriving the two largets
    fence segment IDs */
    int     i, max0 =3D 0, max1 =3D 0;
    for (i =3D 0; i &lt; len; ++i) {
 if (segs[i] &gt; max1) {
     if (segs[i] &gt; max0) {
  max1 =3D max0;
  max0 =3D segs[i];
     }
     else
  max1 =3D segs[i];
 }
    }

 /* The known signatures are searched. If a matching signature is found,
    the corresponding node is returned */
    for (i =3D 0; i &lt; nodeCo; ++i)
 if (max0 =3D=3D sigs[i][0] &amp;&amp; max1 =3D=3D sigs[i][1])
     return i;

 /* A signature could not be made, so we will have to create a new node
    with that signature. This node is then returned */
    sigs[nodeCo][0] =3D max0;
    sigs[nodeCo][1] =3D max1;

    return nodeCo++;
}

/* This function returns length of the shortest path between the =
passed-in
   nodes.
   Paths of length equal to or larger than lessThan are not considered.
   It is not guaranteed that the graph is connected.
   If no suitable path is found, Infinity is returned
*/
int=20
CalcShortestPath (int from, int to, int lessThan) {
    bool    visited[100];
    int     dist[100];

    int     i;
    for (i =3D 0; i &lt; nodeCo; ++i)
 visited[i] =3D false, dist[i] =3D Inf;

    visited[from] =3D true;
    dist[from] =3D 0;
    int     lastVisited =3D from;

    for (;;) {
 int     j;
 for (j =3D 0; j &lt; edgeCo[lastVisited]; ++j) {
     const   Edge &amp; edge =3D edges[lastVisited][j];
     int     d =3D dist[lastVisited] + edge.dist;
     if (d &lt; lessThan &amp;&amp; dist[edge.to] &gt; d)
  dist[edge.to] =3D d;
 }

 int     minDist =3D Inf;
 for (j =3D 0; j &lt; nodeCo; ++j)
     if (!visited[j] &amp;&amp; minDist &gt; dist[j])
  lastVisited =3D j, minDist =3D dist[j];

 if (minDist =3D=3D Inf)
     break;

 visited[lastVisited] =3D true;
    }

    return dist[to];
}

void=20
ReadArray (int *arr, int len, istream &amp; in)
{
    int     i;
    for (i =3D 0; i &lt; len; ++i)
 in &gt;&gt; arr[i];
}

int=20
main () {
    int     segCo;
    in &gt;&gt; segCo;

    int     i;
    for (i =3D 0; i &lt; segCo; ++i) {
 int     dist, co1, co2, segs[9];
 in &gt;&gt; segs[0] &gt;&gt; dist &gt;&gt; co1 &gt;&gt; co2;

 ReadArray (segs + 1, co1, in);
 int     node1 =3D GetNode (segs, co1 + 1);

 ReadArray (segs + 1, co2, in);
 int     node2 =3D GetNode (segs, co2 + 1);

 AddEdge (node1, Edge (node2, dist));
 AddEdge (node2, Edge (node1, dist));
    }

 /*
  * For each node, the smallest perimeter that includes that node is
  * calculated. After each calculation, that node is deleted, as no =
smaller
  * perimeter can possibly include that node (we already got the =
smallest
  * one).
  */
    int     minPerim =3D Inf;
    while (nodeCo !=3D 0) {
 int     node =3D nodeCo - 1;

    /* Nodes and therefore edges are continually removed, so there might =
be
       some nodes with less than 2 edges. Such nodes obviously cannot be
       part of any perimeter. */
 if (edgeCo[node] &gt; 1) {
 /* The minimal perimeter that includes the node is calculated */
     for (i =3D 0; i &lt; edgeCo[node]; ++i) {
  int     otherNode =3D edges[node][i].to;

  Edge    out =3D RemoveEdge (node, otherNode);
  Edge    in =3D RemoveEdge (otherNode, node);

  int     perim =3D out.dist + CalcShortestPath (node,
            otherNode, minPerim - out.dist);

  if (minPerim &gt; perim)
      minPerim =3D perim;

  AddEdge (node, out);
  AddEdge (otherNode, in);
     }
 }

    /* The node is deleted by deleting all edges to it and decreasing
       nodeCo, so that the current node "falls of the edge" of the now
       smaller edges array */
 for (i =3D 0; i &lt; edgeCo[node]; ++i)
     RemoveEdge (edges[node][i].to, node);
 --nodeCo;
    }

    out &lt;&lt; minPerim &lt;&lt; '\n';

    return 0;
}</STRONG></PRE></DIV></TD></TR></TBODY></TABLE><BR>
<DIV class=3Dopt><A =
title=3D=B2=E9=BF=B4=B8=C3=B7=D6=C0=E0=D6=D0=CB=F9=D3=D0=CE=C4=D5=C2=20
href=3D"http://hi.baidu.com/leokan/blog/category/Oi">=C0=E0=B1=F0=A3=BAOi=
</A> | <A=20
title=3D=BD=AB=B4=CB=CE=C4=D5=C2=CC=ED=BC=D3=B5=BD=B0=D9=B6=C8=CB=D1=B2=D8=
 onclick=3D"return addToFavor();"=20
href=3D"http://cang.baidu.com/do/add" =
target=3D_blank>=CC=ED=BC=D3=B5=BD=CB=D1=B2=D8</A> | =E4=AF=C0=C0(<SPAN=20
id=3Dresult></SPAN>) | <A=20
href=3D"http://hi.baidu.com/leokan/blog/item/b586bc352214108fa71e12ce.htm=
l#send">=C6=C0=C2=DB</A>&nbsp;(0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'USACO 4.1.1 Beef McNuggets =CC=E2=BD=E2', 'USACO =
4.1.1 Beef McNuggets =
=CC=E2...','/leokan/blog/item/01425c3db057c9ea3c6d9719.html'];
var post =3D [true,'USACO 4.2.2 The Perfect Stall =CC=E2=BD=E2','USACO =
4.2.2 The Perfect Stall ...', =