放到图论里面，是因为用到了近似Floyd的算法。这题的输入麻烦，到最后直接用C++搞定了。

题目给出一系列物品之间的交换关系（比如6个i交换15个k），要求递推计算出给出的物品之间交换关系。采用的方法是建立图。a[i][k]代表了i和k交换时需要i的个数，a[k][i]是需要k的个数。每次更新信息之后对图遍历，对于那些已知a[i][j]和a[j][k]的路径，求出a[i][k]，就如同Floyd求最短路径一样。

其实不用vector和string也可以解决，但是懒惰了 = = 。

PS:到了寒假，ZOJ似乎又复苏了，做题目的人好多。当初信心满满地想着要在3月份前做到400题，现在看起来像个笑话。好吧……随便做点，我最大的计划就是没有计划。

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

int a[60][60];
vector < string > sv;

void ps ()
{
 int i, k;
 for ( i = 0; i < sv.size (); i ++ )
 {
  for ( k = 0; k < sv.size (); k ++ )
  {
   printf ( "%d ", a[i][k] );
  }
 }
}

int gcd ( int x, int y )
{
 int t;
 if ( x > y )
 {
  t = x, x = y, y = t;
 }
 while ( x )
 {
  t = x;
  x = y % x;
  y = t;
 }
 return y;
}

int index ( string str )
{
 int i;
 for ( i = 0; i < sv.size (); i ++ )
 {
  if ( str == sv[i] )
  {
   return i;
  }
 }
 sv.push_back ( str );
 return i;
}

void floyd ()
{
 int i, k, j;
 for ( i = 0; i < sv.size (); i ++ )
 {
  for ( k = 0; k < sv.size (); k ++ )
  {
   if ( i == k ) continue;
   for ( j = 0; j < sv.size (); j ++ )
   {
    if ( j == k ) continue;
    if ( a[j][k] ) continue;
    if ( a[i][k] && a[j][i] )
    {
     int ta = a[i][j] * a[k][i];
     int tb = a[i][k] * a[j][i];
     int tc = gcd ( ta, tb );
     a[j][k] = tb / tc, a[k][j] = ta / tc;
    }
   }
  }
 }
}

void print ( int ia, int ib )
{
 if ( a[ia][ib] )
 {
  cout << a[ia][ib] << " " << sv[ia] << " = " << a[ib][ia] << " " <<  sv[ib] << endl;
 }
 else
 {
  cout << "? " << sv[ia] << " = " << "? " << sv[ib] << endl;
 }
}
 
int main ()
{ 
 //freopen ( "in.txt", "r", stdin );
 char op;
 string sa, sb;
 int ia, ib, na, nb, nc;
 memset ( a, 0, sizeof ( a ) );
 sv.clear ();
 while ( cin >> op )
 {
  if ( op == '.' ) break;
  else if ( op == '!' )
  {
   cin >> na >> sa >> op >> nb >> sb;
   ia = index ( sa ), ib = index ( sb );
   nc = gcd ( na, nb );
   a[ia][ib] = na / nc, a[ib][ia] = nb / nc;
   floyd ();
  }
  else
  {
   cin >> sa >> op >> sb;
   ia = index ( sa ), ib = index ( sb );
   print ( ia, ib );
  }
 }
 return 0;
}

评论