AOJ2328 Mobile Network

問題
Mobile Network | Aizu Online Judge

ネットワークが与えられる。帯域幅として各辺にxの多項式が重みづけられている。
1番目のノードからN番目のノードまでトラフィックを流したとき、流れる量を最大化せよ。

解法
読解が難しい、というより記述が不足している気がする。

多項式の各次数毎に帯域幅（流量）が増大する。
よって、次数ごとに多項式を加減算できる。vectorなどで、通常は一変数の整数流量であるフローの流量を、整数係数の多項式として管理する。
min(多項式1, 多項式2), 多項式 > 0 の判定を定義した上で、最大流を求めれば良い。
次数が高い流量が優先されるので、min()関数は次数が高い係数から順に比較していく。

フローが双方向なため逆辺を張っているが、ノードの両端点を繋ぐ容量は倍にはならない。同じ辺についてのフローが打ち消し合い片方向にしか流れないため、高々元の容量分しか使われていないからである。（蟻本P.192）

#include <bits/stdc++.h>
 
using namespace std;
 
#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
typedef long long ll;
 
#define MAX_V (55)
#define INF (1<<29)
 
const vector<int> zero_cap = vector<int>(51);
const vector<int> inf_flow = vector<int>(51, INF);
 
struct edge {
  int to, rev;
  vector<int> cap;
  edge(int to, vector<int> cap, int rev) : to(to), cap(cap), rev(rev) {
    assert(cap.size() == 51);
  }
};
 
vector<edge> G[MAX_V];
bool used[MAX_V];
 
void add_edge(int from, int to, vector<int> cap) {
  G[from].push_back(edge(to, cap, G[to].size()));
  G[to].push_back(edge(from, zero_cap, G[from].size() - 1));
}
 
bool larger_than_0(vector<int> const& a) {
  rep(i, a.size()) if(a[i] > 0) return 1;
  return 0;
}
 
vector<int> min(vector<int> const& a, vector<int> const& b) {
  for(int i=50; i>=0; i--) {
    if(a[i] == b[i]) continue;
    if(a[i] < b[i]) return a;
    return b;
  }
  return a;
}
 
void assign_minus(vector<int>& v, vector<int> const& r) {
  for(int i=50; i>=0; i--) {
    v[i] -= r[i];
  }
}
 
void assign_plus(vector<int>& v, vector<int> const& r) {
  for(int i=50; i>=0; i--) {
    v[i] += r[i];
  }
}
 
vector<int> dfs(int v, int t, vector<int> f) {
  if(v == t) return f;
  used[v] = 1;
  rep(i, G[v].size()) {
    edge& e = G[v][i];
    if(!used[e.to] && larger_than_0(e.cap)) {
      auto d = dfs(e.to, t, min(f, e.cap));
      if(larger_than_0(d)) {
        assign_minus(e.cap, d);
        assign_plus(G[e.to][e.rev].cap, d);
        return d;
      }
    }
  }
 
  return zero_cap;
}
 
vector<int> max_flow(int s, int t) {
  vector<int> flow = zero_cap;
  for(;;) {
    memset(used, 0, sizeof(used));
    auto f = dfs(s, t, inf_flow);
    if(f == zero_cap) return flow;
    assign_plus(flow, f);
  }
}
 
void init() {
  rep(i, MAX_V) G[i].clear();
}
 
int N, M;
 
typedef string::const_iterator Iter;
Iter it;
 
int number() {
  int ret = 0;
  assert(isdigit(*it));
  while(isdigit(*it)) {
    ret *= 10; ret += *it - '0';
    it++;
  }
  return ret;
}
 
vector<string> split(string& s) {
  int n = s.size();
  int prev = 0;
  vector<string> ret;
  rep(i, n) {
    if(s[i] == '+') {
      ret.push_back(string(s.begin() + prev, s.begin() + i));
      prev = i + 1;
    }
  }
  ret.push_back(string(s.begin() + prev, s.end()));
  return ret;
}
 
int get_coef(string& term) {
  assert(!term.empty());
  if(term[0] == 'x') return 1;
  int n = term.size();
  rep(i, n) {
    if(term[i] == 'x') {
      return stoi(string(term.begin(), term.begin() + i));
    }
  }
  return stoi(term);
}
 
int get_expo(string& term) {
  if(term.find('x') == string::npos) return 0;
  if(term.find('^') == string::npos) return 1;
  int n = term.size();
  string expos;
  for(int i=n-1; i>=0; i--) {
    if(term[i] == '^') break;
    expos += term[i];
  }
  reverse(expos.begin(), expos.end());
  return stoi(expos);
}
 
vector<int> change_poly(string& s) {
  vector<int> ret(51);
  auto v = split(s);
  for(auto && e: v)
    ret[get_expo(e)] = get_coef(e);
  return ret;
}
 
void output(vector<int>& ans) {
  bool first = 0;
  for(int i=50; i>=0; i--) {
    if(ans[i] > 0) {
      if(first) cout << '+';
      first = 1;
      if(ans[i] > 1 || (ans[i] == 1 && i == 0)) cout << ans[i];
      if(i > 0) cout << 'x';
      if(i > 1) cout << "^" << i;
    }
  }
  cout << endl;
}
 
template<class T> ostream& operator << (ostream& ost, vector<T> const& v) { ost << "["; rep(i, v.size()) { if(i) ost << ", "; ost << v[i]; } ost << "]"; return ost; }
 
int main() {
 
  while(cin >> N >> M && (N | M)) {
    vector<tuple<int, int, vector<int>>> in;
    rep(i, M) {
      int s, t; cin >> s >> t; s--, t--;
      string poly; cin >> poly; auto r = change_poly(poly);
      in.emplace_back(s, t, r);
    }
 
    init();
 
    rep(i, M) {
      add_edge(get<0>(in[i]), get<1>(in[i]), get<2>(in[i]));
      add_edge(get<1>(in[i]), get<0>(in[i]), get<2>(in[i]));
    }
 
    auto ans = max_flow(0, N-1);
 
    int all0 = 1;
    rep(i, ans.size()) {
      all0 &= ans[i] == 0;
    }
 
    if(all0) cout << 0 << endl;
    else output(ans);
  }
   
  return 0;
}