Matrixmultiplication

The first line is an integer n $(1 <=n <= 20)$ stands for the number of the matrices.

Every line of the following n lines contains two integer $a_i,b_i$ representing the number of rows and the number of columns of the ith matrix.( $1 ≤ a_i , b_i ≤ 1000000000$ )

Print an integer in the first line, representing the number of all possible ways to multiply all matrices. If the answer exists, the sequence of dimension tuples in the least lexicographical order must be output in the second line.

C++11(clang++ 3.9) 解法, 执行用时: 870ms, 内存消耗: 127580K, 提交时间: 2020-06-14 17:12:15

#include<bits/stdc++.h>

typedef long long ll;
typedef long double ld;
using namespace std;
//mt19937_64 mrand(chrono::steady_clock::now().time_since_epoch().count());
#define ii for(int i=1;i<=n;++i)
#define ji for(int j=1;j<=n;++j)
#define jj for(int j=1;j<=m;++j)
#define ij for(int i=1;i<=m;++i)
#define sz(x) ((ll)x.size())
#define all(x) x.begin(),x.end()
#define al(x) x+1,x+1+n
#define asd cout<<"ok"<<endl;
#define asdd cout<<"okok"<<endl;
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define pr(v) for(auto i:v) cout<<i<<" ";cout<<endl
#define prt(a, l, r) for(auto i=l;i<=r;++i) cout<<a[i]<<" ";cout<<endl;
#define pc(x) __builtin_popcount(x)
#define pb emplace_back

ll dp[20][1<<20];
pii a[20];
int n,vis[25];
void dfs(int p, vector<int> &v) {
    if(p == n) {
        for(int i : v) cout << a[i].first << " " << a[i].second << " "; cout << endl;
        exit(0);
    }
    for(int i=0;i<n;++i) {
        if(vis[i]) continue;
        if(v.size() && a[v.back()].second != a[i].first) continue;
        vis[i] = 1;
        v.push_back(i);
        dfs(p+1, v);
        vis[i] = 0;
        v.pop_back();
    }
}
int g[25][25];
int main() {
    cin>>n;
    for(int i=0;i<n;++i) {
        cin>>a[i].first>>a[i].second;
    }
    sort(a,a+n);
    for(int i=0;i<n;++i) {
        for(int j=0;j<n;++j) {
            if(i == j) continue;
            if(a[i].second == a[j].first) g[i][j] = 1;
        }
    }
    for(int i=0;i<n;++i) dp[i][1<<i]=1;
    for(int i=0;i<1<<n;++i) {
        for(int j=0;j<n;++j) {
            if(i&(1<<j)) {
                for(int k=0;k<n;++k) {
                    if(!(i&(1<<k)) && g[j][k]) {
                        dp[k][i^(1<<k)] += dp[j][i];
                    }
                }
            }
        }
    }
    ll ans=0;
    for(int i=0;i<n;++i) ans+=dp[i][(1<<n)-1];
    cout<<ans<<endl;
    if(ans) {
        vi v;
        dfs(0, v);
    }
}

详情