AOJ 2328 Mobile Network
問題
容量が多項式で表される無向グラフが与えられる。
このグラフの1番の頂点からn番の頂点への最大流を求めよ。
制約条件
n≦50
m≦500
多項式の次数は50以下
方針
最大流をvectorで書き直すだけ。
なんだけどminを書き間違っててハマった。
ソースコード
vi& operator+=(vi &a, const vi &b){ while(a.size() < b.size()) a.pb(0); rep(i, min(a.size(), b.size())) a[i] += b[i]; while(a.size() && a.back() == 0) a.pop_back(); return a; } vi& operator-=(vi &a, const vi &b){ while(a.size() < b.size()) a.pb(0); rep(i, min(a.size(), b.size())) a[i] -= b[i]; while(a.size() && a.back() == 0) a.pop_back(); return a; } vi min(const vi &a, const vi &b){ for(int i = max(a.size(), b.size()) - 1; i >= 0; i--) if((i < a.size() ? a[i] : 0) != (i < b.size() ? b[i] : 0)) return (i < a.size() ? a[i] : 0) < (i < b.size() ? b[i] : 0) ? a : b; return b; } struct flowGraph{ struct edge{ int to, rev; vi cap; edge(int to, const vi &c, int rev) : to(to), rev(rev){ cap = c; } }; int n, *level, *iter; vector<vector<edge> > G; flowGraph(int sz) : n(sz){ G.resize(n); iter = new int[n]; level = new int[n]; } ~flowGraph(){ delete iter; delete level; } void add(int s, int t, const vi &cap){ G[s].pb(edge(t, cap, G[t].size())); G[t].pb(edge(s, vi(0), G[s].size() - 1)); } void bfs(int s){ rep(i, n) level[i] = -1; queue<int> q; level[s] = 0; q.push(s); while(!q.empty()){ int v = q.front(); q.pop(); rep(i, G[v].size()){ edge &e = G[v][i]; if(e.cap.size() && level[e.to] < 0){ level[e.to] = level[v] + 1; q.push(e.to); } } } } vi dfs(int v, int t, vi f){ if(v == t) return f; for(int &i = iter[v]; i < (int)G[v].size(); i++){ edge &e = G[v][i]; if(e.cap.size() && level[v] < level[e.to]){ vi d = dfs(e.to, t, min(f, e.cap)); if(d.size()){ e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return vi(0); } vi max_flow(int s, int t){ vi flow; while(1){ bfs(s); if(level[t] < 0) return flow; rep(i, n) iter[i] = 0; vi f; while((f = dfs(s, t, vi(51, inf))).size()) flow += f; } } }; vi parse(string s){ each(i, s) if(*i == '+') *i = ' '; stringstream ss(s); vi v; while(ss >> s){ int p, e = s.find("x") != s.npos; if((p = s.find("^")) != s.npos){ e = atoi(s.substr(p + 1).c_str()); } while(v.size() <= e) v.pb(0); if((p = s.find("x")) != s.npos) s = s.substr(0, p); if(s == "") s += "1"; v[e] = atoi(s.c_str()); } return v; } int main(){ int n, m; while(cin >> n >> m, n){ flowGraph g(n); rep(i, m){ int a, b; string c; cin >> a >> b >> c; a--; b--; vi v = parse(c); g.add(a, b, v); g.add(b, a, v); } vi ans = g.max_flow(0, n - 1); if(ans.empty()){ cout << 0 << endl; continue; } for(int i = ans.size() - 1; i >= 0; i--){ if(ans[i] == 0) continue; if(i < ans.size() - 1) cout << "+"; if(ans[i] != 1 || i == 0) cout << ans[i]; if(i > 0) cout << "x"; if(i > 1) cout << "^" << i; } cout << endl; } return 0; }