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;
}