[JLOI2015]管道连接

Time Limit: 30 Sec Memory Limit: 128 MB
[Submit][Status][Discuss]

Description

小铭铭最近进入了某情报部门，该部门正在被如何建立安全的通道连接困扰。

该部门有 n 个情报站，用 1 到 n 的整数编号。给出 m 对情报站 ui;vi 和费用 wi，表示情

报站 ui 和 vi 之间可以花费 wi 单位资源建立通道。

如果一个情报站经过若干个建立好的通道可以到达另外一个情报站，那么这两个情报站就

建立了通道连接。形式化地，若 ui 和 vi 建立了通道，那么它们建立了通道连接；若 ui 和 vi 均

与 ti 建立了通道连接，那么 ui 和 vi 也建立了通道连接。

现在在所有的情报站中，有 p 个重要情报站，其中每个情报站有一个特定的频道。小铭铭

面临的问题是，需要花费最少的资源，使得任意相同频道的情报站之间都建立通道连接。

Input

第一行包含三个整数 n;m;p，表示情报站的数量，可以建立的通道数量和重要情报站的数

量。接下来 m 行，每行包含三个整数 ui;vi;wi，表示可以建立的通道。最后有 p 行，每行包含

两个整数 ci;di，表示重要情报站的频道和情报站的编号。

Output

输出一行一个整数，表示任意相同频道的情报站之间都建立通道连接所花费的最少资源总量。

Sample Input

5 8 4
1 2 3
1 3 2
1 5 1
2 4 2
2 5 1
3 4 3
3 5 1
4 5 1
1 1
1 2
2 3
2 4

Sample Output

HINT

选择 (1; 5); (3; 5); (2; 5); (4; 5) 这 4 对情报站连接。

对于 100% 的数据，0 <ci <= p <= 10; 0 <ui;vi;di <= n <= 1000; 0 <= m <= 3000; 0 <= wi <=

20000。

斯坦纳森林

处理许多颗斯坦纳树，最后合并

合并时向判断状态是否合法，即是否能使频道相同的联通

问题：问什么判断的时候，当前状态与合法状态没有交集也算合法状态？

 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<queue>
using namespace std;
const int maxn=1010;
int n,m,p,oo;
int front[maxn],tot;
int to[20010],nxt[20010],w[20010];
int g[1050],f[maxn][1050],c[maxn],d[maxn];
int bin[maxn];
bool v[maxn];
queue<int>q;
void add(int u,int v,int va)
{
    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; w[tot]=va;
    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; w[tot]=va;
}
void read(int &x)
{
    x=0; char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); }
}
void spfa(int st)
{
    int now;
    while(!q.empty())
    {
        now=q.front(); q.pop(); 
        for(int i=front[now];i;i=nxt[i])
        {
            if(f[to[i]][st]>f[now][st]+w[i])
            {
                f[to[i]][st]=f[now][st]+w[i];
                if(!v[to[i]]) q.push(to[i]),v[to[i]]=true;
            }
        }
        v[now]=false;
    }
}
bool check(int S)
{
    int now;
    for(int i=1;i<=p;i++)
    {
        now=S&bin[i];
        if(!now || now==bin[i]) continue;
        return false;
    }
    return true;
}
int main()
{
    int u,vv,w;
    read(n); read(m); read(p);
    while(m--)
    {
        scanf("%d%d%d",&u,&vv,&w);
        add(u,vv,w);
    }
    for(int i=1;i<=p;i++) scanf("%d%d",&c[i],&d[i]);
    for(int i=1;i<=p;i++)
     for(int j=1;j<=p;j++)
      if(c[j]==c[i]) bin[i]|=(1<<j-1);
    memset(g,0x3f,sizeof(g));
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=p;i++) f[d[i]][1<<i-1]=0; oo=g[0];
    for(int S=1;S<(1<<p);S++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int T=S-1;T;T=(T-1)&S)
              f[i][S]=min(f[i][S],f[i][T]+f[i][S^T]);
            if(f[i][S]<oo) q.push(i),v[i]=true;          
        }
        spfa(S);
        if(!check(S)) continue;
        for(int i=1;i<=n;i++) g[S]=min(g[S],f[i][S]);
        for(int T=S-1;T;T=(T-1)&S) g[S]=min(g[S],g[T]+g[S^T]);
    }
    printf("%d
",g[(1<<p)-1]);
}