解题：APIO 2008 免费道路

我们发现我们可以很容易知道最终完成的生成树中有多少鹅卵石路，但是我们不好得到这棵生成树的结构，所以我们尽量“谨慎”地完成生成树·，最好是一点点加到我们要达到的标准而不是通过删掉一些东西来完成

我们把水泥路视为权值为零，鹅卵石路视为权值为一，做最小生成树，这时加入在生成树里的鹅卵石路一定是必须加入的。再然后我们逆着做最小生成树做到恰好有$k$条鹅卵石路，然后用水泥路把图连通起来就好了

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=,M=;

 struct a

 {

     int n1,n2;

     int val,imp;

 }mst[M],outp[N];

 int aset[N],imp[N];

 int n,m,c,k,rd,cnt;

 bool cmp1(a x,a y)

 {

     return x.val<y.val;

 }

 bool cmp2(a x,a y)

 {

     return x.imp==y.imp?x.val>y.val:x.imp>y.imp;

 }

 int find(int x)

 {

     return x==aset[x]?x:aset[x]=find(aset[x]);

 }

 int main ()

 {

     scanf("%d%d%d",&n,&m,&k);

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

     {

         scanf("%d%d%d",&mst[i].n1,&mst[i].n2,&rd);

         mst[i].imp=false,mst[i].val=rd^;

     }

     for(int i=;i<=n;i++) aset[i]=i;

     sort(mst+,mst++m,cmp1);

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

     {

         int f1=find(mst[i].n1),f2=find(mst[i].n2);

         if(f1!=f2) aset[f1]=f2,mst[i].imp=mst[i].val;

     }

     for(int i=;i<=n;i++) aset[i]=i;

     sort(mst+,mst++m,cmp2);

     for(int i=;i<=m&&c<k;i++)

     {

         int f1=find(mst[i].n1),f2=find(mst[i].n2);

         if(f1!=f2) aset[f1]=f2,c+=mst[i].val,outp[++cnt]=mst[i];

     }

     sort(mst+,mst++m,cmp1);

     for(int i=;i<=m&&cnt<=n-;i++)

     {

         int f1=find(mst[i].n1),f2=find(mst[i].n2);

         if(f1!=f2) aset[f1]=f2,c+=mst[i].val,outp[++cnt]=mst[i];

     }

     if(c!=k) printf("no solution\n"),exit();

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

         printf("%d %d %d\n",outp[i].n1,outp[i].n2,outp[i].val^);

     return ;

 }

巴特西

解题：APIO 2008 免费道路

最新文章

热门文章