ARC 078F

201707 （ACM）位运算

题意

• 给出一张带边权的无向图，无重边无自环。
• 删掉一条边的花费是这条边的边权。
• 最小花费使得1到n只有唯一一条简单路径。

题解

• dp(S,t)为集合S中，1->t的最小花费。
• cost(S,T)为集合S,T之间所有边边权之和
• 如果u不属于S，dp(S并{u},u)可以通过dp(S,t)+cost(S-{t},{u})转移过来
• dp(S并T,t)可以由dp(S,t)+cost(S-{t},T)转移过来
• 实现很精彩，但是我写不出来，代码借鉴了Y_UME的。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define sz(a) (int)a.size()
//---------------
const int N=16;
const int inf=1e9;
int n,m;
int g[N][N],f[1<<N][N],cost[1<<N][N],del[1<<N],sum[1<<N];
void upd(int &a,int b) {
    a=min(a,b);
}
int lb(int x) {return x&(-x);} 
int calc(int u) {
    if(u==0) return 0;
    if(sum[u]!=-1) return sum[u];
    int &res=sum[u];
    int y=lb(u);
    return res=del[y]+calc(y^u);
}
int main() {
    while(~scanf("%d%d",&n,&m)) {
        ///init
        memset(g,0,sizeof(g));
        memset(cost,0,sizeof(cost));
        rep(i,0,1<<n) rep(j,0,n) f[i][j]=inf;
        ///read
        rep(i,0,m) {
            int u,v,c;scanf("%d%d%d",&u,&v,&c);
            --u;--v;
            g[u][v]=g[v][u]=c;
        }
        ///solve
        rep(i,0,1<<n) rep(j,0,n) rep(k,0,n) if(i>>k&1) cost[i][j]+=g[j][k];
        f[1][0]=0;
        rep(i,0,1<<n) rep(j,0,n) if(f[i][j]!=inf) {
            memset(sum,-1,sizeof(sum));
            rep(k,0,n) if(!(i>>k&1)) del[1<<k]=cost[i^(1<<j)][k];
            rep(k,0,n) if(!(i>>k&1) &&g[j][k]) upd(f[i|(1<<k)][k],f[i][j]+del[1<<k]);
            int x=((1<<n)-1)^i;
            for(int k=x;k;k=(k-1)&x) upd(f[i|k][j],f[i][j]+calc(k));
        }
        ///print
        printf("%d\n",f[(1<<n)-1][n-1]);
    }
    return 0;
}