2019-02-14 10:43:38 |  0 Comments  |  网络流 最小割 最短路

BUPT校内训练 & HDU 5294 最短路&最小割

Description

Innocent Wu follows Dumb Zhang into a ancient tomb. Innocent Wu’s at the entrance of the tomb while Dumb Zhang’s at the end of it. The tomb is made up of many chambers, the total number is N. And there are M channels connecting the chambers. Innocent Wu wants to catch up Dumb Zhang to find out the answers of some questions, however, it’s Dumb Zhang’s intention to keep Innocent Wu in the dark, to do which he has to stop Innocent Wu from getting him. Only via the original shortest ways from the entrance to the end of the tomb costs the minimum time, and that’s the only chance Innocent Wu can catch Dumb Zhang.
Unfortunately, Dumb Zhang masters the art of becoming invisible(奇门遁甲) and tricks devices of this tomb, he can cut off the connections between chambers by using them. Dumb Zhang wanders how many channels at least he has to cut to stop Innocent Wu. And Innocent Wu wants to know after how many channels at most Dumb Zhang cut off Innocent Wu still has the chance to catch Dumb

 2019-02-14 09:39:19 |  0 Comments  |  网络流 费用流

BZOJ 1937 Mst最小生成树

Description

Input

第一行为N、M,其中 表示顶点的数目, 表示边的数目。顶点的编号为1、2、3、……、N-1、N。接下来的M行,每行三个整数Ui,Vi,Wi,表示顶点Ui与Vi之间有一条边,其权值为Wi。所有的边在输入中会且仅会出现一次。再接着N-1行,每行两个整数Xi、Yi,表示顶点Xi与Yi之间的边是T的一条边。

Output

输出最小权值

Sample Input

6 9
1 2 2
1 3 2
2 3 3
3 4 3
1 5 1
2 6 3
4 5 4
4 6 7
5 6 6
1 3
2 3
3 4
4 5
4 6

Sample Output

8

【样例说明】 边(4,6)的权由7修改为3,代价为4
边(1,2)的权由2修改为3,代价为1
边(1,5)的权由1修改为4,代价为3
所以总代价为4+1+3=8
修改方案不唯一。

HINT

1<=n<=50,1<=m<=800,1<=wi<=1000
n-->点数..m-->边数..wi--->边权


题解

这道题的题意是要求修改一些边的权值使得给出的树成为这个图的最小生成树,求最小代价。
注意到我们只可能增大非树边,减小树边。

那么对于一个树边ii和一个可能影响到最小生成树的非树边jj,我们一定要满足如下条件:
widiwj+djwi−di≤wj+dj
移项,即
wiwjdi+djwi−wj≤di+dj
其中d表示我们对于边的改动值(一定非负)
这样就可以转化成二分图最小顶标和来做。
我们把边看成点,两原边边权之差作为新点之间的边权,跑一边KM或者最小费用最大流就可以了。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
typedef long long ll;
const int N=1005,M=2e5
 2019-02-13 09:33:40 |  0 Comments  |  最短路 差分约束系统

[转载]差分约束系统详细讲解

差分约束系统

一、何为差分约束系统:
差分约束系统(system of difference constraints),是求解关于一组变数的特殊不等式组之方法。如果一个系统由n个变量和m个约束条件组成,其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统(system of difference constraints)。亦即,差分约束系统是求解关于一组变量的特殊不等式组的方法。
通俗一点地说,差分约束系统就是一些不等式的组,而我们的目标是通过给定的约束不等式组求出最大值或者最小值或者差分约束系统是否有解。
比如:


二、差分约束系统的求解:
差分约束系统可以转化为图论来解决,对应于上面的不等式组,如果要求出x3-x0的最大值的话,叠加不等式可以推导出x3-x0<=7,最大值即为7,我们可以通过建立一个图,包含6个顶点,对每个xj-xi<=bk,建立一条i到j的有向边,权值为bk。通过求出这个图的x0到x3的最短路可以知道也为7,这是巧合吗?并不是。
之所以差分约束系统可以通过图论的最短路来解,是因为xj-xi<=bk,会发现它类似最短路中的三角不等式d[v] <=d[u]+w[u,v],即d[v]-d[u]<=w[u,v]。而求取最大值的过程类似于最短路算法中的松弛过程。
三角不等式:(在此引用大牛的博客)
B - A <= c     (1)
C - B <= a     (2)
C - A <= b     (3)
 如果要求C-A的最大值,可以知道max(C-A)= min(b,a+c),而这正对应了下图中C到A的最短路。


因此,对三角不等式加以推广,变量n个,不等式m个,要求xn-x1的最大值,便就是求取建图后的最短路。
同样地,如果要求取差分约束系统中xn-x1的最小值,便是求取建图后的最长路。最长路可以通过spfa求出来,只需要改下松弛的方向即可,即if(d[v] < d[u] + dist(u,v)) d[v] = d[u] + dist(u,v)。当然我们可以把图中所有的边权取负,求取最短路,两者是等价的。
最长路求解算法证明如下:
http://www.cnblogs.com/g0feng/archive/2012/09/13/2683880.html
最后一点,建图后不一定存在最短路/最长路,因为可能存在无限减小/增大的负环/正环,题

 2019-02-07 01:26:40 |  0 Comments  |  2-SAT

2-SAT问题

2-SAT问题

2-SAT问题一般会给出n个布尔变量(取0或1),再给出m个限制条件,求问是否能够找到可行性解满足这些约束条件。
我们对于2-SAT问题一般采取建图的方式,把一个点拆成两个点分别代表取true和false,然后根据限制条件建图,之后采取强连通分量的方式去寻找是否有可行性解。

约束条件建图方式

我们设其中两个变量xixj,设ij表示原变量(取1),ij表示其反变量(取0),那么有以下的约束条件及其建图方式:
1.必选xi:从ii连一条有向边,表示推出i为1是必然推出i为1,保证xi=true。
2.必不选xi:从ii连一条有向边。
3.xixj中至少选一个(xi or xj = 1):连接边j->i,i->j
4.xixj中不能都选(xi and xj = 0):连接边j->i,i->j
5.xixj选择情况相同(xi xor xj = 0):
连接边j->i,i->jj->i,i->j
6.xixj选择情况相反(xi xor xj = 1):
连接边

 2019-02-07 01:05:31 |  0 Comments  |  2-SAT tarjan topsort

BUPT校内训练&CodeChef - VRTXCOVR-Vertex Cover 2-SAT

Description

You are given an undirected graph G = (V, E) containing N nodes and M edges. The nodes are numbered from 1 to N. A subset C of V is a vertex cover if for every edge (u, v) ∈ E, at least one of u and v belong to C. Note that C = V is always a vertex cover.
Consider a partition of V into two sets A and B. It is said to be a valid partition, if the following two conditions are satisfied: A should be a vertex cover. And for each i such that 1 ≤ i ≤ n/2, nodes 2i and 2i - 1 don't belong to the same set (i.e. one belongs to set A and the other to set B).
Determine if a valid partition exists. If it exists, provide an example of one valid partition.

Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and M denoting the number of nodes and number of edges in the graph respectively.
Each of the following M lines contains two space-se

 2019-02-05 23:39:44 |  0 Comments  |  DP

BUPT校内训练&Codeforces 623B 序列DP

Description

You are given array ai of length n. You may consecutively apply two operations to this array:
·remove some subsegment (continuous subsequence) of length m < n and pay for it m·a coins;
·change some elements of the array by at most 1, and pay b coins for each change.
Please note that each of operations may be applied at most once (and may be not applied at all) so you can remove only one segment and each number may be changed (increased or decreased) by at most 1. Also note, that you are not allowed to delete the whole array.
Your goal is to calculate the minimum number of coins that you need to spend in order to make the greatest common divisor of the elements of the resulting array be greater than 1.

Input

The first line of the input contains integers n, a and b (1 ≤ n ≤ 1 000 000, 0 ≤ a, b ≤ 109) — the length of the array, the cost of removing a single element in the first operation and the cost of changing an element, respectively.
The second line contains n integers ai (2 ≤ a_i

 2019-02-05 23:39:39 |  0 Comments  |  A* 贪心

BUPT训练-Codefoces325E Red Button

Description

Piegirl found the red button. You have one last chance to change the inevitable end.
The circuit under the button consists of n nodes, numbered from 0 to n - 1. In order to deactivate the button, the n nodes must be disarmed in a particular order. Node 0 must be disarmed first. After disarming node i, the next node to be disarmed must be either node (2·i) modulo n or node (2·i) + 1 modulo n. The last node to be disarmed must be node 0. Node 0 must be disarmed twice, but all other nodes must be disarmed exactly once.
Your task is to find any such order and print it. If there is no such order, print -1.

Input

Input consists of a single integer n (2 ≤ n ≤ 105).

Output

Print an order in which you can to disarm all nodes. If it is impossible, print -1 instead. If there are multiple orders, print any one of them.

Examples

Input

2

Output

0 1 0

Input

3

Output

-1

Input

4

Output

0 1 3 2 0

Input

16

Output

0 1 2 4 9 3 6 13 10 5 11 7 15 14 12 8 0

题目大意

有n个红色按钮,编号0,1,……,n,你需要从0开始按这些红色按钮,要求除0号以外都只能按一次,而且是从0按,最后一次也要

 2019-02-03 22:46:55 |  0 Comments  |  三分

三分法

三分法

我们已经学过有序序列查找元素的二分法了,那么这次来学一下三分法。
三分法,故名思义,就是把一个区间分成三份。
但是这三分法是用来干什么的呢?
三分法是用来求解单峰函数型(凸型序列,包括上凸和下凸)查找元素问题最值的有力手段。

(图片转自chenxiaoran666的博客)

三分的核心思路如下: 对于当前的区间[l,r],求出midl = (l+r)/2,midr = (midl+r)/2,比较f(midl)与f(midr)的值哪个更接近于最值,并根据结果确认下一个搜索区间是[l,midr]还是[midl,r],直到l>=r。


示例代码

我们以上凸序列为例

int find(int l,int r){
    if(l >= r)return l;
    int midl = (l+r) >> 1;
    int midr = (midl + r) >> 1;
    if(a[midl] > a[midr])
        return find(l,midr);
    else return find(midl,r);
}​

当然也是可以写成迭代形式的,如下:

while(l < r){
    int midl = (l + r) >> 1;
    int midr = (midl + r) >> 1;
    if(a[midl] > a[midr])
        r = midr;
    else l = midl;
}​

虽然很少用,但是这种方法还是会有些用的,例如凸包。

如果各位官爷学到的话,请在我的QQ点个赞吧,QQ932901730(厚脸皮)。

 2019-01-27 22:31:09 |  0 Comments  |  DP

数位DP & BZOJ1026[SCOI 2009]windy数题解

数位DP

这个鬼东西是个啥????我咋没见过呢?
emmm……
数位DP,顾名思义,利用数字的每一个数位(个、十、百、千、万、……)来计算的动态规划算法。
啥?我还是不懂的?
那么我们还是来说一下这种算法的适用题型吧……
给定两个数a,b,求满足给定条件的数的个数。(举个栗子:求ab之间不包含子串“62”的数的个数)
这也太明显了吧……按照一个个把数字拆开检查不就行了么……
nope! 如果是a,b的范围是1 <= a,b <= 200000000001<=a,b<=20000000000呢?你还暴力拆开检查么?你家计算机跑上一天都不一定能跑出来。
那咋整?
数位DP!
数位DP的基本思路就是按照数位对数字进行拆开,但是数位DP会利用每一位的数进行动态规划从而达到消除重复计算的作用,从而减小时间复杂度。像是上面的例子,我们可以想象,其实我们计算很多数的时候是在进行一些不必要的重复计算的。而数位DP就是为了这类问题避开这些重复计算而被总结设计出来的。
下面我们来说一下数位DP的核心步骤。
枚举当前是第几位,然后枚举这一位上的数,再枚举这个的低一位的数,检查是否满足条件,进行状态转移。这一步的伪代码如下

void init(){
    memset(dp,0,sizeof(dp));
    for(int i = 0;i <= 9;++i)
        dp[1][i] = 1;
    for(int i = 2;i <= 10;++i)
        for(int j = 0;j <= 9;++j)
            for(int k = 0;k <= 9;++k){
                if(满足题目条件)
                    dp[i][j] += dp[i-1][k];
            }
    return;
}

对数位DP数组计算完成后,对于题中的a,b,我们就只需要计算0——b中满足题目条件的数的个数和0——a-1中满足题目条件的个数,然后相减就可以得到我们想要的结果了。(差分前缀和的思想)一般来说这一步的代码是比较固定的,大致如下,具体题目自己调整。

long long solve(long long x){
    long long ans = 0;
    k = 0;
    memset(m,0,sizeof(m
 2019-01-18 23:26:17 |  0 Comments  |  STL

[转载]6 个技巧,提升 C++11 的 vector 性能

6 个技巧,提升 C++11 的 vector 性能

Vector 就像是 C++ STL 容器的瑞士军刀。Bjarne Stoutsoup 有一句话 – “一般情况下,如果你需要容器,就用 vector”。像我们这样的普通人把这句话当作真理,只需要照样去做。然而,就像其它工具一样,vector 也只是个工具,它能提高效率,也能降低效率。

这篇文章中我们可以看到 6 种优化使用 vector 的方法。我们会在最常见的使用 vector 的开发任务中看到有效的方法和无效的方法,并以此衡量有效使用 vector 会带来怎样的性能提升,并试图理解为什么能得到这样的性能提升。

性能测试的搭建和方法:

  • 所有测试都在我的 Surface Book 中运行,这台笔记本拥有主频 2.6Ghz 的酷睿 i7 处理器,8 GB 内存,安装了 Windows 10 操作系统并使用 VS2015 C++ 编译器编译运行。

  • 我们会使用 Stopwatch。这个工具由 Kjell 创建,在 https://github.com/KjellKod/Stopwatch 可以找到。

  • 我们会运行每个测试 100 次,然后计算平均运行时间来作为依据。运行测试的代码在这里。你可以自由下载,用于在你自己的系统中评估 vector 的性能。那里提供的代码段只反映了一次循环,这让事件变得简单。

  • 我们在 vector 中存入 TestStruct 结构的数据,并使用 FillVector() 来填充 vector。它们的定义如下。

// Test struct to be inserted/removed from vector
struct BigTestStruct
{
  int iValue = 1;
  float fValue;
  long lValue;
  double dValue;
  char cNameArr[10];
  int iValArr[100];
};
// Helper function to populate the test vectors
void FillVector(vector<BigTestStruct>& testVector)
{
  for (int i = 0; i < 10000; i++)
  {
    BigTestStruct bt;
    testVect
Title - Artist
0:00