今天的图论题略多
但好像都是noip题
bzoj3624
有一个图，边是黑色或者白色，求一个生成树满足恰好有k条白边
贪心
我们把最小生成树上的白边叫做“富家子弟”，把不在树上的叫“贫下中农”
很明显，如果富家子弟超过k个，无解
否则我们先记录富家子弟，然后加入若干贫下中农直至有k条白边
然后加入剩下的黑边让图连通即可
bzoj4596
一个不超过17个点的无重边无自环的图
每个公司可以建一个集合里的边
一共n个点n个公司
求一个生成树满足这n-1个点分别由n-1个公司建成
矩阵树板子题
考虑容斥原理
答案为
[最小生成树的数量]-[一个公司没有建的数量]+[两个公司没有建的数量] ...
二进制枚举一下就可以了，毕竟17
bzoj3007
一个$r imes c$的矩形
从$(1,1)$走一条路径到$(r,c)$
这个矩形里有n个boss，你的路径要满足离boss的最近距离最远
$n leq 3000$
首先，根据题目描述我们可以二分答案/滑稽
我们二分到一个mid就是以所有boss为圆心，mid为半径画一个圆
用最小割思想建出对偶图（反向对偶¿
原图矩形左下到右上连通等价于对偶图里左下到右上不连通
我们用画出的圆做一下noip2017D2T1的并查集就可以了
（我没见过自己鞭尸自己的
#include <iostream> #include <cstdio> #include <cctype> using namespace std; const int maxn = 20020; const int maxm = 100010; int n, m, k, fa[maxn], cnt0, cnt1, num; bool chs[maxm]; struct edge { int u, v, c; } e[maxm]; inline int read() { int x=0,f=1;char ch; for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f=-f; for(;isdigit(ch);ch=getchar())x=10*x+ch-'0'; return x*f; } int find(int u) { return fa[u] == u ? u : fa[u] = find(fa[u]); } int main() { n = read(); m = read(); k = read(); for (int i = 1; i <= n; i++) fa[i] = i; for (int i = 1; i <= m; i++) { e[i].u = read(); e[i].v = read(); e[i].c = read(); } for (int i = 1; i <= m; i++) { if (e[i].c == 1) { int r1 = find(e[i].u); int r2 = find(e[i].v); if (r1 != r2) { fa[r1] = r2; ++cnt1; } } } for (int i = 1; i <= m; i++) { if (e[i].c == 0) { int r1 = find(e[i].u); int r2 = find(e[i].v); if (r1 != r2) { chs[i] = 1; fa[r1] = r2; ++cnt0; } } } if (cnt0 + cnt1 != n - 1 || cnt0 > k) { printf("no solution "); return 0; } for (int i = 1; i <= n; i++) fa[i] = i; cnt0 = cnt1 = 0; for (int i = 1; i <= m; i++) { if (chs[i]) { int r1 = find(e[i].u); int r2 = find(e[i].v); if (r1 != r2) { fa[r1] = r2; ++cnt0; } } } for (int i = 1; i <= m; i++) { if (e[i].c == 0 && cnt0 < k) { int r1 = find(e[i].u); int r2 = find(e[i].v); if (r1 != r2) { chs[i] = 1; fa[r1] = r2; ++cnt0; } } } if (cnt0 != k) { printf("no solution "); return 0; } for (int i = 1; i <= m; i++) { if (e[i].c == 1) { int r1 = find(e[i].u); int r2 = find(e[i].v); if (r1 != r2) { chs[i] = 1; fa[r1] = r2; } } } for (int i = 1; i <= m; i++) if (chs[i]) printf("%d %d %d ", e[i].u, e[i].v, e[i].c); return 0; }
#include<bits/stdc++.h> #define LL LL using namespace std; const int N=405,M=25; const int mod=1e9+7; struct node{int x,y;}t[M][N]; LL C[M][M];int m[M]; LL Guass(int n) { LL ans=1; for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { LL a=C[i][i],b=C[j][i]; while(b) { LL temp=a/b;a%=b;swap(a,b); for(int k=i;k<=n;k++) C[i][k]=(C[i][k]-temp*C[j][k]%mod+mod)%mod,swap(C[i][k],C[j][k]); ans=-ans; } } if(!C[i][i]) return 0; ans=ans*C[i][i]%mod; } ans=(ans%mod+mod)%mod; return ans; } int main() { int n;scanf("%d",&n); for(int i=1;i<n;i++) { scanf("%d",&m[i]); for(int j=1;j<=m[i];j++) scanf("%d%d",&t[i][j].x,&t[i][j].y); } LL ans=0; for(int i=0;i<(1<<n-1);i++) { memset(C,0,sizeof(C)); int num=0; for(int j=1;j<n;j++) { if(!(i&(1<<j-1))) continue; num++; for(int k=1;k<=m[j];k++) { int a=t[j][k].x,b=t[j][k].y; C[a][b]--;C[b][a]--; C[a][a]++;C[b][b]++; } } if((n-1-num)%2) ans-=Guass(n-1); else ans+=Guass(n-1); ans=(ans%mod+mod)%mod; } printf("%lld ",ans); return 0; }
#include <bits/stdc++.h> #define N 3010 using namespace std; int f[N]; double x[N] , y[N]; int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); } void merge(int x , int y) { int tx = find(x) , ty = find(y); if(tx != ty) f[tx] = ty; } int main() { int n , i , j , cnt = 60; double a , b , l = 0 , r , mid; scanf("%d%lf%lf" , &n , &a , &b) , r = min(a , b); for(i = 1 ; i <= n ; i ++ ) scanf("%lf%lf" , &x[i] , &y[i]); while(cnt -- ) { mid = (l + r) / 2; for(i = 0 ; i <= n + 1 ; i ++ ) f[i] = i; for(i = 1 ; i <= n ; i ++ ) { if(mid >= x[i] - 1 || mid >= b - y[i]) merge(i , 0); if(mid >= a - x[i] || mid >= y[i] - 1) merge(i , n + 1); for(j = 1 ; j < i ; j ++ ) if((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) <= 4 * mid * mid) merge(i , j); } if(find(0) == find(n + 1)) r = mid; else l = mid; } printf("%.2lf " , l); return 0; }