問題
複数のN[i]とM[i]の行列が与えられ、積の計算を行う。
行列計算はAxB、CxDにおいてB=CであればAxDの値と等しくなる。
また、計算結果の要素数はAxDの値となる。
このとき、行列の計算順序を入れ替えることですべての積をひとつにまとめることができるのであれば、そのうち計算結果が最大の要素となる要素数を求める。
まとめることができない場合はー１を返す。
解き方
行列をひとつにまとめることができるか、ということなので
つまり一筆書きができるか、オイラー路があるかと考えることができる。
オイラー路があるかどうか、あるときにそのルートを求める方法は以下に解説されています。
http://nya3.jp/libicpc/?%E3%83%A9%E3%82%A4%E3%83%96%E3%83%A9%E3%83%AA%2F%E3%82%B0%E3%83%A9%E3%83%95%2F%E5%B7%A1%E5%9B%9E%E8%B7%AF%2F%E6%9C%89%E5%90%91%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E8%B7%AF
今回は始点と終点を求められるようにコーディングする。
まずは各数に対して出次数と入次数を計算し、その差の次数が２以上であれば一筆書きできない。
また差の入次数１のノードが１つ、差の出次数１のノードが１つでなければ一筆書きできない。
次に全てのノードをたどっていったとき、たどっていないノードがあれば一筆書きできない。
最後に入次数１のノードが１つ、出次数１のノードが１つであればそのノードの積が答えになり、すべての次数が０であればどこからでもスタートできるので最大のＮ＊Ｎが答えになる。
コーディングの際、配列の数は十分か注意する。
（p[x][y]は実際の要素数を表わすので、p[60][60]ではなくp[1001][1001]）
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int p[1001][1001];
int deg[1001],used[1001];
class OrderDoesMatter {
public:
void f(int x){
used[x]=1;
FORE(i,0,1001)if(p[x][i]&&!used[i])f(i);
}
int getOrder(vector<int> N, vector<int> M) {
int n=N.size();
memset(p,0,sizeof(p));
memset(deg,0,sizeof(deg));
memset(used,0,sizeof(used));
FORE(i,0,n){
p[N[i]][M[i]]=1;
deg[N[i]]++;
deg[M[i]]--;
}
int cnt=0,maxp=N[0],minp=N[0];
FORE(i,0,1001){
if(deg[i]!=0){
cnt++;
if(abs(deg[i])>=2)return -1;
if(deg[i]==1)maxp=i;
if(deg[i]==-1)minp=i;
}
}
if(cnt>2)return -1;
f(maxp);
FORE(i,0,n)if(!used[N[i]])return -1;
if(cnt>0)return maxp*minp;
int ans=0;
FORE(i,0,n)ans=max(ans,N[i]*N[i]);
return ans;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int p[1001][1001];
int deg[1001],used[1001];
class OrderDoesMatter {
public:
void f(int x){
used[x]=1;
FORE(i,0,1001)if(p[x][i]&&!used[i])f(i);
}
int getOrder(vector<int> N, vector<int> M) {
int n=N.size();
memset(p,0,sizeof(p));
memset(deg,0,sizeof(deg));
memset(used,0,sizeof(used));
FORE(i,0,n){
p[N[i]][M[i]]=1;
deg[N[i]]++;
deg[M[i]]--;
}
int cnt=0,maxp=N[0],minp=N[0];
FORE(i,0,1001){
if(deg[i]!=0){
cnt++;
if(abs(deg[i])>=2)return -1;
if(deg[i]==1)maxp=i;
if(deg[i]==-1)minp=i;
}
}
if(cnt>2)return -1;
f(maxp);
FORE(i,0,n)if(!used[N[i]])return -1;
if(cnt>0)return maxp*minp;
int ans=0;
FORE(i,0,n)ans=max(ans,N[i]*N[i]);
return ans;
}
};