洛谷P3264 [JLOI2015]管道连接（斯坦纳树）

传送门

感觉对斯坦纳树还是有很多疑惑啊……

等到时候noip没有爆零的话再回来填坑好了

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<cstring>

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,:;}

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=1e6+;

 int head[N],Next[N],ver[N],edge[N],tot;

 inline void add(int u,int v,int e){

     ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;

 }

 int col[N],id[N],f[][],g[];

 int vis[N],sum[N],n,m,k;

 queue<int> q;

 void spfa(int now){

     while(!q.empty()){

         int u=q.front();q.pop(),vis[u]=;

         for(int i=head[u];i;i=Next[i]){

             int v=ver[i];

             if(f[v][now]>f[u][now]+edge[i]){

                 f[v][now]=f[u][now]+edge[i];

                 if(!vis[v]) vis[v]=,q.push(v);

             }

         }

     }

 }

 int tmp[];

 bool check(int S){

     memset(tmp,,sizeof(tmp));

     for(int i=;i<=;++i)

     if(S&(<<i-)) ++tmp[col[i]];

     for(int i=;i<=;++i)

     if(tmp[i]&&tmp[i]!=sum[i]) return ;

     return ;

 }

 int main(){

 //    freopen("testdata.in","r",stdin);

     n=read(),m=read(),k=read();

     for(int i=;i<=m;++i){

         int u=read(),v=read(),e=read();

         add(u,v,e),add(v,u,e);

     }

     memset(f,0x3f,sizeof(f));

     memset(g,0x3f,sizeof(g));

     for(int i=;i<=k;++i)

     col[i]=read(),id[i]=read(),++sum[col[i]],f[id[i]][<<i-]=;

     int limit=(<<k)-;

     for(int S=;S<=limit;++S){

         for(int i=;i<=n;++i){

             for(int SS=S;SS;SS=(SS-)&S)

             cmin(f[i][S],f[i][SS]+f[i][S^SS]);

             q.push(i),vis[i]=;

         }

         spfa(S);

     }

     for(int S=;S<=limit;++S)

     for(int i=;i<=n;++i)

     cmin(g[S],f[i][S]);

     for(int S=;S<=limit;++S)

     if(check(S))

     for(int SS=S;SS;SS=(SS-)&S)

     if(check(SS))

     cmin(g[S],g[SS]+g[S^SS]);

     printf("%d\n",g[limit]);

     return ;

 }