JAG 模擬地区予選 2011 I問題

解法

多項式の比較 + Dinic法

実装(C++)

遅いフローアルゴリズムで提出してしまい1TLE

#include <algorithm>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <iomanip>
#include <functional>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iterator>
#include <sstream>
using namespace std;
#define REP(i,x) for(int i=0;i<(int)x;i++)
#define FOR(it,x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
typedef map<int,int> P;
const int MAX_V=100;
struct edge{int to;P cap;int rev;};
vector<edge> G[MAX_V];
bool used[MAX_V];
vector<string> split(string exp,string delimiter){
        int L=delimiter.size(),l=exp.size();
        vector<string> res;string tmp="";
        REP(i,l){
                if(i<=l-L&&exp.substr(i,L)==delimiter){
                         res.push_back(tmp);
                         tmp="";
                         i+=L-1;
                }else{
                        tmp+=exp[i];
                }
        }
        if(tmp!="")res.push_back(tmp);
        return res;
}

istream &operator>>(istream &is,P &a){
        a.clear();
        string s;
        is>>s;
        vector<string> plused=split(s,"+");
        REP(i,plused.size()){
                string tmp=plused[i];
                vector<string> strs=split(tmp,"x");
                if(strs[0].size()==0)strs[0]="1";
                if(strs.size()==1&&tmp.find("x")==string::npos){
                        a[0]+=atoi(strs[0].c_str());
                }else{
                        if(strs.size()==1){
                                a[1]+=atoi(strs[0].c_str());
                        }else{
                                a[atoi(strs[1].substr(1).c_str())]+=atoi(strs[0].c_str());
                        }
                }
        }
        return is;
}
ostream &operator<<(ostream &os,P tmp){
        bool init=0;
        FOR(it,tmp){
                if(it->second==0){
                        tmp.erase(it--);
                }
        }
        if(tmp.size()==0){
                cout<<"0";
        }else{
                for(P::reverse_iterator it=tmp.rbegin();it!=tmp.rend();it++){
                        if(init){
                                if(it->second>0){
                                        cout<<"+";
                                }
                        }
                        if(it->second==0)continue;
                        if(it->second==-1)
                                cout<<"-";
                        else if(it->second==1){

                        }else{
                                cout<<it->second;
                        }
                        if(it->first==1){
                                cout<<"x";
                        }else if(it->first==0){
                                if(abs(it->second)==1){
                                        cout<<1;
                                }
                        }else{
                                cout<<"x^"<<it->first;
                        }
                        init++;
                }
        }
        return os;
}
P operator+(const P &a,const P &b){
        P res(b);
        FOR(it,a){
                res[it->first]+=it->second;
        }
        return res;
}
P operator-(const P &a,const P &b){
        P res(a);
        FOR(it,b){
                res[it->first]-=it->second;
        }
        return res;
}
bool operator<(const P &a,const P &b){
        P tmp=a-b;
        for(P::reverse_iterator it=tmp.rbegin();it!=tmp.rend();it++){
                //cout<<"!"<<it->first<<","<<it->second<<endl;
                if(it->second>0)return false;
                if(it->second<0)return true;
        }
        return false;
}
bool operator>(const P &a,const P &b){
        return b<a;
              //a>b;
}
int level[MAX_V];
int iter[MAX_V];
void add_edge(int from,int to,P cap){
        G[from].push_back((edge){to,cap,G[to].size()});
        G[to].push_back((edge){from,P(),G[from].size()-1});
}

P dfs(int v,int t,P f){
        //cout<<v<<","<<f<<endl;
        if(v==t)return f;
        for(int &i=iter[v];i<(int)G[v].size();i++){
                edge &e=G[v][i];
                if(e.cap>P()&&level[v]<level[e.to]){
                        P next=f;
                        if(f>e.cap)next=e.cap;
                        P d=dfs(e.to,t,next);
                        if(d>P()){
                                e.cap=e.cap-d;
                                G[e.to][e.rev].cap=G[e.to][e.rev].cap+d;
                                return d;
                        }
                }
        }
        return P();
}
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(int i=0;i<(int)G[v].size();i++){
                        edge &e=G[v][i];
                        if(e.cap>P()&&level[e.to]<0){
                                level[e.to]=level[v]+1;
                                que.push(e.to);
                        }
                }
        }
}
P max_flow(int s,int t){
        P flow;
        while(1){
                bfs(s);
                if(level[t]<0)return flow;
                memset(iter,0,sizeof(iter));
                P INF;
                INF[100]=99999999;
                P f;
                while((f=dfs(s,t,INF))>P())
                        flow=flow+f;
        }
}

int main() {
        int N,M;
        while(cin>>N>>M){
                if(N==0)break;
                for(int i=0;i<N;i++){
                        G[i].clear();
                }
                for(int i=0;i<M;i++){
                        int s,t;P c;
                        cin>>s>>t>>c;
                        s--;t--;
                        add_edge(s,t,c);
                        add_edge(t,s,c);
                }
                cout<<max_flow(0,N-1)<<endl;
        }
        return 0;
}