题目大意:n个点由m条边连接(1.两点之间最多1条边连接;2.点不能连接自身;3.至少有一种方式连接所有的点)。求出一个方案,使这个方案能用最小的长度连接所有的顶点。
输入:第一行:n(2<=n<=1000),m(1<=m<=15000);
            后面m行:a(顶点1),b(顶点2),c(长度)。
输出:第一行:方案中最长的边
       &[……]

继续阅读


图1是我给出的二分图中的一个匹配:[1,5]和[2,6]。图2就是在这个匹配的基础上找到的一条增广路径:3->6->2->5->1->4。我们借由它来描述一下二分图中的增广路径的性质:

(1)有奇数条边。
(2)起点在二分图的左半边,终点在右半边。
(3)路径上的点一定是一个在左半边,一个在右半边,交替出现。(其实二分图的性质就决定了这一点,因为二分图同一边的点之间没有边相连,不要忘记哦。)
(4)整条路径上没有重复的点。
(5)起点和终点都是目前还没有[……]

继续阅读

http://jsj.sdibt.edu.cn/judge/problem/viewProblem.action?id=186
题目大意:给定一个圆的直径d,以及均匀分布在圆上的n个点,从这n个点中,根据规则(g*k)%n[其中k=0,1,…,c-1]从这n个点中选出c个点,在这c个可用点上放置4个音箱,使这由这个4个音箱构成的四边形的面积最大。
输入输出:
输入:第一行是测试数据的组数,后面每一行4个数分别代表圆的直径d,n,c和g,其中:
1<=d<=1000
4<=n<=10^9
4<=c<=1000且c<=n
1<=g&[……]

继续阅读

http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2340
题目大意:(如题)
输入输出:(如题)
解题思路:
1.01背包问题(不同的是可以放同种类的物体)
2.建立dp数组,dp[i]表示容量为i时最大的分数,动态规划公式如下:
dp[j]=dp[j](j<cost[i])
dp[j]=max(dp[j],dp[j-cost[i]+score[i]])(cost[i]<=j<=m)
3.最后dp[m]即为所求
核心代码:

for(i=1;i<=n;i++)
    {
        c[......]

继续阅读

http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2338
题目大意:(如题)
输入输出:(如题)
解题思路:
1.长除法。(小学学过)
2.开辟lastrem数组,lastrem[i]表示余数i是否在前面出现过以及i出现的位置。数组dec[i]保存长除法中的商(包括循环和非循环部分)
3.sprintf的应用:由于涉及到整型数据到字符串型数据的转换,所以用sprintf。
核心代码:

while(true)
	{
		if(rem==0)
		{
			if(i==0)
				sprintf(res+strl[......]

继续阅读

http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2337
题目大意:给出标记为‘a-z’和‘A-Y’的牧场,标记为‘Z’的谷仓以及一些各个牧场之间和各个牧场到谷仓的距离。求出有母牛的牧场中到谷仓的最短距离。
输入输出:(如题)
解题思路:
1.floyed Warshall算法
2.建立大小为52*52的graph数组用于储存距离。(注意:是52,因为‘A’牧场和‘a’牧场不是一个牧场)
3.用floyed W[……]

继续阅读

http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2336
题目大意:(如题)
输入输出:(如题)
解题思路:
1.参考了nocow-usaco上的解题思路,开辟数组len,len[i][j]表示牧区i到牧区j的最短距离。maxlen[i]表示牧区i到其他可到达牧区的最大距离。
2.首先输入数据,p[i]保存了各个牧区的坐标,所以当:
(1)输入的字符为1时,对应的牧区i和牧区j的距离即可求出,公式为:
sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[[……]

继续阅读

http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2334
题目大意:(如题)
输入输出:(如题)
解题思路:
1.队列模拟。
2.定义结构体用于记录农民john和两头牛的信息:
 

typedef struct
{
int x;//横坐标
int y;//纵坐标
char d;//方向N,S,E,W
}pos;


3.建立两个队列qc和qf,进行模拟,满足条件的入队列
4.每次取两队首元素进行比较,如果纵坐标横坐标都相同时抓到当队列为空或者cnt>160000[……]

继续阅读

http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2332
题目大意:(如题)
输入输出:(如题)
解题思路:
1.建立datv数组,用来记录所给的硬币种类。dp[j]表示构造数量为j的面值所用硬币的方式数。
2.当取用的第i种硬币,问题就转换为dp[j-datv[i]]这个子问题。即构造数量为j-datv[i]的面值所用硬币的方式数。
3.动态规划公式: dp[j]=dp[j]+dp[j-datv[i]](j>=datv[i])
      &nbsp[……]

继续阅读

http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2331

题目大意:(如题)
输入输出:(如题)
解题思路:
1.深搜。最大解空间为一棵深度为9的完全3叉树。
2.用sum表示之前所有数的和,num表示当前数,outs记录要输出的字符串,t记录层数。
3.每次按“ ”,“+”,“-”的顺序生成下一层的子节点。当t==n时,判断sum+num是否等于0,等于0则输出outs返回,否则直接返回。
核心代码:

if(t==n)
	{
		if(su[......]

继续阅读

http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2330

解题思路:    
1.简单动态规划。基本思想是用小的二叉树去组成大的二叉树,最后输出dp[k][n]-dp[k-1][n]恰好就是要求的n个
    点组成深度最多为k的方法数
2.设dp[i][j]表示j个点组成深度最多为i的二叉树的方法数,则动态规划公式为:
    dp[i][j]=∑(dp[i-1][l]*dp[i-1[……]

继续阅读

题目大意:(如题)
输入输出:(如题)
解题思路:
1.简单动态规划。
2.纠结的边界处理,不建议采用dp[i]表示s前i个字符能否取得这种方法。用这种方法实现字符串储存的时候会比较麻烦。而且如果存储不对边界处理会非常麻烦……(最先我采用的是这种方法,结果WA 4次,多次处理还是有长度为0和长度为1的情况无法分辨,最终放弃)
核心代码:

lens=s.length();
	for(i=0;i<lens;i++)
	{
		for(j=0;j<cntp;j++)
		{
			flag=false;
			len[......]

继续阅读

http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2328
题目大意:(如题)
输入输出:(如题)
解题思路:
1.因为每个按钮按2次和没按效果是一样的。所以每个按钮或者按或者不按,一共有2^4=16中状态。
2.然后因为这个电灯系统有个性质,每6个一循环,所以把这4个按钮的16种状态对应的前6个灯的状态枚举出来。然后分析,发现一下规律:
-按1和按2相当于按3;
-按2和按3相当于按1;
-按1和按3相当于按2;
-按1按2和按3相当于不按;
-相差3的倍数也可以相互转换;
消重之后得到8种[……]

继续阅读

http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2325
题目大意:(如题)
输入输出:(如题)
解题思路:
1.用打表法将每个数N(1<=N<3500)中间“I”“V”“X”“L”“C”“D”“M”的个数统计出来,用一个二维数组cnt[3500][7]保存起来。
2.枚举。从千位开始枚举,一直枚举到个位为止,每次判断减掉那个数之后剩下的数是否还不小于0[……]

继续阅读

http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2324
题目大意:(如题)
输入输出:(如题)
解题思路:
简单搜索。按递增顺序搜索要求的n个数,然后跟前面的数判断距离是否大于d,找到的一组解即为最小的。
注意:
1.0在每组数据里面都出现。
2.b给出了搜索的最大值:2^b-1。
3.计算两个数a,b的距离,只要计算a^b的二进制形式中1的个数。
核心代码:
 

int dist(int x,int y) 
  
{ 
  
    int cnt,tmp;[......]

继续阅读

Algos is the Greek word for pain. Algor is Latin, to be cold. Neither is the root for algorithm, which stems instead from al-Khwarizmi, the name of the ninth-century Arab scholar whose book al-jabrwa’l muqabalah devolved into today’s high school algebra textbooks. Al-Khwarizmi stressed t[……]

继续阅读

、A*算法的程序编写原理
  我在《初识A*算法》中说过,A*算法是最好优先算法的一种。只是有一些约束条件而已。我们先来看看最好优先算法是如何编写的吧。如图有如下的状态空间:(起始位置是A,目标位置是P,字母后的数字表示节点的估价值)。
  如图有如下的状态空间:(起始位置是A,目标位置是P,字母后的数字表示节点的估价值)

图1 状态空间图

  搜索过程中设置两个表:OPEN和CLOSED。OPEN表保存了所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。算法中有一步是根据估[……]

继续阅读