Codeforces 847J Students Initiation 二分答案 最大流

Codeforce 847J Students Initiation

题意

给一个包含$n$($n \leq 5000$)个点的无向图,边的条数$m \leq 5000$,没有重边自环。现在给每条边一个方向,问每个点的出度的最大值,最小为多少。输出这个最小值,并输出方案。

思路&建图

  1. 看到最大值最小,最小值最大,首先想到炸天哥猜想:二分!!
  2. 二分这个最大值$mid$,检验这个猜测值是否满足要求
  3. 从源点相这$n$个点引一条边,容量为$mid$。
  4. 对于第$i$条边来说,其编号为$n+i$,从其两个断点分别引一条边到这个点,容量为$1$。再从这个点到汇点连一条边,容量为$1$。
  5. 跑最大流,如果最大流和边的数目相同,即这个猜测值可行。此时,对于每一条边对应的点来说,这条边的方向就应该是从[流量来的那个点]到[没有流量流过来的那个点]。

代码

 

 

HDU 6214 Smallest Minimum Cut 最小割的割边的数目最少

Smallest Minimum Cut

题意

给一个有向的网络图,每条边有一定的容量$w_i$,现在以$1$点为源点,$n$点为汇点。求一组最小割的割边,使边的数目最少,输出最少数目。

建图&思路

直接按照原网络建图,只是边的容量改变为$10000 * w_i +1$,其中边的条数$m<10000$。这样跑最大流(最小割)后,假设最大流为$flow$,那么$flow / 10000$就是原始网络的最大流(最小割),$flow \mod 10000$就是最小割的最少边的条数。

代码

 

计蒜客 Our Journey of Dalian Ends 费用流找最短路

Our Journey of Dalian Ends

题意

给一个无向图,有边权,每个点用地名字符串表示。现在要从大连出发到达西安,并且必须经过上海,且给个点只能经过一次,问最短路径。

建图&思路

  1. 可以认为是找两条路径,起点都是上海,分别到达西安和大连,且经过的点不能重复,求路径和的最小长度。
  2. 将每个点拆点,拆分为入点和出点,入点向出点连一条边,容量为$1$,费用为$0$,代表这个点只能经过一次。
  3. 对于原图上的点,从一个城市的出点连一条边,到另一个城市所代表的点的入点。容量为$1$,费用为这条边的边权。反过来也需要连一条边,代表双向可行。
  4. 从源点向上海的出点连一条边,容量为$2$,费用为$0$,代表需要找到两条路径。
  5. 从西安和大连的出点,分别引一条边到汇点,容量为$1$,费用为$0$,代表只能是以这两个点为终点。
  6. 跑费用流,如果流量为2,那么费用就是两条路径的最短长度。
  7. 当然,如果输入数据中没有这三个城市,直接不行啊!

代码

 

 

Codeforces 546E Soldier and Traveling 最大流找可行方案

Codeforces 546E

题意

一个国家有$n$个城市,由$m$条双向边连接。现在,每个城市有$a_i$个士兵。现在每个士兵可以沿着一条边,走到相邻的城市,并且只能走一次,或者不走,留在原来的城市。问能否达到每个城市分别有$b_i$的士兵。切每条道路有一个上限,通过的士兵的个数不能超过这个上限。

  • 如果可以,输出"YES"。并输出方案,用矩阵$A_{ij}$表示从$i$城市走到$j$城市的士兵的个数。
  • 如果不可以,输出"NO"。

建图&思路

  1. 左边$n$个点,从源点往分别这$n$个点引一条边,容量为$a_i$。
  2. 右边$n$个点,从这个$n$个点分别往汇点引一条边,容量为$b_i$。
  3. 对于每一个城市$i$来说,从左边的第$i$个点向右边的第$i$个点引一条边,容量为$INF$,表示允许驻留。
  4. 对于每一条路来说,它的两个断点分别为$st,en$,那么需要从左边的第$st$个点引一条边到右边的第$en$个点,容量为这条路的上限。同时,从左边的第$en$个点引一条边到右边的第$st$个点,容量为这条路的上限。表示这两个城市之间的士兵可以相互移动,数量的上限不超过路的上限。
  5. 跑最大流,得到最大流量为$flow$,如果$flow$和士兵的总数相同,那么就有可行方案。否则没有。
  6. 对于每一个左边的点,枚举每一条向右边连的边,那么从这个点对应的城市到所连的点的城市所移动的士兵的个数,就是这条边所流过的流量,即这条边反向边的残余流量。

代码

注释

这个代码是2015年写的isap模板,所以不怎么好看。

Codeforces 863F 费用流求最小花费方案

Codeforces 863F

题意

  • 构造一个长度为$n$的序列$a_i$($1 \leq n \leq 50, 1 \leq a_i \leq n$),需要满足$q$个条件($0 \leq q \leq 100$)
  • 对于每一个条件,有一下两种可能
    1 $l_i,r_i,v_i$,对于所有满足$l_i \leq x \leq r_i$的下标$x$,有$a_x \geq v_i$
    2 $l_i,r_i,v_i$,对于所有满足$l_i \leq x \leq r_i$的下标$x$,有$a_x \leq v_i$
  • 构造出该序列的花费$cost = \sum_{i=1}^{n}cnt(i)^2$,其中$cnt(i)$为数$i$在构造的序列中出现的次数,求最小的花费。

建图

  • 先确定每个位置能填的数的范围,如果范围非法,可直输出$-1$并结束
  • 左边$n$个点,分别代表$1~n$这$n$个位置上的数,从源点引一条边,到左边的每一个点,容量为$1$,费用为$0$。
  • 右边也有$n$个点,分别代表填写的数。对于每个点,向汇点引$n$条边,第$j$条边的容量为$1$,费用为$j^2-(j-1)^2$。
  • 对于左边的每个点,向范围内的数对应的右边的数连边,容量为$1$,费用为$0$。
  • 由于费用流会优先使用费用较小的边,所以对于一个单独的数对应的右边的点来说,他向汇点的边的,只会使用前几条,这几条边的费用加起来正好是通过这个点的流量的平方,满足题目要求。
  • 跑费用流,即可解决问题。

代码

 

CodeForces 818G 费用流 优化建图

CodeForces 818G

题意

给定一个长度为$n$的序列$a_i$,$4 \leq n \leq 3000,1 \leq a_i \leq 10^5$,从中选出$4$个不想交的子序列,满足每个子序列中相邻的两个项,要么是差的绝对值为$1$,要么他们模$7$的结果相同。问这四个序列的总长度最长为多少。


思路

  • 对于每个项来说,将其看成一个点,将其拆点为为$i$和$i+n$,从$i$向$i+n$引一条边,容量为$1$,费用为$-1$,表示该点项只能被选一次,且选了之后收益$+1$。这一对点的流量方向,一定为从$i$进,并且从$i+n$出。
  • 对于每个项来说,都有可能作为子序列的起点或者终点。所以,从源点引一条边到$i$点,容量为$1$,费用为$0$;再从$i+n$点引一条边到汇点,容量为$1$,费用为$0$。
  • 对于每一个可能相邻的项$a_i,a_j$且$i \lt j$来说,需要建一条边从$i+n$到$j$,容量为$1$,费用为$-1$。但是这样建边之后,会发现边很多,根本跑不过。其实会发现,对于每一类相邻来说,只需要往后找到四个是同类的并建边就好了。
  • 从源点压入$4$点流量,跑费用流即可,答案为最小费用的相反数。

代码

HDU 4871 Shortest-path tree 最短路生成树 树上点分治

Shortest-path tree

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 130712/130712 K (Java/Others)

Problem Description

Given a connected, undirected graph G, a shortest-path tree rooted at vertex v is a spanning tree T of G, such that the path distance from root v to any other vertex u in T is the shortest path distance from v to u in G.
We may construct a shortest-path tree using the following method:
We consider a shortest-path tree rooted at node 1. For every node i in the graph G, we choose a shortest path from root to i. If there are many shortest paths from root to i, we choose the one that the sequence of passing nodes' number is lexicographically minimum. All edges on the paths that we chose form a shortest-path tree.
Now we want to know how long are the longest simple paths which contain K nodes in the shortest-path tree and how many these paths? Two simple paths are different if the sets of nodes they go through are different.

Input

The first line has a number T (T <= 10), indicating the number of test cases.
For each test case, the first line contains three integers n, m, k(1<=n<=30000,1<=m<=60000,2<=k<=n), denote the number of nodes, the number of edges and the nodes of required paths.
Then next m lines, each lines contains three integers a, b, c(1<=a, b<=n, 1<=c<=10000),denote there is an edge between a, b and length is c.

Output

For each case, output two numbers, denote the length of required paths and the numbers of required paths.

Sample Input

1
6 6 4
1 2 1
2 3 1
3 4 1
2 5 1
3 6 1
5 6 1

Sample Output

3 4

Author

FZU

Source

 
 
 

 

HDU5943 Kingdom of Obsession 暴力判质数+二分匹配

http://acm.hdu.edu.cn/showproblem.php?pid=5943


Kingdom of Obsession

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Problem Description

There is a kindom of obsession, so people in this kingdom do things very strictly.
They name themselves in integer, and there are $n$ people with their id continuous $(s+1, s+2, \cdots, s+n)$ standing in a line in arbitrary order, be more obsessively, people with id $x$ wants to stand at $y^{th}$ position which satisfy
$$x \mod y = 0$$
Is there any way to satisfy everyone's requirement?

Input

First line contains an integer $T$, which indicates the number of test cases.
Every test case contains one line with two integers $n$, $s$.
Limits
$1 \leq T \leq 100$.
$1 \leq n \leq 10^9$.
$0 \leq s \leq 10^9$.

Output

For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result string.
If there is any way to satisfy everyone's requirement, y equals 'Yes', otherwise y equals 'No'.

Sample Input

2
5 14
4 11

Sample Output

Case #1: No
Case #2: Yes

Source

 

题意:

有n个人,分别id为s+1,s+2,……s+n,现在让这n个人排队,要求每个位置的人的id要能被位置号整除,问是否可行。

思路:

考虑到id为质数的人,只能被放到第一个位置,或者放到位置号和他id相同的位置。当s+1……s+n区间内出现2个质数以上质数的时候,一定要将后部分放到前面去。因为数据范围为$1 \leq n \leq 10^9$.$0 \leq s \leq 10^9$.这个范围下相邻的两个质数都靠的比较近,可以暴力从s+n开始往前,验证区间的质数是否大于等于2。

如果区间内的质数小于2个,则将s+1到s+n的数与1到n进行二分匹配。

如果区间内的质数大于等于2个,则将后s个数与1到s进行二分匹配。

如果完全匹配上就是可行的。

 

 

Codeforces 708D 费用流

 

HDU 5723 Abandoned country 最小生成树 + 期望计算

http://acm.hdu.edu.cn/showproblem.php?pid=5723

Abandoned country

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description
An abandoned country has n(n100000) villages which are numbered from 1 to n . Since abandoned for a long time, the roads need to be re-built. There are m(m1000000) roads to be re-built, the length of each road is wi(wi1000000) . Guaranteed that any two wi are different. The roads made all the villages connected directly or indirectly before destroyed. Every road will cost the same value of its length to rebuild. The king wants to use the minimum cost to make all the villages connected with each other directly or indirectly. After the roads are re-built, the king asks a men as messenger. The king will select any two different points as starting point or the destination with the same probability. Now the king asks you to tell him the minimum cost and the minimum expectations length the messenger will walk.
Input
The first line contains an integer T(T10) which indicates the number of test cases.
For each test case, the first line contains two integers n,m indicate the number of villages and the number of roads to be re-built. Next m lines, each line have three number i,j,wi , the length of a road connecting the village i and the village j is wi .
Output
output the minimum cost and minimum Expectations with two decimal places. They separated by a space.
Sample Input
1
4 6
1 2 1
2 3 2
3 4 3
4 1 4
1 3 5
2 4 6
Sample Output
6 3.33
Author
HIT
Source
题意:给定一个图,每条边边权不同,求问最小生成树的大小,并求出任意两点,在最小生成树上路径长度的期望。
思路:由于每条边权都不同,那么最小生成树是唯一的。求任意两点,在最小生成树上路径长度的期望,可以考虑计算每条边对答案的贡献,经过这条边的次数*这条边的边权就是贡献,次数为这条边两边点的个数的乘积。用第一次dfs求出每个子树的大小,用第二次dfs求出每条边两边点的数目即可。最后将总和除以总的方案数n*(n-1)/2得到最终的答案。