惠州建站模板,wordpress更换主题帖子封面不显示,宁波今晨发现1例阳性,千锋教育培训机构就业率正题 题目大意
给出nnn个点nk−1nk-1nk−1条边的一张图#xff0c;求有多少种删除若干条边的方案使得图依旧联通。 1≤n≤105,1≤k≤101\leq n\leq 10^5,1\leq k\leq 101≤n≤105,1≤k≤10 解题思路
注意到kkk很小#xff0c;我们考虑先搞出一棵dfsdfsdfs树然后剩下的做非树…正题 题目大意
给出nnn个点nk−1nk-1nk−1条边的一张图求有多少种删除若干条边的方案使得图依旧联通。
1≤n≤105,1≤k≤101\leq n\leq 10^5,1\leq k\leq 101≤n≤105,1≤k≤10 解题思路
注意到kkk很小我们考虑先搞出一棵dfsdfsdfs树然后剩下的做非树边。
这里有个结论是我们将第iii条非树边权值定为2i2^i2i树边权值定义为覆盖了它的非树边的权值的异或和那么删除边集SSS后图不连通的充要条件就是存在一个子集异或和为000。
感性理解一下如果一个边集异或和为000显然边集内肯定有树边考虑一条非树边如果没有显然是会被分割的它如果跨过偶数条被删的边那么中间如果有被删除的树边就会被分割出中间的连通块如果它跨过奇数条被删除的树边那么显然它也要被删除无法连接两个连通块。
然后考虑一张被删除后不连通的图我们将边集中连接原本两个连通块的边拿出来如果只有树边显然这个树边的权值为000如果有非树边那么中间被删除的树边也会异或上这个权值所以异或和还是为000。
这样充分性和必要性就证明完了。
至于做法我们得到所有边的权值那么显然权值种类不会超过3k3k3k种我们直接爆搜每种权值选不选用线性基求解就好了。 code
#includecstdio
#includecstring
#includealgorithm
#includevector
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N1e510;
const int P998244353;
struct node{int to,next,w ;
}a[N1];
int n,k,tot,m,ls[N],dep[N],c[N],w[N],ans,d[90];
bool v[N];
vectorpairint,int f;
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x,int fa){v[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(i(fa^1)||a[i].w)continue;if(v[y]){a[i].wa[i^1].w1;w[x]^(1m);w[y]^(1m);c[1m];m;}else dfs(y,i);}return;
}
void build(int x,int fa){for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa||a[i].w)continue;build(y,x);w[x]^w[y];}if(fa)c[w[x]];return;
}
void calc(int dep,int r){if(depf.size()){(ansr)%P;return;}int xf[dep].first,p-1;calc(dep1,r);for(int im-1;i0;i--)if((xi)1){if(d[i])x^d[i];else {pi;break;} }if(x){d[p]x;calc(dep1,1ll*r*f[dep].second%P);d[p]0;}
}
int main()
{freopen(connected.in,r,stdin);freopen(connected.out,w,stdout);scanf(%d%d,n,k);tot1;for(int i1;ink;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);} dfs(1,0);build(1,0);for(int i1;i(1m);i)if(c[i])f.push_back(mp(i,c[i]));calc(0,1);printf(%d\n,ans);return 0;
}
