Poj Solution 2257

http://poj.org/problem?id=2257

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static String[] names = new String[0];
    static int[] amount = new int[0];
    private static int[][] relation = new int[0][0];

    private static int getIndex(String s) {
        for (int i = 1; i < names.length; i++) {

            if (names[i].equals(s)) {
                return i;
            }
        }

        return -1;
    }


    /**
     * @param args
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));

        int kase = 0;

        while (true) {
            String line = stdin.readLine();

            String[] temp = line.split("[ ]+");

            int n = Integer.parseInt(temp[0]);
            int k = Integer.parseInt(temp[1]);

            if (n == 0 && k == 0) {
                break;
            }

            kase++;

            names = new String[n + 1];

            for (int i = 1; i <= n; i++) {
                names[i] = stdin.readLine().trim();
            }

            relation = new int[n + 1][n + 1];
            amount = new int[n + 1];

            for (int i = 0; i <= n; i++) {
                amount[i] = 0;

                for (int j = 0; j <= n; j++) {
                    relation[i][j] = 0;
                }
            }

            for (int i = 1; i <= k; i++) {
                line = stdin.readLine();

                temp = line.split("[ ]+");

                int indexA = getIndex(temp[0]);
                int indexB = getIndex(temp[1]);

                if (indexA == -1 || indexB == -1) {
                  //  System.out.println("name==" + temp[0] + "  " + temp[1]);
                    continue;
                }

                relation[indexA][indexB] = 1;

                int m = Integer.parseInt(temp[2]);
                amount[indexA] -= m;

                amount[indexB] += m;
            }


            // firt using foyld wall-shall.
            for (int i = 1; i<= n; i++) {
                for (int j = 1; j<= n; j++) {
                    for (int f = 1; f <= n; f++) {
                        if (relation[i][f] == 1  && relation[f][j] == 1) {
                            relation[i][j] = 1;
                        }
                    }
                }
            }

     System.out.println("Case #" + kase);
     for (int i = 1; i <= n; i++) {
       if (amount[i] < 0) {
          while (amount[i] < 0) {
          for (int j = 1; j<= n; j++) {
            if (amount[j] <= 0) {
               continue;
             }
            if (relation[i][j] == 1) {
              if (amount[j] >= Math.abs(amount[i])) {
                 System.out.println(names[j] + " " + names[i] + " " + Math.abs(amount[i]));
                 amount[j] -= Math.abs(amount[i]);
                 amount[i] = 0;
                 if (amount[i] == 0) {
                    break;
                  }
             } else {
                 System.out.println(names[j] + " " + names[i] + " " + amount[j]);
                 amount[i] += amount[j];
                 amount[j] = 0;
                 break;
             }
           }
          }
      }
     }
    }

    System.out.println();
  }

 }

}


											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *