Problem C Dist 解题报告

Problem C Dist

Description

有一个(n)个点带边权的连通无向图，边集用(k)个集合(s_1,s_2,dots,s_k)和(k)个整数(w_1,w_2,dots,w_k)来表示，((s_i,w_i))表示(forall u,vin s_i (u ot=v))，(exists E(u,v)=w_i)

求(sum_{i=1}^nsum_{j=1}^{i-1}dist(i,j))，(dist(i,j))代表(i)点到(j)点的最短路。

Input

第一行两个整数(n,k)。

接下来(k)行，每行前两个整数表示(k_i,|s_i|)，接下来的(|s_i|)个整数表示(s_i)中的元素，保证集合非空且给出的元素两两不同。

Output

输出一个整数表示答案。

HINT

(1le nle 10^5,1le k le 18,1le w_ile 10^7,sum|s_i|le3 imes 10^5)

其实这种题看起来不太好想，但是可能没那么难，就是考查一些枚举技巧和小trick之类的。

首先团才那么几个，这就给了一个关于集合的思维导向性。

不妨把团抽象成点，先求出团之间的两两最短路。这里有边的条件是团的并不为空，最短路是点权和最小。

然后枚举每一个点(x)，然后把(x)到团的距离从小到大进行排序，一个团一个团的向里面加。

当前加团时，产生的贡献为(x)到团的最短距离乘上可以做出贡献的点数，可以做出贡献的点是之前加进去的团没有出现过的。

这里预处理一个(cnt_{i,s})代表在第(i)个团但不在(s)中的(1)对应的团的(x)的个数。

预处理这个需要快速求解子集和的技巧，就是(FMT)里面的一个小trick吧

Code:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
#define ll long long
const int N=1e5+10;
const int M=20;
const int inf=0x3f3f3f3f;
std::bitset <N> hav[M];
struct node
{
    int w,id;
    bool friend operator <(node n1,node n2){return n1.w<n2.w;}
    node(){}
    node(int w,int id){this->w=w,this->id=id;}
}dis[M];
using std::min;
int n,m,wei[M],be[N],g[M][M],cnt[M][1<<M];
int main()
{
    scanf("%d%d",&n,&m);
    for(int s,i=1;i<=m;i++)
    {
        scanf("%d%d",wei+i,&s);
        for(int x,j=1;j<=s;j++)
        {
            scanf("%d",&x);
            be[x]|=1<<i-1;
            hav[i][x]=1;
        }
    }
    for(int j=1;j<=m;j++)
        for(int i=1;i<=n;i++)
            if(be[i]>>j-1&1)
                ++cnt[j][be[i]];
    for(int k=1;k<=m;k++)
    {
        for(int i=1;i<1<<m;i<<=1)
            for(int s=0;s<1<<m;s++)
                if(s&i)
                    cnt[k][s]+=cnt[k][s^i];
        for(int s=0;s<1<<m;s++)
        {
            int t=s^((1<<m)-1);
            if(s<t) std::swap(cnt[k][s],cnt[k][t]);
        }
    }
    memset(g,0x3f,sizeof(g));
    for(int i=1;i<=m;i++)
        for(int j=i+1;j<=m;j++)
            if((hav[i]&hav[j]).count()!=0)
                g[i][j]=g[j][i]=wei[i]+wei[j];
    for(int k=1;k<=m;k++)
        for(int i=1;i<=m;i++)
            for(int j=1;j<=m;j++)
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]-wei[k]);
    for(int i=1;i<=m;i++) g[i][i]=wei[i];
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) dis[j]=node(inf,inf);
        for(int j=1;j<=m;j++)
            if(be[i]>>j-1&1)
                for(int k=1;k<=m;k++)
                    dis[k]=min(dis[k],node(g[j][k],k));
        std::sort(dis+1,dis+1+m);
        int sta=0;
        for(int j=1;j<=m;j++)
        {
            ans+=1ll*dis[j].w*cnt[dis[j].id][sta];
            if(j==1) ans-=dis[j].w;
            sta|=1<<dis[j].id-1;
        }
    }
    printf("%lld
",ans>>1);
    return 0;
}

2018.12.27