CodeForce D. Shichikuji and Power Grid 【错误记录】

题目链接

  假设用电线连接了若干个城市，那么这若干个城市构成的连通块中，我只需要在其中一个建立发电站即可，而且我肯定贪心的在 c [ i ] c[i] c[i]最小的城市建。
  其次如果某个城市 u u u 已经通电了，那么对于所有满足 d i s t [ u ] [ v ]   <   c [ v ] dist[u][v] < c[v] dist[u][v] < c[v]的城市 v v v，我选择从 u u u 连电线过去，而不是在 v v v 建发电站。（ d i s t [ i ] [ j ] dist[i][j] dist[i][j]就是题目说的牵电线的花费）
  然后就想到把 c [ i ] c[i] c[i]最小的城市 i i i 入队，然后每次取出队首元素，遍历其它城市，然后 i f ( d i s t [ c u r ] [ i ] < m i n _ c o s t [ i ] ) if( dist[cur][i] < min_cost[i] ) if(dist[cur][i]

	int cur = que.front(); que.pop();
    cnt--;
    if( prev[cur] == cur )station.push_back( cur );
    else wire.push_back( make_pair(prev[cur],cur) );
    ans += min_cost[cur];
	// 遍历所有其它城市
    for(int i=1;i<=n;i++){
        if( i!=cur && dist[cur][i] < min_cost[i] ){
            // printf("%d -> %dn",cur,i);
            if( !vis[i] )que.push(i);
            vis[i] = true;
            min_cost[i] = dist[cur][i];
            prev[i] = cur;
        }
    }

 而如果当前队列为空，就在没通电的城市里找一个 c [ i ] c[i] c[i] 最小的，丢到队列里继续

	// 这部分代码在上面那个代码上面的位置
	if( que.empty() ){
 	     int u = -1; long long Min = INFq;
         for(int i=1;i<=n;i++){
             if( !vis[i] && min_cost[i] < Min ){
                 Min = min_cost[i];
                 u = i;
             }
         }
         vis[u] = true;
         que.push(u);
         prev[u] = u;
     }

然后WA13？？

看了题解代码后想了下发现了盲点：

4
1 2
2 2
1 1
2 1
1 100 2 100
25 25 1 25

这个数据我原来的代码输出的是

103
2
1 3
2
1 2
2 4

 开始城市1入队，然后更新城市2，然后城市2更新4。
 接下来队列为空。城市3的 c [ i ] c[i] c[i]最小，建一个发电站。over。
 所以说写的很像MST时就应该注意到这一点了，虽然遍历时是有更新的 m i n c o s t [ i ] = d i s t [ c u r ] [ i ] ; min_cost[i] = dist[cur][i]; minc​ost[i]=dist[cur][i]; 这一步，但是要保证每次用来更新的点都是当前所有点中 m i n _ c o s t min_cost min_cost最小的，这个点不一定是队首元素。

	if( i!=cur && dist[cur][i] < min_cost[i] ){
         if( !vis[i] )que.push(i);
         vis[i] = true;
         min_cost[i] = dist[cur][i];
         prev[i] = cur;
     }

 所以按照MST的写法每次遍历所有没通电的城市找 m i n _ c o s t min_cost min_cost 最小的城市才是正确的。