题解 P4854 【MloVtry的咸鱼树】

· · 题解

没人写题解我就胡一个吧

这个题真的是.....一言难尽

首先先明确一下题意：

要求一个最小生成树，其中每条边有选取条件S，当S代表的所有点连通时，这条边才能被选。

不保证S包含这条边的两个端点.....

这太自闭了.....

意识到这个情况直接A，意识不到就剩10分/xk

由于n非常小，不难想到状压。

设f[S]表示使得S代表的所有点连通的最小代价

考虑从S往外转移，边j可以往外转移需要满足S \& e[j].S == e[j].S

然后再判一下，S是不是至少包含着边j的一个端点即可。

Code: 
#include <bits/stdc++.h>
#define N 20 
using namespace std;
int bin[N];
int f[33000];
struct Edge{int x,y,S,z;}e[N*N];
char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd() {int x=0,f=1; char c=nc(); while(c<48) {if(c=='-') f=-1; c=nc();} while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x*f;}
int main()
{
    int n=rd(),m=rd();
    bin[1]=1; for(int i=2;i<=n;i++) bin[i]=bin[i-1]<<1;
    for(int i=1;i<=m;i++)
    {
        e[i].x=rd(),e[i].y=rd(),e[i].S=rd(),e[i].z=rd();
    }
    int all=(1<<n)-1;
    memset(f,0x3f,sizeof f);
    f[0]=0;
    for(int i=1;i<=n;i++) f[bin[i]] = 0;
    for(int i=0;i<=all;i++)
    {
        // f[i] ->
        for(int j=1;j<=m;j++)
        {
            if((i & e[j].S) == e[j].S)
            {
                if(((i & bin[e[j].x]) == bin[e[j].x]) || ((i & bin[e[j].y]) == bin[e[j].y]))
                {
                    f[i | (bin[e[j].x] | bin[e[j].y])] = min(f[i] + e[j].z , f[i | (bin[e[j].x] | bin[e[j].y])]);
                }
            }
        }
    }
    if(f[all]==0x3f3f3f3f) puts("-1");
    else cout << f[all] << endl ;
    return 0;
}

我也不知道为啥这个题是个黑题.....

推销个人Blog