青烟绕指柔 - 个人主页动态

2019-12-27 14:03

Problem Description Years later, Jerry fell in love with a girl, and he often walks for a long time to pay visits to her. But, because he spends too much time with his girlfriend, Tom feels neglected and wants to prevent him from visiting her. After doing some research on the neighbourhood, Tom foun...

0 点赞评论收藏

2019-12-27 14:02

已编辑

中央美术学院算法工程师

A_star 第K短路

给定一张N个点（编号1,2…N），M条边的有向图，求从起点S到终点T的第K短路的长度，路径允许重复经过点或边。 注意： 每条最短路中至少要包含一条边。 输入格式 第一行包含两个整数N和M。 接下来M行，每行包含三个整数A,B和L，表示点A与点B之间存在有向边，且边长为L。 最后一行包含三个整数S,T和K，分别表示起点S，终点T和第K短路。 输出格式 输出占一行，包含一个整数，表示第K短路的长度，如果第K短路不存在，则输出“-1”。 数据范围 1≤S,T≤N≤1000, 0≤M≤105, 1≤K≤1000, 1≤L≤100 输入样例： 2 2 1 2 5 2 1 4 1 2 2 输出...

0 点赞评论收藏

2019-12-27 14:02

中央美术学院算法工程师

树的重心

定义及性质 定义1：找到一个点,删除它得到的森林中最大的子树节点数最少（也就是最大的连通块的点数最小）,那么这个点就是这棵树的重心。 定义2：删除重心后得到的所有子树，其顶点数必然不超过n/2 性质1：树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么他们的距离和一样。 性质2：把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上。 性质3：把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离。 一般我们树形dp一下就能求出树的重心，我们用 dp[x] 表示 x 点的子树的节点数量，然后dfs一遍就可以了。 POJ 16...

0 点赞评论收藏

2019-12-27 14:02

中央美术学院算法工程师

POJ 2631

Roads in the North Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 6281 Accepted: 2950 Description Building and maintaining roads among communities in the far North is an expensive business. With this in mind, the roads are build such that there is only one route from a village to a vil...

0 点赞评论收藏

2019-12-27 14:01

已编辑

中央美术学院算法工程师

信息传递

题目描述 有 n 个同学（编号为 1 到 n ）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 i 的同学的信息传递对象是编号为 Ti 的同学。 游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息， 但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？ 输入输出样例 输入 5 2 4 2 3 1 输出 3 题意很简单，如果信息可以传递回来，代表形成了一个环，所以题意就是要求找一个最小环...

0 点赞评论收藏

2019-12-27 14:01

中央美术学院算法工程师

[HAOI2006]受欢迎的牛

题目描述 每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶 牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜 欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你 算出有多少头奶牛可以当明星。 输入格式 第一行：两个用空格分开的整数：N和M 第二行到第M + 1行：每行两个用空格分开的整数：A和B，表示A喜欢B 输出格式 第一行：单独一个整数，表示明星奶牛的数量 输入输出样例 输入 3 3 1 2 2 1 2 3 输出 1 说明/提示 只有 3 号奶牛可以做明星 【数据范围】 10%...

0 点赞评论收藏

2019-12-27 14:01

中央美术学院算法工程师

[POI2008]BLO-Blockade

题目描述 在Byteotia有n个城镇。 一些城镇之间由无向边连接。 在城镇外没有十字路口，尽管可能有桥，隧道或者高架公路（反正不考虑这些）。每两个城镇之间至多只有一条直接连接的道路。人们可以从任意一个城镇直接或间接到达另一个城镇。 每个城镇都有一个公民，他们被孤独所困扰。事实证明，每个公民都想拜访其他所有公民一次（在主人所在的城镇）。所以，一共会有n*（n-1）次拜访。 不幸的是，一个程序员总罢工正在进行中，那些程序员迫切要求购买某个软件。 作为抗议行动，程序员们计划封锁一些城镇，阻止人们进入，离开或者路过那里。 正如我们所说，他们正在讨论选择哪些城镇会导致最严重的后果。 编写一个程...

0 点赞评论收藏

2019-12-27 14:00

已编辑

中央美术学院算法工程师

[USACO5.3]校园网Network of Schools

题目描述 一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使 B 在 A 学校的分发列表中， A 也不一定在 B 学校的列表中。 你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务 B）。一个扩展就是在一个学校的接收学校列表中...

0 点赞评论收藏

2019-12-27 14:00

中央美术学院算法工程师

HDU -4289

Control Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5620 Accepted Submission(s): 2281 Problem Description   You, the head of Department of Security, recently received a top-secret information that a group of terrorists is planning to transp...

0 点赞评论收藏

2019-12-27 13:59

已编辑

中央美术学院算法工程师

HDU - 3605

Escape Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 14541 Accepted Submission(s): 3666 Problem Description 2012 If this is the end of the world how to do? I do not know how. But now scientists have found that some stars, who can live, but so...

0 点赞评论收藏

2019-12-27 13:59

已编辑

中央美术学院算法工程师

HDU - 3081

Marriage Match II Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5882 Accepted Submission(s): 1872 Problem Description Presumably, you all have known the question of stable marriage match. A girl will choose a boy; it is similar as the game of...

0 点赞评论收藏

2019-12-27 13:59

中央美术学院算法工程师

酒店之王

题目描述 XX酒店的老板想成为酒店之王，本着这种希望，第一步要将酒店变得人性化。由于很多来住店的旅客有自己喜好的房间色调、阳光等，也有自己所爱的菜，但是该酒店只有p间房间，一天只有固定的q道不同的菜。 有一天来了n个客人，每个客人说出了自己喜欢哪些房间，喜欢哪道菜。但是很不幸，可能做不到让所有顾客满意（满意的条件是住进喜欢的房间，吃到喜欢的菜）。 这里要怎么分配，能使最多顾客满意呢？ 输入格式 第一行给出三个正整数表示n,p,q(<=100)。 之后n行，每行p个数包含0或1，第i个数表示喜不喜欢第i个房间（1表示喜欢，0表示不喜欢）。 之后n行，每行q个数，表示喜不喜欢第i道...

0 点赞评论收藏

2019-12-27 13:58

已编辑

中央美术学院算法工程师

负载平衡问题

题目描述 GG 公司有 n 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 n 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。 输入格式 文件的第 1 行中有 1 个正整数 n，表示有 n 个仓库。 第 2 行中有 n 个正整数，表示 n 个仓库的库存量。 输出格式 输出最少搬运量。 输入输出样例 输入 5 17 9 14 16 4 输出 11 说明/提示 1≤n≤100 极其***的我（不拆点要死？） 看到这道题，不难想到，要么直接贪心，要么费用流。 既然是网络流24题，给出费用流做法： 首先建立超级源点S，与超级汇...

0 点赞评论收藏

2019-12-27 13:58

中央美术学院算法工程师

运输问题

题目乱码。 题目链接：P 4015 费用流的模板题。。。。。直接按照题目建边跑一遍费用流即可（这居然是网络流24题。。。。），需要注意跑完一次网络流之后，要回归原图跑第二次。 AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> #define int long long using namespace std; const int N=410,M=100010; const int inf=0x3f3f3f3f3f3f3f3f; int n,m,s,t,d[N],a[N],b[N],c[N][N]; int he...

0 点赞评论收藏

2019-12-27 13:58

中央美术学院算法工程师

洛谷P3410 - 拍照

题目描述 小B有n个下属，现小B要带着一些下属让别人拍照。 有m个人，每个人都愿意付给小B一定钱让n个人中的一些人进行合影。如果这一些人没带齐那么就不能拍照，小B也不会得到钱。 注意：带下属不是白带的！！！对于每个下属，如果他带了那么小B需要给他一些钱，保证当他拍照时配合。 请问，小B的净收益最多是多少。 输入格式 第1行有2个正整数m和n（0<m,n<=100）。接下来的m行，每行是一个要求拍照的人的有关数据。第一个数是他同意支付该合影的费用；接着是该合影需要的若干下属的编号，以一个0作为行的结束标记。最后一行的n个数是带每个下属的费用。 输出格式 一个数，表示最大收益...

0 点赞评论收藏

关注他的用户也关注了：