Codeforces 62E

发布时间：2020-12-16 10:46:26 所属栏目：百科来源：网络整理

导读：$dp$维护最小割发现最小割是每个竖列都需要割掉一条边，然后用横边把他们连起来。 $dp_{i,s}$表示当前到了第$i$列,集合$s$的竖列已经有某条边被选中了，那么转移就是枚举当前第$i$列选不选边，然后再把需要选的横边选上割掉。复杂度$O(2^{n}nm)$? #include

$dp$维护最小割

发现最小割是每个竖列都需要割掉一条边，然后用横边把他们连起来。

$dp_{i,s}$表示当前到了第$i$列,集合$s$的竖列已经有某条边被选中了，那么转移就是枚举当前第$i$列选不选边，然后再把需要选的横边选上割掉。

复杂度$O(2^{n}nm)$?

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int sz = 1 << 7,maxn = 1e5 + 5;
const ll inf = 1LL << 62;
int n,m;
int a[maxn][6],b[maxn][6];
ll dp[sz];
int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1; i < m; ++i)
        for(int j = 0; j < n; ++j)
            scanf("%d",&a[i][j]);
    for(int i = 0; i < m; ++i)
        for(int j = 0; j < n; ++j)
            scanf("%d",&b[i][j]);
    for(int i = 1; i < 1 << n; ++i) dp[i] = inf;
    for(int i = 1; i < m; ++i)
        for(int s = 0; s < 1 << n; ++s) {
            for(int j = 0; j < n; ++j) 
                if(!(s >> j & 1))
                    dp[s ^ (1 << j)] = min(dp[s ^ (1 << j)],dp[s] + a[i][j]);
            for(int j = 0; j < n; ++j)
                if((s >> j & 1) ^ (s >> ((j + 1) % n) & 1)) 
                    dp[s] += b[i][j];
        }
    printf("%lldn",dp[(1 << n) - 1]);
    return 0;
}

View Code

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!