标签归档:dfs

hdu 6073 Matching In Multiplication

Problem Description

In the mathematical discipline of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V (that is, U and V are each independent sets) such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. A matching in a graph is a set of edges without common vertices. A perfect matching is a matching that each vertice is covered by an edge in the set.

Little Q misunderstands the definition of bipartite graph, he thinks the size of U is equal to the size of V, and for each vertex p in U, there are exactly two edges from p. Based on such weighted graph, he defines the weight of a perfect matching as the product of all the edges’ weight, and the weight of a graph is the sum of all the perfect matchings’ weight.

Please write a program to compute the weight of a weighted ”bipartite graph” made by Little Q.

 

Input

The first line of the input contains an integer T(1T15), denoting the number of test cases.

In each test case, there is an integer n(1n300000) in the first line, denoting the size of U. The vertex in U and V are labeled by 1,2,...,n.

For the next n lines, each line contains 4 integers vi,1,wi,1,vi,2,wi,2(1vi,jn,1wi,j109), denoting there is an edge between Ui and Vvi,1, weighted wi,1, and there is another edge between Ui and Vvi,2, weighted wi,2.

It is guaranteed that each graph has at least one perfect matchings, and there are at most one edge between every pair of vertex.

 

Output
For each test case, print a single line containing an integer, denoting the weight of the given graph. Since the answer may be very large, please print the answer modulo 998244353.

 

Sample Input
1
2
2 1 1 4
1 4 2 3

 

Sample Output
16
题目定义了一种“二分图”,U和V两边集合点数相等且U中每个点只有两条边均和V中点相连。
那么这个图就是若干个环套树组成的。而且分析一下可以知道一定是偶环和偶链,且环和链的公共节点一定是V中的。
而每个环都有两种选择方案可以认为是a1和a2,而链上只有一种选择方案。所以答案就是若干个(a1+a2)*c的乘积。直接把环抠出来,然后在按照类似于拓扑序的关系处理链上的情况。至于为什么要考虑拓扑序,因为链可能是多个链交叉而成的,那么这个多叉的公共点一定是V中的点,我们只能在一条链上选一条边和他匹配,否则就会乱掉。比赛的时候就是因为没考虑需要做拓扑序的处理链的情况而错了。

 

“玲珑杯”ACM比赛 Round #18做题记录

这场比赛感觉题目较为简单,但是体验较差。主要是评测机崩掉了,然后莫名延时莫名突然结束,算了,按照qwertier大爷的口头禅:“这都无所谓了,反正你那么垃圾早过一个题又能怎样?”

A — 计算几何你瞎暴力

题意:略。

因为坐标范围较小,最多也就一千多个,所以暴力枚举然后统计一个关于距离的前缀和就好了。但是因为我一开始的脑子进水了,居然调了很久。

B — 数论你还会快速幂

题意:给出\(n\),\(p\),\(k\),范围都是\(10^{18}\),并且保证\(0 \leq n-p \leq 100\)。求\(\sum_{i=1}^{n}i^{k} \mod p\)

我是打表找规律,首先大于p的幂和不会超过100项所以选择直接暴力。那么转化成我们要求这么一个东西\(\sum_{i=1}^{p}i^{k} \mod p\)。那么当k为奇数的时候这部分一定是0.但是偶数的部分我不知道,所以选择打表,发现也是0。。。。当然,当k时p-1倍数的话,这一坨是p-1,根据费马小定理。。。所以说我们直接从p算到n求个快速幂就可以了,为什么要从p呢?因为会有k=0的情况,这时候\(p^{k} \mod p=1\)。机房几位大爷比我先发现这个规律,但是貌似就是因为这个坑,没我A的早。。。但是A了以后还是把我踩爆。。。

至于正解貌似是从原根角度证明的。。。我连原根是啥都不知道,贴个链接好了:链接

C — 图论你先敲完模板

题意:略。

和开火车的一道煞笔题一样的思想,就是随着距离增大增长是指数级的,这也就意味着当两个点距离过大的时候肯定分段比不分段优秀。。。所以\(n^2\)的dp就可以优化到\(nlogn\)

D — 最后你还是AK了

题意:略。

一开始以为是求一种分配方案让最长路径上的值最大,不会做。。。最后还剩半个小时才听闻原来是求sum最大。然后写完突然又告诉我比赛结束了。。。

那么每条边被经历的次数一定是他两个端点\(u\),\(v\)的子树大小中的最小值。所以我们可以先求出来每条边被经历了多少次,再考虑如何让路径和最大。那么自然是给经历次数最多的边次多的边依次加最大的变化,次大的变化这样的。。。。

所以就是dfs完成后,排序贪心。

E — 数据结构你干瞪眼啊

题意:给出一个\(n*m\)的矩阵,\(n*m<=100000\),每个值在\([0,255]\)的范围内。有\(q\)次操作。

(1)询问某个格子的值

(2) 询问某一行一段区间有多少种不同的值。

(3)某一行区间加一个数并且模256

(4)某一行区间翻转

比赛的时候看到了\(n*m<=100000\)的条件,但是因为下意识的想的是二维数据结构,或者什么东西套个分块之类的。。。觉得自己的码力根本没法写。。。。简直傻逼透顶。。。

其实直接当成区间操作就好了,然后splay随便做,维护一个256位的bitset的标记记录一下子树都有哪些值即可。如果没有区间翻转直接线段树就可以了。

 

Codeforces Round #408 (Div. 2)做题记录

A. Buying A House

题意:略。

扫一遍好了。

B. Find The Bone

题意:略。

模拟一下好了。注意特判第一个是洞的情况。

C. Bank Hacking

题意:给出一个n个点的树,每次砍掉一个点可以让和他相连的点+1,孙子点+2(但是儿子节点必须存在)。问在这个过程中点权的最大值是多大。

发现最大值要么是一开始的最大值,最大值+1,最大值+2中的一个。所以枚举一下所有点好啦,在这个过程中用两个set维护一下好了。大概是\(O(nlogn)\)吧。。。

D. Police Stations

题意:给出一颗树让删除最多的边,使得所有点到关键点的距离都小于等于d。

考虑bfs,从所有的关键点开始bfs。因为题目保证有解,所以每个点都可以在d步内被关键点抵达。需要删除的边一定是某个关键点u可以通过一条边到v但是v已经被别的关键点访问过了,所以这个边需要删去。

不可以dfs!!!因为dfs走d步,是盲目性的,对于某个点来说关键点到他的路径不一定是最短的,那么会出现反例的,比如删边后发现有的点到达别的点距离大于d了。。。而bfs走的一定是最短路径,最短路径一定保证解不会更差。所以bfs才可以。。。

E. Exam Cheating

题意:现在有n个题目,你有p次机会看左右两个人,每次可以抄连续k道题目,告诉你每个人会的题目,最多可以做对多少道题目。\(n \leq 1000,p \leq 1000,k\leq min(50,n)\)

感觉和之前gym里一个抽牌的题目很像。考虑\(dp[i][j][k][l]\)代表现在做到第\(i\)题,已经用了\(j\)次机会,\(k\)表示在左边的人在这次机会中还剩多少道可以让你抄,\(l\)是指右边的。

那么对于对于第\(i\)道题目,如果我不使用新的机会,假如我现在还可以看左边的或者右边的题目也就是\(k>0\)或者\(l>0\),那么就是左边和右边人是否能答对就可以了。那么\(dp[i][j][k-1][l-1]=max(dp[i][j][k-1][l-1],dp[i-1][j][k][l]+((k&&a[i])||(l&&b[i]))\)。

假如我使用机会的话,就需要分左右两边考虑了。dp过程与上面的类似分析一下就可以了。。。

但是这样时间复杂度和空间复杂度都爆炸了。。。空间可以滚动数组,时间优化的话就是发现,每条线段上的n个点,每次覆盖k个点,一定可以通过\(ceil(n/k)\)次覆盖完全。所以时间复杂度为\(O(n*2*ceil(n/k)*k^{2})\)就可以了。