[洛谷 3623][APIO2008]免费道路

题目链接

https://www.luogu.org/problem/P3623

题解

容易看出本题的目标是构造一棵生成树，使得图中边权为 \(0\) 的边恰好有 \(k\) 条。

注意到有些 \(0\) 边是必须在树上的，有些则不是。

我们可以先尝试向生成树中加入所有 \(1\) 边，再尝试插入每一条 \(0\) 边，从而算出至少需要加入的 \(0\) 边数量。

如果至少加入的 \(0\) 边数量大于 \(k\)，则无解。

否则前一步插入的 \(0\) 边都将在最终的生成树当中出现。

我们重新跑一遍生成树，将上述的边插入后，我们再尝试将剩下的 \(0\) 边加入生成树中，直到有 \(k\) 条 \(0\) 边为止。

最后把 \(1\) 边插入生成树就可以得出结果了。

#include <cstdio>
#include <algorithm>
using namespace std;
struct edge
{
 int u,v,w;
}e[100005];
int fa[20005],res[100005];
bool cmp1(const edge&a,const edge&b)
{
 return a.w>b.w;
}
bool cmp2(const edge&a,const edge&b)
{
 return a.w<b.w;
}
int find(int x)
{
 return fa[x]==x?x:fa[x]=find(fa[x]);
}
void unionn(int x,int y)
{
 fa[x]=y;
}
int main()
{
 int n,m,k;
 scanf("%d%d%d",&n,&m,&k);
 for(int i=1;i<=m;i++)
  scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
 for(int i=1;i<=n;i++)
  fa[i]=i;
 sort(e+1,e+m+1,cmp1);
 int cnt=0;
 for(int i=1;i<=m;i++)
  if(find(e[i].u)!=find(e[i].v))
  {
   unionn(find(e[i].u),find(e[i].v));
   if(!e[i].w)cnt++,e[i].w=-1;
  }
 if(cnt>k)
 {
  puts("no solution");
  return 0;
 }
 for(int i=1;i<=n;i++)
  fa[i]=i;
 sort(e+1,e+m+1,cmp2);
 cnt=0;
 for(int i=1;i<=m;i++)
 if(find(e[i].u)!=find(e[i].v))
  {
   if(e[i].w!=1)
   {
    if(k)k--;
    else continue;
   }
   unionn(find(e[i].u),find(e[i].v));
   res[++cnt]=i;
   if(e[i].w==-1)e[i].w=0;
   if(cnt==n-1)break;
  }
 if(cnt<n-1||k)
 {
  puts("no solution");
  return 0;
 }
 for(int i=1;i<n;i++)
  printf("%d %d %d\n",e[res[i]].u,e[res[i]].v,e[res[i]].w);
 return 0;
}