SDOJ 3742 黑白图

【描述】

一个 n 个点 m 条边构成的无向带权图。由一些黑点与白点构成树现在每个白点都要与他距离最近的黑点通过最短路连接（如果有很多个，可以选取其中任意一个），我们想要使得花费的代价最小。请问这个最小代价是多少？注意：最后选出的边保证每个白点到黑点的距离任然是最短距离。

【输入】

第一行两个整数 n，m；第二行 n 个整数，0 表示白点，1 表示黑点；接下来 m 行，每行三个整数 x，y，z，表示一条连接 x 和 y 点，权值为 z 的边。

【输出】

如果无解，输出 impossible；否则，输出最小代价。

【输入样例】

5 7 0 1 0 1 0 1 2 11 1 3 1 1 5 17 2 3 1 3 5 18 4 5 3 2 4 5

【输出样例】

【样例说明】

选 2、4、6 三条边；

【数据范围】

对 30%的输入数据： 1≤n≤10， 1≤m≤20；对 100%的输入数据：1≤n≤100000，1≤m≤200000，1≤z≤1000000000

------------------------------------------------------------------------------------------------

这道题有两个关键点，一是距离最近的黑点，一是价值最小。

对于距离最近，我们可以建立一个超级汇点，汇点用零边连接每个黑点，然后从汇点开始跑最短路。

因为汇点和黑点之间权值为0，所以汇点与白点之间跑出来的最短路是白点和黑点之间的最短路。

对于第二点，价值最小，我们已经得到了最短路径图、确定了距离白点最近的黑点，所以可以跑一个最小生成树，在确保图连通的情况下得到最小价值。

注：形成的最小生成树上的边不一定是白点到黑点最短距离的边，但可以肯定这个黑点是最优的，而且我们关注的是最小价值。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<queue>
  7 #define N 200100
  8 #define INF 0x3f
  9 using namespace std;
 10 long long n,m,ans=0;
 11 bool vis[N];
 12 long long dis[N];
 13 long long fa[N];
 14 struct node
 15 {
 16     long long u,v,w,nxt;
 17 }e[N*2],d[N*2];
 18 long long first[N],cnt,tot;
 19 void ade(long long u,long long v,long long w)
 20 {
 21     e[++cnt].nxt=first[u]; first[u]=cnt;
 22     e[cnt].u=u; e[cnt].v=v; e[cnt].w=w;
 23 }
 24 queue<long long>q;
 25 void spfa(long long x)
 26 {
 27     memset(dis,0x3f,sizeof(dis));
 28     memset(vis,true,sizeof(vis));
 29     q.push(x);
 30     dis[x]=0;
 31     while(!q.empty())
 32     {
 33         long long u=q.front(); q.pop();
 34         vis[u]=true;
 35         for(long long i=first[u];i;i=e[i].nxt)
 36         {
 37             long long v=e[i].v;
 38             if(dis[v]>dis[u]+e[i].w)
 39             {
 40                 dis[v]=dis[u]+e[i].w;
 41                 if(vis[v]==true)
 42                 {
 43                     q.push(v);
 44                     vis[v]=false;
 45                 }
 46             }
 47         }
 48     }
 49 }
 50 inline bool cmp(node a,node b)
 51 {
 52     return a.w<b.w;
 53 }
 54 long long la(long long x)
 55 {
 56     if(fa[x]!=x)  fa[x]=la(fa[x]);
 57     return fa[x];
 58 }
 59 void kruskal()
 60 {
 61     sort(e+1,e+tot+1,cmp);
 62     for(long long i=1;i<=n;i++) fa[i]=i;
 63     long long cnnt=n;
 64     for(long long i=1;i<=tot;i++)
 65     {
 66         if(!cnnt) break;
 67         long long x=la(d[i].u);
 68         long long y=la(d[i].v);
 69         if(x==y) continue;
 70         fa[x]=y;
 71         ans+=d[i].w;
 72         --cnnt;
 73     }
 74 }
 75 int main()
 76 {
 77     scanf("%lld%lld",&n,&m);
 78     for(long long i=1,x;i<=n;i++)
 79     {
 80         scanf("%lld",&x);
 81         if(x==1) ade(n+1,i,0);//ade(i,n+1,0);//建立汇点 
 82     }
 83     for(long long i=1;i<=m;i++)
 84     {
 85         long long x,y,z;
 86         scanf("%lld%lld%lld",&x,&y,&z);
 87         ade(x,y,z);ade(y,x,z);
 88     }
 89     spfa(n+1);
 90 //    for(long long i=1;i<=n;i++) cout<<dis[i]<<" ";
 91 //    cout<<endl;
 92     bool pu=0;
 93     for(long long i=1;i<=n;i++)
 94     {
 95         if(dis[i]==INF) pu=1; 
 96         for(long long j=first[i];j;j=e[j].nxt)//!!!!!!!!建立新最短路图 
 97             if(dis[e[j].v]==dis[i]+e[j].w) 
 98                 d[++tot].u=i,d[tot].v=e[j].v,d[tot].w=e[j].w;
 99     }
100 //    for(long long i=1;i<=tot;i++)
101 //        cout<<d[i].u<<" "<<d[i].v<<" "<<d[i].w<<endl;
102 //    cout<<endl;
103     if(pu==1)
104     {
105         printf("impossible
");
106         return 0;
107     }
108     kruskal();
109     if(ans==0)
110     {
111         printf("impossible
"); return 0;
112     }
113     printf("%lld
",ans);
114     return 0;
115 }