FJUT_ACM_cjt152-CSDN博客

原创一个ACM底层参赛选手的退役感言

一个ACM底层参赛选手的退役感言大概是大学生活最有意义最有回忆的一年了吧，借着年底的最后几天写一下退役总结吧。直到现在还是感觉自己是个还在打比赛的选手。在高中毕业的时候选专业的时候纠结很久，本来在高中想的是奔着医学或者生物学方向选的专业，因为那时自认为是一个在这方面比较有天赋的人，但是最终也是没有选吧，因为种种原因吧，最后还是选择了计算机类专业。后来报志愿的时候第一所大学的第一个专业录取我也就

2018-01-02 14:00:52 4128 3

原创 POJ 2186 Popular Cows tarjan缩点强连通分量

题目大意：输入一行n,m代表n个牛，m个关系，下面m行每行两个数字u和v代表u仰慕v，如果a仰慕b，b仰慕c那么a仰慕c，问是否有牛被所有的其他牛仰慕，这样的牛的数量是多少。思路：如果一个牛被其他所有牛仰慕，那么这个牛所在的强连通分量出度一定为0。所以我们要先缩点，把是一个强连通分量的牛看成一个整体。接下来我们依次判断一个牛所仰慕的其他牛是否和它是一个强连通分量，如果不是那么这个强连通分量的出

2017-08-13 10:19:57 387

原创 HDU 3998 Sequence 最长上升子序列+网络流求不相交的最长上升子序列个数

题目大意：给你一个序列，求不相交的最长上升子序列的个数。思路：我们找0为超级源点，2*n+1为超级汇点，我们先dp出LIS，在dp的过程中建图，把一个点拆成两个点i和i+n在它们之间连一条权值为1的边，如果a[i]>a[j]&&dp[i]代码如下：#include#include#include#include#define inf 0x3fffffffusi

2017-08-11 14:44:18 666

原创 HDU 3416 Marriage Match IV SPFA+dinic 不相交最短路数目

题目大意：给你一个有向图，求不相交路径的最短路的数目。思路：首先我们需要知道最短路的长度，我们需要只满足可以成为最短路的边建成一个图，那么我们就需要筛选出这条边，先跑一遍SPFA把两点之间的最短路都找出来，然后判断一下这条边是否可以成为最短路我们只需要判断dis[to]-dis[from]是否等于w即可，如果等于说明加上这条边不影响最短路的长度，把所有的这些边重新建一个图，边权为1，跑

2017-08-11 10:36:40 341

原创 HDU 3277 Marriage Match III 网络流（dinic 优化）+floyd

题目大意：n个女生n个男生在一起玩耍，他们在玩一个“”结婚“的游戏，每局游戏女生找到一个男生作为自己的伴侣，每个女生可以找不和自己争吵的男生，如果一个女生和另外一个女生是好朋友，她也可以找和另外一个女生不争吵的男生作为自己的伴侣，另外有K次机会从所有的男生中选一个强制作为自己伴侣，每一局每个女生要找的男生都必须不相同，问这个游戏最多能进行多少局。首先输入一个T代表T组样例，第二行输入四

2017-08-10 09:59:59 334

大概是第二次参加福建省的省赛赛吧，和第一次省赛不同的是换了两个队友，然后“”实力变强了？”。六月十一号正式赛，六月十号从学校出发开始半天的旅程，和蓝桥杯到车站的时间差不多，指导老师在车站等我们，大概一个小时后到了火车站，买票的时候买的有些晚，和他们几个隔开了，不过影响不大。两个小时后到了厦门，先感慨了了一番厦门的好，然后发现真的热，几个人背着书包在太阳下走了半个小时终于到了酒店，然后指导老师一...

2017-07-25 17:00:21 1539

原创 HDU 1595 find the longest of the shortest枚举+最短路(删掉任意一条边的最长最短路)★★

题目大意：给出n和m表示顶点数和边数，边为双向边，接下来m行每行输入三个数起点，终点，权值。问删除掉其中的一条边，剩下的m-1条边中1到n的最短路中的最大长度是多少。思路：如果每条边都删除一次尝试着求m次最短路算出最大值肯定会超时，因为边最多有500000条，那么我们可以换个思路，先求出一遍最短路，如果删除的边不是最短路里的边，那么删除这条边后1到n的最短路还是不变的，如果要改变那么删

2017-07-22 16:27:37 569

原创 POJ 1860 Currency Exchange 货币兑换★

题目大意：给出n种货币，m种兑换方式，初始时你拥有的是第s种货币，价值为s。接下来m行每行前两个数代表两种货币，之后四个数分别代表，第一种货币到第二种货币的汇率和所要交的佣金，第二种到第一种货币的汇率和所要交的佣金。问能否在拥有初始货币数量的情况下，多次兑换后使得这种货币的数量增加。思路：判环，当有一个点入队次数大于n时说明有一个环能让数值一直变大。(SPFA判环技巧)#inclu

2017-07-21 09:58:11 488

原创 HDU 4253 Two Famous Companies

题目大意：给出三个数n,m,k,代表有n个点m条边，边分为两种一种A类一种B类，建一棵最小生成树其中A类的边要刚好用到k条，问最小花费是多少。思路：最小生成树+二分，要使得A类边正好用到k条，可以假设如果刚开始是一条也取不到，那么原因是A类的边权值很大，随着权值的减少建最小生成树时取到A类的边会越来越多，那么我们可以用二分来逐渐修改A类边的权值，使得最小生成树A类的边逼近k条，这时二分

2017-07-20 11:20:41 382

原创 HDU 3926 Hand in Hand 同构图★

判断两个图是否是同构图题目大意：给你两个图得顶点数和边数组成两个图，问两个图是否是同构图。首先两个图如果是同构图，那么顶点数和边数要相同。根据题中所给的信息可以得出构成的图可能是有好几个连通分量，我们可以用并查集加排序依次判断这些连通分量的顶点数是否相同，但是还要判断边数也是否一致，比如说下面这个样例5 41 22 33 14 55 41

2017-07-19 09:58:29 652

原创 POJ 3159 Candies 差分约束系统

差分约束系统的模板题。题目大意：输入一个n，m表示总人数和两个人之间分糖果关系的个数，接下来m行，每行输入一个A,B,c表示B最多比A多c个糖果，即B-A=B，这与求最短路时d(v)+w(v,u)点击打开链接这个网站里有差分约束系统的简单实用讲解。注意这个题要用栈对SPFA进行优化，用链式前向星存图，vector存图可能会超时，因为vector是动态数组，它每次开的内存有限，当内存

2016-11-06 09:14:15 411

原创 POJ 3169 Layout 差分约束系统

对于差分不等式，d(v)+w(v,u)>=d(u)，那么有一条边从v到u权值为w，求的是最短路，得到的是最大值，对于d(v)+w(v,u)，求的是最长路，得到的是最小值。根据本题所给的条件有d[i]=d[i],即i+1到i有一条权值为0的边,对于关系好的两头牛d[AL]+DL>=d[BL],即AL到BL有一条权值为DL的边，对于关系不好的两头牛有d[AD]+DD=d[AD],即BD到A

2016-11-05 20:50:56 282

原创 POJ 3259 Wormholes （寻找负权回路）

题目大意：有n个点m条双向路，w条单向路，输入的数据中前两个表示两点之间有路，前m条路表示这条路所花费的时间，后w条单向路表示可以回到过去某个时间，现在问你从某个点走之后是否会看到自己还没出发时的样子。如果有负权回路，即一个回路中点的权值总和为负数，那么就能看到没有出发时的自己，因为自己回到了出发之前的时间。用SPFA算法进行解，不断的松弛边，如果存在负权回路那么每一次松弛都会使距

2016-11-05 15:41:49 720

原创 POJ 1847 Tram 简单最短路★

读懂题意后就是一道简单的模板题。题目大意：n个交叉点，A,B是起始点和终点，接下来输入的n行每行刚开始输入一个数字num代表和那个点相邻的点的个数，之后num个数的第一个代表可以直接到达的城市，后面num-1个要翻转一下才可以到，问你从A到B最少的翻转次数。直接建图就好，第一个相邻的点距离是0，后面的距离是1，求最短路即为最小翻转次数，注意建图是单向的。AC代码：#in

2016-11-05 11:01:51 1043

原创 HDU 1856 More is better 基础并查集★

题目大意：王先生想让男孩们帮助他，男孩越多越好，但是房子有限，他只想留住那些有朋友关系或者间接有朋友关系的人，如果所有的人都没有朋友关系的话，他随机选一个人去帮他，问最多能留住多少人。并查集的基础题，但是当n等于0时好多人看题不清可能会写错，所有人都没关系就输出一个人。合并两个人的时候判断一下两个人是否已经直接或者间接有朋友关系，再合并一下这个集合中所包含元素的个数，找出最大的即可。代码如...

2016-11-04 15:53:18 884

原创 hdu 1325&&poj1308 Is It A Tree? 基础并查集★

题目大意：输入每次两个数n,m，表示n->m有一条边，当输入0 0时表示一棵树输入完毕，开始判断。题目要求任意两个顶点之间只有一条路可以相通，并且输入的必须是一个树形结构，即有一个是根节点，入度为0。上图中1，2满足题目要求，3图中5到8有两条路相通，不满足。首先输入的边数肯定是顶点数减一，因为两个顶点之间只有一条路，并且除根节点之外所有节点的入度只能为1，输入的所有的点构成的只有一幅

2016-11-04 15:03:21 408

原创 HDU 1272 小希的迷宫基础并查集★

并查集的基础题，输入时判断一下两个点的根节点是否已经联通，如果已经联通那么说明迷宫不符合要求，需要注意2点： 1.当直接输入0 0时这时直接输出Yes,进行下一次输入，因为0 0也满足题目的要求。 2.迷宫必须是联通的1 2 3 4 0 0这组样例是错误的，因为迷宫两处被分开.1的解决办法很简单直接判断就行，2就要记录一下每个点所在的集合的点的数目，首先点的总数应该记下，这个很好判断，开一个数组

2016-11-03 09:00:53 558

原创开通博客

开通博客的第一天，2016年10月29日。#includeusing namespace std;int main(){printf("Hello,c boke"); return 0;}

2016-10-29 20:34:14 320

FJUT_ACM_cjt152的博客