2011年11月 模擬地区予選 Problem I: Mobile Network (解法2) [Licence: NYSL Version 0.9982]

Main.java

import java.io.*;
import java.util.*;

public class Main {

  static final int L = 50;

  public void run() {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int N = sc.nextInt();
			int M = sc.nextInt();
			if (N == 0 && M == 0)
				return;
			PolyDinic pd = new PolyDinic(N, L);
			for (int i = 0; i < M; i++) {
				int s = sc.nextInt() - 1;
				int t = sc.nextInt() - 1;
				pd.addEdge(s, t, poly_parse(sc.next()));
			}
			System.out.println(poly_pp(pd.maxFlow(0, N - 1)));
		}
	}

	int[] poly_parse(String s) {
		char[] fx = (s + '\0').toCharArray();
		int[] poly = new int[L + 1];
		for (int pos = 0; fx[pos] != '\0';) {
			if (fx[pos] == '+')
				pos++;
			int c = 0;
			for (; Character.isDigit(fx[pos]); pos++) {
				c *= 10;
				c += fx[pos] - '0';
			}
			if (c == 0)
				c = 1;
			int d = 0;
			if (fx[pos] == 'x') {
				pos++;
				if (fx[pos] == '^') {
					pos++;
					for (; Character.isDigit(fx[pos]); pos++) {
						d *= 10;
						d += fx[pos] - '0';
					}
				} else
					d = 1;
			}
			poly[d] = c;
		}
		return poly;
	}

	String poly_pp(int[] poly) {
		StringBuilder sb = new StringBuilder();
		for (int i = L; i >= 0; i--)
			if (poly[i] > 0) {
				if (sb.length() > 0)
					sb.append('+');
				if (poly[i] > 1 || i == 0)
					sb.append(poly[i]);
				if (i > 0)
					sb.append('x');
				if (i > 1)
					sb.append('^').append(i);
			}
		if (sb.length() == 0)
			sb.append('0');
		return sb.toString();
	}

	public static void main(String... args) {
		new Main().run();
	}
}

class PolyDinic {
	private static final int INF = 1000000;

	private final int N, L;
	private final V[] vs;

	public PolyDinic(int n, int l) {
		N = n;
		L = l;
		vs = new V[n];
		for (int i = 0; i < n; i++)
			vs[i] = new V();
	}

	public void addEdge(int from, int to, int[] poly) {
		E e = new E(vs[from], vs[to], poly);
		vs[from].add(e);
		vs[to].add(e.inv);
	}

	public int[] maxFlow(int src, int dst) {
		vs[dst].isSink = true;

		int[] ret = new int[L + 1];
		for (int i = L; i >= 0; i--) {
			resetCapacity(i);
			while (true) {
				bfs(vs[src]);
				int t = dfs(vs[src], N);
				if (t == 0)
					break;
				ret[i] += t;
			}
		}
		return ret;
	}

	private void resetCapacity(int i) {
		for (V v : vs)
			for (E e : v)
				e.c = e.c > 0 ? INF : e.poly[i];
	}

	private void bfs(V src) {
		for (V v : vs)
			v.dist = N;
		src.dist = 0;
		Queue<V> que = new LinkedList<V>();
		que.offer(src);
		while (!que.isEmpty()) {
			V v = que.poll();
			for (E e : v)
				if (e.c > 0 && e.to.dist > v.dist + 1) {
					e.to.dist = v.dist + 1;
					que.offer(e.to);
				}
		}
	}

	private int dfs(V src, int max) {
		if (src.isSink)
			return max;
		int ret = 0;
		for (E e : src) {
			if (ret == max)
				break;
			if (e.to.dist == src.dist + 1 && e.c > 0) {
				int f = dfs(e.to, Math.min(e.c, max - ret));
				ret += f;
				e.c -= f;
				e.inv.c += f;
			}
		}
		return ret;
	}

	private static class V extends ArrayList<E> {
		public boolean isSink = false;
		private int dist = 0;
	}

	private static class E {
		public final V to;
		public final E inv;
		public final int[] poly;
		public int c = 0;

		public E(V to, E inv, int[] poly) {
			this.to = to;
			this.inv = inv;
			this.poly = poly;
		}

		public E(V from, V to, int[] poly) {
			this.to = to;
			this.inv = new E(from, this, poly);
			this.poly = poly;
		}
	}
}