图论专题总结( 二 ) _图论

<='9'){a=a*10+ch-'0';ch=getchar();}return a*b;}void add(rint x,rint y){edge[++tot].to=y;edge[tot].nxt=head[x];head[x]=tot;}int find(rint x){if(fat[x]==x) return x;return fat[x]=find(fat[x]);}void get_dell(rint x,rint dex){bar[x]=dex;for(rint i=head[x];i;i=edge[i].nxt){rint y=edge[i].to;if(bar[y]==dex){++cnt;while(y!=x){dell[cnt].push_back(x);x=ac[x];}dell[cnt].push_back(y);}else ac[y]=x,get_dell(y,dex);}}void bfs(rint x,rint tp){d[x]=1,bl[x]=tp;q.push(x);while(!q.empty()){rint x=q.front();q.pop();for(rint i=head[x];i;i=edge[i].nxt){rint y=edge[i].to;if(!bar[y]&&!d[y]){bl[y]=tp;d[y]=d[x]+1;q.push(y);f[y][0]=x;for(rint j=1;j<=t;j++) f[y][j]=f[f[y][j-1]][j-1];}}}}int Lca(rint x,rint y){if(d[x]>d[y]) swap(x,y);for(rint i=t;i>=0;i--)if(d[f[y][i]]>=d[x]) y=f[y][i];if(x==y) return x;for(rint i=t;i>=0;i--){if(f[y][i]^f[x][i]){y=f[y][i];x=f[x][i];}}return f[x][0];}void solve(){for(rint i=1;i<=n;i++)if(!bar[i]) get_dell(i,++dex);memset(bar,0,sizeof(bar));for(rint i=1;i<=cnt;i++)for(rint j=0;jmax(ans3,ans4)) printf("%d %d\n",ans3,ans4);else{if(min(ans1,ans2)min(ans3,ans4)) printf("%d %d\n",ans3,ans4);else printf("%d %d\n",max(ans1,ans2),min(ans1,ans2));}}}return 0;}
View Code
：最小生成树+二分答案
被天皇忽悠说这道题贼恶心，去看题解（推锅推锅）然后1A掉不想说话。
不是特别好想。不过填了一种最小生成树题目的做题方法：通过改变边权来改变最小生成树的构成。
黑白边，要求need条白边。一开始sb的想成了树里只有白边。
显然还有n-1-need条黑边 /糊脸（n是节点数目）顺嘴吐槽：BZOJ上直接跑最小生成树都能过……
二分给白边加上边权，跑最小生成树，看是否符合need条白边。
直接暴力累计就好了没必要开优化（懒）还有人直接爆搜不二分都A了……
建议打二分咕咕咕～
#include#include#include#include#include#include#include#define rint register intusing namespace std;int n,m,need,l,r,cnt,tot,ans;int u[100005],v[100005],c[100005],col[100005];int fa[100005];struct node {int u,v,c,col;}edge[100005];inline int read(){int a=0,b=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')b=-1;ch=getchar();}while(ch>='0'&&ch<='9'){a=(a<<3)+(a<<1)+(ch-'0');ch=getchar();}return a*b;}inline bool cmp(node a,node b){return a.c==b.c?a.col=need)return 1;else return 0;}}int main(){n=read(),m=read(),need=read();for(rint i=1;i<=m;i++)u[i]=read()+1,v[i]=read()+1,c[i]=read(),col[i]=read();l=-101,r=101;while(l>1;if(kruskal(mid))l=mid+1,ans=tot-need*mid;else r=mid;}cout