test/aoj/2328.test.cpp

View this file on GitHub
Last update: 2020-10-27 18:08:33+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2328

Depends on

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2328

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../string/split.cpp"
#include "../../maxflow/dinic.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  const int DEG = 55;
  const int INF = 1<<28;
  int n,m;
  while(cin>>n>>m,n){
    Dinic<int, false> flow(n);
    int ed[DEG][55][55];
    memset(ed,0,sizeof(ed));

    for(int i=0;i<m;i++){
      int a,b;
      string s;
      cin>>a>>b>>s;
      a--;b--;
      flow.add_edge(a,b,0);
      for(string t:split(s,'+')){
        if(!count(t.begin(),t.end(),'x')){
          ed[0][a][b]+=stoi(t);
          ed[0][b][a]+=stoi(t);
        }else if(t.back()=='x'){
          t.pop_back();
          if(t.empty()) t="1";
          ed[1][a][b]+=stoi(t);
          ed[1][b][a]+=stoi(t);
        }else{
          auto v=split(t,'^');
          v[0].pop_back();
          if(v[0].empty()) v[0]="1";
          ed[stoi(v[1])][a][b]+=stoi(v[0]);
          ed[stoi(v[1])][b][a]+=stoi(v[0]);
        }
      }
    }

    vector<int> ans(DEG);
    for(int i=DEG-1;i>=0;i--){
      for(auto& v:flow.G){
        for(auto& e:v){
          if(e.cap) e.cap=INF;
          e.cap+=ed[i][e.dst][flow.G[e.dst][e.rev].dst];
        }
      }
      ans[i]=flow.flow(0,n-1);
    }

    bool f=1;
    for(int i=DEG-1;i>=0;i--){
      if(!ans[i]){
        if(i) continue;
        if(f) cout<<ans[i],f=0;
        continue;
      }
      if(!f) cout<<"+";
      f=0;
      if(!(i&&ans[i]==1)) cout<<ans[i];
      if(i>0) cout<<"x";
      if(i>1) cout<<"^"<<i;
    }
    cout<<endl;
  }
  return 0;
}

#line 1 "test/aoj/2328.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2328

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "string/split.cpp"

#line 3 "string/split.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
vector<string> split(string& s,char c){
  int n=s.size();
  vector<string> res;
  for(int i=0;i<n;i++){
    if(s[i]==c) continue;
    res.emplace_back();
    while(i<n and s[i]!=c) res.back()+=s[i++];
  }
  return res;
}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "maxflow/dinic.cpp"

#line 3 "maxflow/dinic.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
// O(E V^2)
// O(E \min(E^{1/2}, V^{2/3})) if caps are constant
template<typename Flow,bool directed>
struct Dinic{
  struct Edge {
    int dst;
    Flow cap;
    int rev;
    Edge(int dst,Flow cap,int rev):dst(dst),cap(cap),rev(rev){}
  };

  vector< vector<Edge> > G;
  vector<int> level,iter;

  Dinic(int n):G(n),level(n),iter(n){}

  int add_edge(int src,int dst,Flow cap){
    int e=G[src].size();
    int r=(src==dst?e+1:G[dst].size());
    G[src].emplace_back(dst,cap,r);
    G[dst].emplace_back(src,directed?0:cap,e);
    return e;
  }

  void bfs(int s){
    fill(level.begin(),level.end(),-1);
    queue<int> que;
    level[s]=0;
    que.emplace(s);
    while(!que.empty()){
      int v=que.front();que.pop();
      for(Edge &e : G[v]) {
        if(e.cap>0 and level[e.dst]<0){
          level[e.dst]=level[v]+1;
          que.emplace(e.dst);
        }
      }
    }
  }

  Flow dfs(int v,int t,Flow 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>0 and level[v]<level[e.dst]){
        Flow d=dfs(e.dst,t,min(f,e.cap));
        if(d==0) continue;
        e.cap-=d;
        G[e.dst][e.rev].cap+=d;
        return d;
      }
    }
    return 0;
  }

  Flow flow(int s,int t,Flow lim){
    Flow fl=0;
    while(1){
      bfs(s);
      if(level[t]<0 or lim==0) break;
      fill(iter.begin(),iter.end(),0);

      while(1){
        Flow f=dfs(s,t,lim);
        if(f==0) break;
        fl+=f;
        lim-=f;
      }
    }
    return fl;
  }

  Flow flow(int s,int t){
    return flow(s,t,numeric_limits<Flow>::max()/2);
  }

  Flow cut(int s,int t,int x,int a){
    static_assert(directed, "must be directed");
    auto &e=G[x][a];
    int y=e.dst;
    Flow cr=G[y][e.rev].cap;
    if(cr==0) return e.cap=0;
    e.cap=G[y][e.rev].cap=0;
    Flow cap=cr-flow(x,y,cr);
    if(x!=s and cap!=0) flow(x,s,cap);
    if(t!=y and cap!=0) flow(t,y,cap);
    return cap;
  }

  Flow link(int s,int t,int x,int a,Flow f){
    auto &e=G[x][a];
    e.cap+=f;
    return flow(s,t,f);
  }
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 9 "test/aoj/2328.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  const int DEG = 55;
  const int INF = 1<<28;
  int n,m;
  while(cin>>n>>m,n){
    Dinic<int, false> flow(n);
    int ed[DEG][55][55];
    memset(ed,0,sizeof(ed));

    for(int i=0;i<m;i++){
      int a,b;
      string s;
      cin>>a>>b>>s;
      a--;b--;
      flow.add_edge(a,b,0);
      for(string t:split(s,'+')){
        if(!count(t.begin(),t.end(),'x')){
          ed[0][a][b]+=stoi(t);
          ed[0][b][a]+=stoi(t);
        }else if(t.back()=='x'){
          t.pop_back();
          if(t.empty()) t="1";
          ed[1][a][b]+=stoi(t);
          ed[1][b][a]+=stoi(t);
        }else{
          auto v=split(t,'^');
          v[0].pop_back();
          if(v[0].empty()) v[0]="1";
          ed[stoi(v[1])][a][b]+=stoi(v[0]);
          ed[stoi(v[1])][b][a]+=stoi(v[0]);
        }
      }
    }

    vector<int> ans(DEG);
    for(int i=DEG-1;i>=0;i--){
      for(auto& v:flow.G){
        for(auto& e:v){
          if(e.cap) e.cap=INF;
          e.cap+=ed[i][e.dst][flow.G[e.dst][e.rev].dst];
        }
      }
      ans[i]=flow.flow(0,n-1);
    }

    bool f=1;
    for(int i=DEG-1;i>=0;i--){
      if(!ans[i]){
        if(i) continue;
        if(f) cout<<ans[i],f=0;
        continue;
      }
      if(!f) cout<<"+";
      f=0;
      if(!(i&&ans[i]==1)) cout<<ans[i];
      if(i>0) cout<<"x";
      if(i>1) cout<<"^"<<i;
    }
    cout<<endl;
  }
  return 0;
}