Mobile Network (AOJ2328)

AOJ-ICPC Programming

続く550点地帯

この問題は問題文を読んでもエスパーしないと解けないので,問題を説明すると,capが一変数(x)多項式の最大流(正確に言うと,多項式P(x)であって,xが十分大きい時にそれを代入したグラフでの(実数)フローとP(x)にxを代入した値が一致するもの)を求めよ,というやつでそれさえわかればフローを流すだけ.結局辞書順を入れればいいことはすぐわかる.

あと多項式をvectorで持ってたんですけど,昇べきで持ってたから比較関数を変えなきゃいけなくて,変えても(つまりoperator<をオーバーロードしても)もともと<が定義されてる場合はminとかの結果は変わらないんですね・・・そのせいで

#define min(x,y) (x<y?x:y)

とかいう闇コードを書いてしまった


ダメやんけ

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define min(x,y) (x<y?x:y)
using namespace std;
using namespace rel_ops;
typedef vector<int> poly;
const int MX=50;			//max deg
int deg(poly x){
	for(int i=MX;i>=0;i--) if(x[i]!=0) return i;
	return -1;
}
bool operator<(poly x,poly y){
	for(int i=MX;i>=0;i--){
		if(x[i]<y[i]) return 1;
		if(x[i]>y[i]) return 0;
	}
	return 0;
}
bool operator>(poly x,poly y){return (y<x);}
poly operator+(poly x,poly y){
	rep(i,MX+1) x[i]+=y[i];
	return x;
}
poly operator-(poly x,poly y){
	rep(i,MX+1) x[i]-=y[i];
	return x;
}
void operator+=(poly &x,poly y){
	rep(i,MX+1) x[i]+=y[i];
}
void operator-=(poly &x,poly y){
	rep(i,MX+1) x[i]-=y[i];
}
poly operator*(poly x,poly y){
	poly z(MX+1,0);
	rep(i,MX+1) rep(j,MX+1-i) z[i+j]+=x[i]*y[j];
	return z;
}
poly operator*(int x,poly y){
	rep(i,MX+1) y[i]*=x;
	return y;
}
void showpoly(poly x){
	int N=deg(x);
	if(N==-1){
		puts("0");
		return;
	}
	for(int i=N;i>=0;i--){
		if(x[i]==0) continue;
		if(i!=N&&x[i]>0) cout<<"+";
		if(x[i]==-1) cout<<"-";
		else if(x[i]!=1) cout<<x[i];
		if(i==0){
			if(x[i]==1||x[i]==-1) cout<<"1";
		}else if(i==1){
			cout<<"x";
		}else{
			cout<<"x^"<<i;
		}
	}
	puts("");
}
int num(string &s,int &it){
	int n=1;
	if(s[it]=='-'){
		it++;
		n=-1;
	}
	int x=0;
	while(isdigit(s[it])){
		x=x*10+s[it++]-'0';
	}
	return x*n;
}
poly term(string &s,int& it){
	int c=1;
	int d=0;
	if(isdigit(s[it])||s[it]=='-') c=num(s,it);
	if(s[it]=='x'){
		it++;
		d=1;
		if(s[it]=='^'){
			it++;
			d=num(s,it);
		}
	}
	poly ret(MX+1);
	ret[d]=c;
	return ret;
}
poly sttopoly(string s){
	s+="$";
	int it=0;
	poly ret=term(s,it);
	while(s[it]=='+'||s[it]=='-'){
		if(s[it]=='+'){
			it++;
			ret=ret+term(s,it);
		}else{
			it++;
			ret=ret-term(s,it);
		}
	}
	return ret;
}

typedef poly D;
struct edge {
	int to;
	D cap;
	int rev;
	edge(int to,D cap,int rev) :to(to),cap(cap),rev(rev){}
};
const int MAX_V=50;
D inf(51),zero(51);
vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];
void add_edge(int from, int to, D cap){
	edge e1(to,cap,G[to].size()),e2(from,cap,G[from].size());
	G[from].push_back(e1);
	G[to].push_back(e2);
}
void bfs(int s){
	memset(level,-1,sizeof(level));
	queue<int> que;
	level[s]=0;
	que.push(s);
	while(!que.empty()){
		int v=que.front();
		que.pop();
		for(edge& e:G[v]){
			if(e.cap>zero && level[e.to]<0){
				level[e.to]=level[v]+1;
				que.push(e.to);
			}
		}
	}
}
D dfs(int v,int t,D f){
//	cout<<v<<"v"<<endl;
	if(v==t) return f;
	for(int &i=iter[v];i<G[v].size();i++){
		edge &e=G[v][i];
		if(e.cap>zero && level[v]<level[e.to]){
			// cout<<"f=";
			// showpoly(f);
			// cout<<"e.cap=";
			// showpoly(e.cap);
			// cout<<"min=";
			// showpoly(min(f,e.cap));
			// bool b=(f<e.cap);
			// show(b);
			D d=dfs(e.to,t,min(f,e.cap));
			if(d>zero){
				e.cap-=d;
				G[e.to][e.rev].cap+=d;
				return d;
			}
		}
	}
	return zero;
}
D max_flow(int s,int t){
	D flow=zero;
	while(true){
		bfs(s);
		if(level[t]<0) return flow;
		memset(iter,0,sizeof(iter));
		D f=zero;
		while( (f=dfs(s,t,inf))>zero ) flow+=f;
	}
}
int main(){
	inf[50]=100000000;
	while(true){
		int N,M;
		cin>>N>>M;
		if(N==0) break;
		rep(i,N) G[i].clear();
		rep(i,M){
			int x,y;
			string s;
			cin>>x>>y>>s;
			add_edge(x-1,y-1,sttopoly(s));
		}
		showpoly(max_flow(0,N-1));
	}
}