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

Codeforce 847J Students Initiation

## 思路&建图

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

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

Smallest Minimum Cut

## 计蒜客 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

## 题意

• 如果可以，输出"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. 对于每一个左边的点，枚举每一条向右边连的边，那么从这个点对应的城市到所连的点的城市所移动的士兵的个数，就是这条边所流过的流量，即这条边反向边的残余流量。

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

# 思路

• 对于每个项来说，将其看成一个点，将其拆点为为$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$点流量，跑费用流即可，答案为最小费用的相反数。

# 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.

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

3 4

FZU

## 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'.

2
5 14
4 11

Case #1: No
Case #2: Yes

## 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