原题链接: P3623 [APIO2008] 免费道路 https://www.luogu.org/problemnew/show/P3623
题意
给定一个图 (不一定连通), 上面有 $m$ 条 $0$ 边和 $1$ 边.
要求选边使图连通,$0$ 边的数量必须等于 $k$.
分析
一开始用很天真的想法加边: 先加鹅卵石路, 一直加到 $k$ 条. 然后再加水泥路, 加到满.
然后发现在洛谷上 WA 了一个点.
仔细分析一下问题: 一对点, 如果我们加的是鹅卵石路, 那么我们本可以用水泥路使这一对点连通, 我们现在却使用了一次鹅卵石名额, 这样子可能会导致后面鹅卵石名额不足.
那么怎么考虑这个问题呢?
我们发现只有用鹅卵石代替了水泥才会导致名额的冲突, 那么我们只要求出有多少名额是必须给的 (不给就不能连通的), 然后优先给它们名额.
至于剩下的, 就先把鹅卵石的名额加到 $k$, 然后再加水泥路加到满就可以了.
代码
- #include <bits/stdc++.h>
- using namespace std;
- const int N=2e5+1000,M=3e5+1000;
- struct edge{
- int x,y;
- }sn[M],er[M];
- int read(){
- char c;int num,f=1;
- while(c=getchar(),!isdigit(c))if(c=='-')f=-1;num=c-'0';
- while(c=getchar(), isdigit(c))num=num*10+c-'0';
- return f*num;
- }
- int n,m,k,pre[N];
- int tot1=0,tot2=0,ans=0;
- int pt[M][4],vis[M];
- int fid(int x){return (x==pre[x])?x:(pre[x]=fid(pre[x]));}
- int main()
- {
- n=read();m=read();
- k=read();
- for(int i=1;i<=m;i++){
- int u,v,w;
- u=read();v=read();
- w=read();
- if(w==1){
- sn[++tot1].x=u;
- sn[ tot1].y=v;
- }else{
- er[++tot2].x=u;
- er[ tot2].y=v;
- }
- }
- if(tot2<k)goto no;
- int tt=0;
- for(int i=1;i<=n;i++)pre[i]=i;
- for(int i=1;i<=tot1;i++){
- if(fid(sn[i].x)!=fid(sn[i].y)){
- pre[fid(sn[i].x)]=fid(sn[i].y);
- tt++;
- }
- }
- int num=0;
- for(int i=1;i<=tot2;i++){
- if(fid(er[i].x)!=fid(er[i].y)){
- pre[fid(er[i].x)]=fid(er[i].y);
- vis[i]=1;
- num++;tt++;
- }
- }
- if(tt<n-1||num>k)goto no;
- for(int i=1;i<=n;i++)pre[i]=i;
- for(int i=1;i<=tot2;i++){
- if(vis[i]){
- pre[fid(er[i].x)]=fid(er[i].y);
- pt[++ans][1]=er[i].x;
- pt[ ans][2]=er[i].y;
- pt[ ans][3]=0;
- if(ans==k)break;
- }
- }
- for(int i=1;i<=tot2;i++){
- if(vis[i])continue;
- if(fid(er[i].x)!=fid(er[i].y)){
- pre[fid(er[i].x)]=fid(er[i].y);
- pt[++ans][1]=er[i].x;
- pt[ ans][2]=er[i].y;
- pt[ ans][3]=0;
- if(ans==k)break;
- }
- }
- if(ans<k)goto no;
- for(int i=1;i<=tot1;i++){
- if(fid(sn[i].x)!=fid(sn[i].y)){
- pre[fid(sn[i].x)]=fid(sn[i].y);
- pt[++ans][1]=sn[i].x;
- pt[ ans][2]=sn[i].y;
- pt[ ans][3]=1;
- if(ans==n-1)break;
- }
- }
- if(ans<n-1)goto no;
- for(int i=1;i<=ans;i++)
- printf("%d %d %d\n",pt[i][1],pt[i][2],pt[i][3]);
- return 0;
- no:
- printf("no solution\n");
- return 0;
- }
- View Code
[luogu]P3623 [APIO2008] 免费道路
来源: http://www.bubuko.com/infodetail-2862618.html