放到图论里面，是因为用到了近似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;}

评论