Codeforces 62E

概述$dp$维护最小割 发现最小割是每个竖列都需要割掉一条边，然后用横边把他们连起来。 $dp_{i,s}$表示当前到了第$i$列,集合$s$的竖列已经有某条边被选中了，那么转移就是枚举当前第$i$列选不选边，然后再把需要选的横边选上割掉。 复杂度$O(2^{n}nm)$  #include <bits/stdc++.h>using namespace std;typedef long lon

$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("%lld\n",dp[(1 << n) - 1]);    return 0;}

VIEw Code 总结

以上是内存溢出为你收集整理的Codeforces 62E全部内容，希望文章能够帮你解决Codeforces 62E所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。