匈牙利算法java代码 匈牙利算法java代码大全

ACM入门学什么

初学者建议购买，《算法竞赛入门经典》 刘汝佳作，十分好，在深入可以是他的另外一本，黑书，《算法艺术与信息学竞赛》。

创新互联公司一直通过网站建设和网站营销帮助企业获得更多客户资源。 以"深度挖掘，量身打造，注重实效"的一站式服务，以成都网站建设、成都网站设计、移动互联产品、成都营销网站建设服务为核心业务。十余年网站制作的经验，使用新网站建设技术，全新开发出的标准网站，不但价格便宜而且实用、灵活，特别适合中小公司网站制作。网站管理系统简单易用，维护方便，您可以完全操作网站资料，是中小公司快速网站建设的选择。

计划：

ACM的算法（觉得很好，有层次感）POJ上的一些水题(可用来练手和增加自信)

(poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)

初期:

一.基本算法:

(1)枚举. (poj1753,poj2965)

(2)贪心(poj1328,poj2109,poj2586)

(3)递归和分治法.

(4)递推.

(5)构造法.(poj3295)

(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.图算法:

(1)图的深度优先遍历和广度优先遍历.

(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)

(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)

(3)最小生成树算法(prim,kruskal)

(poj1789,poj2485,poj1258,poj3026)

(4)拓扑排序 (poj1094)

(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)

(6)最大流的增广路算法(KM算法). (poj1459,poj3436)

三.数据结构.

(1)串 (poj1035,poj3080,poj1936)

(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)

(3)简单并查集的应用.

(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)

(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)

(5)哈夫曼树(poj3253)

(6)堆

(7)trie树(静态建树、动态建树) (poj2513)

四.简单搜索

(1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)

(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)

(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.动态规划

(1)背包问题. (poj1837,poj1276)

(2)型如下表的简单DP(可参考lrj的书 page149):

1.E[j]=opt{D[i]+w(i,j)} (poj3267,poj1836,poj1260,poj2533)

2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列)

(poj3176,poj1080,poj1159)

3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)

六.数学

(1)组合数学:

1.加法原理和乘法原理.

2.排列组合.

3.递推关系.

(POJ3252,poj1850,poj1019,poj1942)

(2)数论.

1.素数与整除问题

2.进制位.

3.同余模运算.

(poj2635, poj3292,poj1845,poj2115)

(3)计算方法.

1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)

七.计算几何学.

(1)几何公式.

(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)

(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)

(poj1408,poj1584)

(4)凸包. (poj2187,poj1113)

中级:

一.基本算法:

(1)C++的标准模版库的应用. (poj3096,poj3007)

(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)

二.图算法:

(1)差分约束系统的建立和求解. (poj1201,poj2983)

(2)最小费用最大流(poj2516,poj2516,poj2195)

(3)双连通分量(poj2942)

(4)强连通分支及其缩点.(poj2186)

(5)图的割边和割点(poj3352)

(6)最小割模型、网络流规约(poj3308, )

三.数据结构.

(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)

(2)静态二叉检索树. (poj2482,poj2352)

(3)树状树组(poj1195,poj3321)

(4)RMQ. (poj3264,poj3368)

(5)并查集的高级应用. (poj1703,2492)

(6)KMP算法. (poj1961,poj2406)

四.搜索

(1)最优化剪枝和可行性剪枝

(2)搜索的技巧和优化 (poj3411,poj1724)

(3)记忆化搜索(poj3373,poj1691)

五.动态规划

(1)较为复杂的动态规划(如动态规划解特别的施行商问题等)

(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)

(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)

(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)

六.数学

(1)组合数学:

1.容斥原理.

2.抽屉原理.

3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).

4.递推关系和母函数.

(2)数学.

1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)

2.概率问题. (poj3071,poj3440)

3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)

(3)计算方法.

1.0/1分数规划. (poj2976)

2.三分法求解单峰(单谷)的极值.

3.矩阵法(poj3150,poj3422,poj3070)

4.迭代逼近(poj3301)

(4)随机化算法(poj3318,poj2454)

(5)杂题.

(poj1870,poj3296,poj3286,poj1095)

七.计算几何学.

(1)坐标离散化.

(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).

(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)

(3)多边形的内核(半平面交)(poj3130,poj3335)

(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高级:

一.基本算法要求:

(1)代码快速写成,精简但不失风格

(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)

(2)保证正确性和高效性. poj3434

二.图算法:

(1)度限制最小生成树和第K最短路. (poj1639)

(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)

(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446

(3)最优比率生成树. (poj2728)

(4)最小树形图(poj3164)

(5)次小生成树.

(6)无向图、有向图的最小环

三.数据结构.

(1)trie图的建立和应用. (poj2778)

(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法

(RMQ+dfs)).(poj1330)

(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的

目的). (poj2823)

(4)左偏树(可合并堆).

(5)后缀树(非常有用的数据结构,也是赛区考题的热点).

(poj3415,poj3294)

四.搜索

(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)

(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)

五.动态规划

(1)需要用数据结构优化的动态规划.

(poj2754,poj3378,poj3017)

(2)四边形不等式理论.

(3)较难的状态DP(poj3133)

六.数学

(1)组合数学.

1.MoBius反演(poj2888,poj2154)

2.偏序关系理论.

(2)博奕论.

1.极大极小过程(poj3317,poj1085)

2.Nim问题.

七.计算几何学.

(1)半平面求交(poj3384,poj2540)

(2)可视图的建立(poj2966)

(3)点集最小圆覆盖.

(4)对踵点(poj2079)

八.综合题.

(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)gsyagsy 2007-11-29 00:22

以及补充 Dp状态设计与方程总结

1.不完全状态记录

1青蛙过河问题

2利用区间dp

2.背包类问题

1 0-1背包，经典问题

2无限背包，经典问题

3判定性背包问题

4带附属关系的背包问题

5 + -1背包问题

6双背包求最优值

7构造三角形问题

8带上下界限制的背包问题(012背包)

3.线性的动态规划问题

1积木游戏问题

2决斗（判定性问题）

3圆的最大多边形问题

4统计单词个数问题

5棋盘分割

6日程安排问题

7最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等)

8方块消除游戏(某区间可以连续消去求最大效益)

9资源分配问题

10数字三角形问题

11漂亮的打印

12邮局问题与构造答案

13最高积木问题

14两段连续和最大

152次幂和问题

16N个数的最大M段子段和

17交叉最大数问题

4.判定性问题的dp(如判定整除、判定可达性等)

1模K问题的dp

2特殊的模K问题，求最大(最小)模K的数

3变换数问题

5.单调性优化的动态规划

11-SUM问题

22-SUM问题

3序列划分问题(单调队列优化)

6.剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)

1凸多边形的三角剖分问题

2乘积最大问题

3多边形游戏(多边形边上是操作符,顶点有权值)

4石子合并(N^3/N^2/NLogN各种优化)

7.贪心的动态规划

1最优装载问题

2部分背包问题

3乘船问题

4贪心策略

5双机调度问题Johnson算法

8.状态dp

1牛仔射击问题(博弈类)

2哈密顿路径的状态dp

3两支点天平平衡问题

4一个有向图的最接近二部图

9.树型dp

1完美服务器问题(每个节点有3种状态)

2小胖守皇宫问题

3网络收费问题

4树中漫游问题

5树上的博弈

6树的最大独立集问题

7树的最大平衡值问题

8构造树的最小环

参加ACM大赛应该准备哪些课程？

课程：

（1）基本算法: 二分,分治，贪心

（2） 离散数学离散数学动态规划

（3） 搜索算法：深度优先 搜索，广度优先搜 A*算法 ，阿尔法贝塔剪枝

（4）数据结构:  线段树, 树状数组，并查集,Trie图

（5）图论问题：最小生成树 最短路 强连通分量、桥和割点

（6）网络流算法：基本的网络流算法，Dinic算法，带上下界的网络流，最小费用流

（7）计算几何：线与线求交，线与面求交，求凸包，半平面求交等

（8） 离散数学，高等数学，线性代数，初等数论，计算几何

（9）计算机专业英语

（10）C++；基础的递归、枚举算法

扩展资料：

1.参赛队伍最多由三名参赛队员组成。

2.竞赛中命题10题左右，试题描述为英文，比赛时间为5个小时，前四个小时可以实时看到排名，最后一小时封榜，无法看到排名。

3.竞赛可以使用的语言：Java, C, C++, Kotlin 和 Python。

4.重点考察选手的算法和程序设计能力，不考察实际工程中常用的系统编程，多线程编程等等；

5.选手可携带任何非电子类资料，包括书籍和打印出来的程序等，部分赛区会对选手携带的纸质资料做限制。

6.评委负责将结果（正确或出错的类型）通过网络尽快返回给选手，除此之外不提供任何额外帮助；

7.每个题目对应一种颜色的气球，通过该题目的队伍会得到对应颜色气球。每道题目第一支解决掉它的队还会额外获得一个“FIRST PROBLEM SOLVED”的气球。

参考资料：北京大学暑期课：ACM/ICPC竞赛训练

百度百科-ACM国际大学生程序设计竞赛

java软件开发的代码规范

1、组织与风格

(1).关键词和操作符之间加适当的空格。

(2).相对独立的程序块与块之间加空行

(3).较长的语句、表达式等要分成多行书写。

(4).划分出的新行要进行适应的缩进，使排版整齐，语句可读。

(5).长表达式要在低优先级操作符处划分新行，操作符放在新行之首。

(6).循环、判断等语句中若有较长的表达式或语句，则要进行适应的划分。

(7).若函数或过程中的参数较长，则要进行适当的划分。

(8).不允许把多个短语句写在一行中，即一行只写一条语句。

(9).函数或过程的开始、结构的定义及循环、判断等语句中的代码都要采用缩进风格。

注：如果大家有兴趣可以到安安DIY创作室博客，有相关说明性的文章和解释。

2、注解

Java 的语法与 C++ 及为相似，那么，你知道 Java 的注释有几种吗？是两种？

// 注释一行

/* ...... */ 注释若干行

不完全对，除了以上两种之外，还有第三种，文档注释：

/** ...... */ 注释若干行，并写入 javadoc 文档

注释要简单明了。

String userName = null; //用户名

边写代码边注释，修改代码同时修改相应的注释，以保证注释与代码的一致性。

在必要的地方注释，注释量要适中。注释的内容要清楚、明了，含义准确，防止注释二义性。

保持注释与其描述的代码相邻，即注释的就近原则。

对代码的注释应放在其上方相邻位置，不可放在下面。对数据结构的注释应放在其上方相邻位置，不可放在下面；对结构中的每个域的注释应放在此域的右方；

同一结构中不同域的注释要对齐。

变量、常量的注释应放在其上方相邻位置或右方。

全局变量要有较详细的注释，包括对其功能、取值范围、哪些函数或过程存取它以及存取时注意事项等的说明。

在每个源文件的头部要有必要的注释信息，包括：文件名；版本号；作者；生成日期；模块功能描述（如功能、主要算法、内部各部分之间的关系、该文件与其它文件关系等）；主要函数或过程清单及本文件历史修改记录等。

/**

* Copy Right Information : Neusoft IIT

* Project : eTrain

* JDK version used : jdk1.3.1

* Comments : config path

* Version : 1.01

* Modification history :2003.5.1

* Sr Date Modified By Why What is modified

* 1. 2003.5.2 Kevin Gao new

**/

在每个函数或过程的前面要有必要的注释信息，包括：函数或过程名称；功能描述；输入、输出及返回值说明；调用关系及被调用关系说明等

/**

* Description :checkout 提款

* @param Hashtable cart info

* @param OrderBean order info

* @return String

*/

public String checkout(Hashtable htCart,

OrderBean orderBean)

throws Exception{

}

javadoc注释标签语法

@author 对类的说明 标明开发该类模块的作者

@version 对类的说明 标明该类模块的版本

@see 对类、属性、方法的说明 参考转向，也就是相关主题

@param 对方法的说明 对方法中某参数的说明

@return 对方法的说明 对方法返回值的说明

@exception 对方法的说明 对方法可能抛出的异常进行说明

3、命名规范

定义这个规范的目的是让项目中所有的文档都看起来像一个人写的，增加可读性，减少项目组中因为换人而带来的损失。（这些规范并不是一定要绝对遵守，但是一定要让程序有良好的可读性）较短的单词可通过去掉元音形成缩写；要不然最后自己写的代码自己都看不懂了，那可不行。

较长的单词可取单词的头几发符的优先级，并用括号明确表达式的操作顺序，避免使用默认优先级。

使用匈牙利表示法

Package 的命名

Package 的名字应该都是由一个小写单词组成。

package com.neu.util

Class 的命名

Class 的名字必须由大写字母开头而其他字母都小写的单词组成,对于所有标识符，其中包含的所有单词都应紧靠在一起，而且大写中间单词的首字母。

public class ThisAClassName{}

Class 变量的命名

变量的名字必须用一个小写字母开头。后面的单词用大写字母开头

userName , thisAClassMethod

Static Final 变量的命名

static Final 变量的名字应该都大写，并且指出完整含义。

/**

*DBConfig PATH

**/

public static final String

DB_CONFIG_FILE_PATH =com.neu.etrain.dbconfig;

参数的命名

参数的名字必须和变量的命名规范一致。

数组的命名

数组应该总是用下面的方式来命名：

byte[] buffer;

而不是：

byte buffer[];

方法的参数

使用有意义的参数命名，如果可能的话，使用和要赋值的字段一样的名字：

SetCounter(int size){

this.size = size;

}

4、文件样式

所有的 Java(*.java) 文件都必须遵守如下的样式规则：

版权信息

版权信息必须在 java 文件的开头，比如：

/*

* Copyright ? 2000 Shanghai XXX Co. Ltd.

* All right reserved.

*/

其他不需要出现在 javadoc 的信息也可以包含在这里。

Package/Imports

package 行要在 import 行之前，import 中标准的包名要在本地的包名之前，而且按照字母

顺序排列。如果 import 行中包含了同一个包中的不同子目录，则应该用 * 来处理。

package hotlava.net.stats;

import java io.*;

import java.util.Observable;

import hotlava.util.Application;

这里 java。io.* 使用来代替InputStream and OutputStream 的。

Class

接下来的是类的注释，一般是用来解释类的。

/**

* A class representing a set of packet and byte counters

* It is observable to allow it to be watched, but only

* reports changes when the current set is complete

*/

接下来是类定义，包含了在不同的行的 extends 和 implements

public class CounterSet

extends Observable

implements Cloneable

Class Fields

接下来是类的成员变量：

/**

* Packet counters

*/

protected int[] packets;

public 的成员变量必须生成文档（JavaDoc）。proceted、private和 package 定义的成

员变量如果名字含义明确的话，可以没有注释。

存取方法

接下来是类变量的存取的方法。它只是简单的用来将类的变量赋值获取值的话，可以简单的

写在一行上。

/**

* Get the counters

* @return an array containing the statistical data. This array has been

* freshly allocated and can be modified by the caller.

*/

public int[] getPackets() { return copyArray(packets, offset); }

public int[] getBytes() { return copyArray(bytes, offset); }

public int[] getPackets() { return packets; }

public void setPackets(int[] packets) { this.packets = packets; }

其它的方法不要写在一行上

构造函数

接下来是构造函数，它应该用递增的方式写（比如：参数多的写在后面）。

访问类型 (public, private 等.) 和 任何 static, final 或 synchronized 应该在一行

中，并且方法和参数另写一行，这样可以使方法和参数更易读。

public

CounterSet(int size){

this.size = size;

}

克隆方法

如果这个类是可以被克隆的，那么下一步就是 clone 方法：

public

Object clone() {

try {

CounterSet obj = (CounterSet)super.clone();

obj.packets = (int[])packets.clone();

obj.size = size;

return obj;

}catch(CloneNotSupportedException e) {

throw new InternalError(Unexpected CloneNotSUpportedException: +

e.getMessage());

}

}

类方法

下面开始写类的方法：

/**

* Set the packet counters

* (such as when restoring from a database)

*/

protected final

void setArray(int[] r1, int[] r2, int[] r3, int[] r4)

throws IllegalArgumentException

{

//

// Ensure the arrays are of equal size

//

if (r1.length != r2.length || r1.length != r3.length || r1.length != r4.length)

throw new IllegalArgumentException(Arrays must be of the same size);

System.arraycopy(r1, 0, r3, 0, r1.length);

System.arraycopy(r2, 0, r4, 0, r1.length);

}

toString 方法

无论如何，每一个类都应该定义 toString 方法：

public

String toString() {

String retval = CounterSet: ;

for (int i = 0; i data.length(); i++) {

retval += data.bytes.toString();

retval += data.packets.toString();

}

return retval;

}

}

main 方法

如果main(String[]) 方法已经定义了, 那么它应该写在类的底部.

5、代码可读性

避免使用不易理解的数字，用有意义的标识来替代。

不要使用难懂的技巧性很高的语句。

源程序中关系较为紧密的代码应尽可能相邻。

6、代码性能

在写代码的时候，从头至尾都应该考虑性能问题。这不是说时间都应该浪费在优化代码上，而是我们时刻应该提醒自己要注意代码的效率。比如：如果没有时间来实现一个高效的算法，那么我们应该在文档中记录下来，以便在以后有空的时候再来实现她。

不是所有的人都同意在写代码的时候应该优化性能这个观点的，他们认为性能优化的问题应该在项目的后期再去考虑，也就是在程序的轮廓已经实现了以后。

不必要的对象构造

不要在循环中构造和释放对象

使用 StringBuffer 对象

在处理 String 的时候要尽量使用 StringBuffer 类，StringBuffer 类是构成 String 类的基础。

String 类将 StringBuffer 类封装了起来，（以花费更多时间为代价）为开发人员提供了一个安全的接口。当我们在构造字符串的时候，我们应该用 StringBuffer 来实现大部分的工作，当工作完成后将 StringBuffer 对象再转换为需要的 String 对象。比如：如果有一个字符串必须不断地在其后添加许多字符来完成构造，那么我们应该使用StringBuffer 对象和她的 append() 方法。如果我们用 String 对象代替StringBuffer 对象的话，会花费许多不必要的创建和释放对象的 CPU 时间。大家可以来安安DIY创作室一起讨论。

避免太多的使用 synchronized 关键字避免不必要的使用关键字 synchronized，应该在必要的时候再使用她，这是一个避免死锁的好方法。

7、编程技巧

byte 数组转换到 characters

为了将 byte 数组转换到 characters，你可以这么做：

Hello world!.getBytes();

Utility 类

Utility 类（仅仅提供方法的类）应该被申明为抽象的来防止被继承或被初始化。

初始化

下面的代码是一种很好的初始化数组的方法：

objectArguments = new Object[] { arguments };

枚举类型

JAVA 对枚举的支持不好，但是下面的代码是一种很有用的模板：

class Colour {

public static final Colour BLACK = new Colour(0, 0, 0);

public static final Colour RED = new Colour(0xFF, 0, 0);

public static final Colour GREEN = new Colour(0, 0xFF, 0);

public static final Colour BLUE = new Colour(0, 0, 0xFF);

public static final Colour WHITE = new Colour(0xFF, 0xFF, 0xFF);

}

这种技术实现了RED, GREEN, BLUE 等可以象其他语言的枚举类型一样使用的常量。

他们可以用 '==' 操作符来比较。

但是这样使用有一个缺陷：如果一个用户用这样的方法来创建颜色 BLACK new Colour(0,0,0)

那么这就是另外一个对象，'=='操作符就会产生错误。她的 equal() 方法仍然有效。由于这个原因，这个技术的缺陷最好注明在文档中，或者只在自己的包中使用。

8、编写格式

代码样式

代码应该用 unix 的格式，而不是 windows 的（比如：回车变成回车+换行）

文档化

必须用 javadoc 来为类生成文档。不仅因为它是标准，这也是被各种 java 编译器都认可的方法。使用 @author 标记是不被推荐的，因为代码不应该是被个人拥有的。

缩进

缩进应该是每行2个空格. 不要在源文件中保存Tab字符. 在使用不同的源代码管理工具时Tab字符将因为用户设置的不同而扩展为不同的宽度.如果你使用 UltrEdit 作为你的 Java 源代码编辑器的话，你可以通过如下操作来禁止保存Tab字符, 方法是通过 UltrEdit中先设定 Tab 使用的长度室2个空格，然后用 Format|Tabs to Spaces 菜单将 Tab 转换为空格。

页宽

页宽应该设置为80字符. 源代码一般不会超过这个宽度, 并导致无法完整显示, 但这一设置也可以灵活调整. 在任何情况下, 超长的语句应该在一个逗号或者一个操作符后折行. 一条语句折行后, 应该比原来的语句再缩进2个字符.

{} 对

{} 中的语句应该单独作为一行. 例如, 下面的第1行是错误的, 第2行是正确的:

if (i0) { i ++ }; // 错误, { 和 } 在同一行

if (i0) {

i ++

}; // 正确, { 单独作为一行

} 语句永远单独作为一行.如果 } 语句应该缩进到与其相对应的 { 那一行相对齐的位置。

括号

左括号和后一个字符之间不应该出现空格, 同样, 右括号和前一个字符之间也不应该出现空格. 下面的例子说明括号和空格的错误及正确使用:

CallProc( AParameter ); // 错误

CallProc(AParameter); // 正确

不要在语句中使用无意义的括号. 括号只应该为达到某种目的而出现在源代码中。下面的例子说明错误和正确的用法:

if ((I) = 42) { // 错误 - 括号毫无意义

if (I == 42) or (J == 42) then // 正确 - 的确需要括号

9、代码编译

1.编写代码时要注意随时保存，并定期备份，防止由于断电、硬盘损坏等原因造成代码丢失。

2.同一项目组内，最好使用相同的编辑器，并使用相同的设置选项。

3.合理地设计软件系统目录，方便开发人员使用。

4.打开编译器的所有告警开关对程序进行编译。

5.在同一项目组或产品组中，要统一编译开关选项。

6.使用工具软件（如Visual SourceSafe）对代码版本进行维护。如果大家有不明白的可以到安安DIY创作室留言。

10、可移植性

Borland Jbulider 不喜欢 synchronized 这个关键字，如果你的断点设在这些关键字的作用域内的话，调试的时候你会发现的断点会到处乱跳，让你不知所措。除非必须，尽量不要使用。

换行

如果需要换行的话，尽量用 println 来代替在字符串中使用\n。

你不要这样：

System.out.print(Hello,world!\n);

要这样：

System.out.println(Hello,world!);

或者你构造一个带换行符的字符串，至少要象这样：

String newline = System.getProperty(line.separator);

System.out.println(Hello world + newline);

PrintStream

PrintStream 已经被不赞成（deprecated）使用，用 PrintWrite 来代替它。

匈牙利算法 java

#includestdio.h

#includestring.h

bool g[201][201];

int n,m,ans;

bool b[201];

int link[201];

bool init()

{

int _x,_y;

memset(g,0,sizeof(g));

memset(link,0,sizeof(link));

ans=0;

if(scanf("%d%d",n,m)==EOF)return false;

for(int i=1;i=n;i++)

{

scanf("%d",_x);

for(int j=0;j_x;j++)

{

scanf("%d",_y);

g[ i ][_y]=true;

}

}

return true;

}

bool find(int a)

{

for(int i=1;i=m;i++)

{

if(g[a][ i ]==1!b[ i ])

{

b[ i ]=true;

if(link[ i ]==0||find(link[ i ]))

{

link[ i ]=a;

return true;

}

}

}

return false;

}

int main()

{

while(init())

{

for(int i=1;i=n;i++)

{

memset(b,0,sizeof(b));

if(find(i))ans++;

}

printf("%d\n",ans);

}

}

Pascal:

Program matching;

Const

max = 1000;

Var

map : array [1..max, 1..max] of boolean; {邻接矩阵}

match: array [1..max] of integer; {记录当前连接方式}

chk : array [1..max] of boolean; {记录是否遍历过，防止死循环}

m, n, i, t1, t2, ans,k: integer;

Function dfs(p: integer): boolean;

var

i, t: integer;

begin

for i:=1 to k do

if map[p, i] and not chk[ i ] then

begin

chk[ i ] := true;

if (match[ i ] = 0) or dfs(match[ i ]) then {没有被连过 或 寻找到增广路}

begin

match[ i ] := p;

exit(true);

end;{if}

end;{for}

exit(false);

end;{function}

begin{main}

readln(n, m); {N 为二分图左侧点数 M为可连接的边总数}

fillchar(map, sizeof(map), 0);

k:=0;

for i:=1 to m do{initalize}

begin

readln(t1, t2);

map[t1, t2] := true;

if kt2 then k:=t2;

end;{for}

fillchar(match, sizeof(match), 0);

ans := 0;

for i:=1 to n do

begin

fillchar(chk, sizeof(chk), 0);

if dfs(i) then inc(ans);

end;

writeln(ans);

for i:=1 to 1000 do

if match[ i ] 0 then

writeln(match[ i ], '--', i);

end.

谁帮忙给个运筹学任务指派问题的JAVA算法阿！不需要C或者C++语言,也不要和我说看着C++就能改,我不会改!!!!!

public class AssignWorkProblem {

public static void main(String[] args) {

/*

*测试

**/

int[][] cost=new int[][]{{2,15,13,4},{10,4,14,15},{9,14,16,13},{7,8,11,9}};

System.out.println(Arrays.toString(awpProcedure(cost, 4, 4)));

cost=new int[][]{{12,7,9,7,9},{8,9,6,6,6},{7,17,12,14,12},{15,14,6,6,10},{4,10,7,10,6}};

System.out.println(Arrays.toString(awpProcedure(cost, 5, 5)));

}

/*

* 费用矩阵costMatrix,由于要改变costMatrix的值，clone方法只能对基本类型;

* pnum即为几个人，也是costMatrix的行数，wnum是几个任务，也是costMatrix的列数

* 返回值：没两个数字为一组，表示i,j。如返回[1,1,2,0]表示costMatrix[1][1]、costMatrix[2][0]费用最低

*/

public static int[] awpProcedure(int[][] costMatrix,int pnum,int wnum){

if(pnum1||pnumwnum)

return null; //test n=m

int[][] costC=new int[pnum][]; //clone 一份costMatrix

for(int i=0;ipnum;i++){

costC[i]=costMatrix[i].clone();

}

//每行减去最小的元素

int[] lzeroa=new int[pnum+1]; //记录每行0的个数,lzero[pnum]记录0最少的行标

lzeroa[pnum]=-1;

int i,j;

for(i=0;ipnum;i++){

int lmin=costC[i][0]; //记录每行最小的

for(j=1;jwnum;j++)

lmin=lmincostC[i][j]?costC[i][j]:lmin;

for(j=0;jwnum;j++){

costC[i][j]-=lmin;

lzeroa[i]+=costC[i][j]==0?1:0;

}

}

for(j=0;jwnum;j++){

int cmin=costC[0][j]; //记录每列最小的

for(i=1;ipnum;i++)

cmin=cmincostC[i][j]?costC[i][j]:cmin;

if(cmin==0)continue;

for(i=0;ipnum;i++){

costC[i][j]-=cmin;

lzeroa[i]+=costC[i][j]==0?1:0;

}

}

int[] rzerop;

int whilenum=0;

while(true){

boolean[] lzerob=new boolean[pnum]; //记录某行是否查找过

rzerop=new int[pnum*2]; //记录0元素所在的行列

Arrays.fill(rzerop, -1);

if(awpIsSolution(costC,pnum,wnum,lzeroa.clone(),lzerob,rzerop))

break;

//下面调整矩阵

int[] coverLC=new int[pnum+wnum]; //要被标记的行列，0-pnum-1为行，pnum以后为列

Arrays.fill(coverLC, -1);

//没有找到合适0元素的行做标记

for(i=0;ipnum;i++)

if(lzerob[i]==false)coverLC[i]=i;

//对已经标记的行上的0元素所在的列做标记

for(i=0;ipnum;i++)

if(coverLC[i]!=-1){

for(j=0;jwnum;j++){

if(costC[coverLC[i]][j]==0)

coverLC[pnum+j]=j;

}

}

//对已经标记的列上的已经选中的0元素所在的行做标记

for(j=0;jwnum;j++){

if(coverLC[pnum+j]!=-1){

for(i=0;irzerop.lengthrzerop[i]!=-1;i+=2){

if(rzerop[i+1]==j)

coverLC[rzerop[i]]=rzerop[i];

}

}

}

//确定能找出新最小值的区域，直线覆盖掉没有打勾的行，打勾的列,最终coverLC[x]!=-1就是能选择的数

for(i=0;iwnum;i++){

if(coverLC[pnum+i]!=-1)coverLC[pnum+i]=-1;

else coverLC[pnum+i]=i;

}

//从区域中找出最小元素

int nmin=-1;

for(i=0;ipnum;i++){

if(coverLC[i]==-1)continue;

for(j=0;jwnum;j++){

if(coverLC[pnum+j]==-1)continue;

if(nmin==-1)nmin=costC[i][j];

else nmin=nmincostC[i][j]?costC[i][j]:nmin;

}

}

//打勾的列加上nmin,打勾的行减去nmin,记录0个数的数组作相应变化

for(j=0;jwnum;j++){

if(coverLC[pnum+j]==-1){

for(i=0;ipnum;i++){

if(costC[i][j]==0)lzeroa[i]-=1;

costC[i][j]+=nmin;

}

}

}

for(i=0;ipnum;i++){

if(coverLC[i]!=-1){

for(j=0;jwnum;j++){

costC[i][j]-=nmin;

if(costC[i][j]==0)lzeroa[i]+=1;

}

}

}

whilenum++;

if(whilenum==100){

System.out.println("100次之内矩阵调整没有找到");

return null;

}

}

return rzerop;

}

/*

* 测试矩阵costC是否有解，已经通过变换或者调整得到的矩阵

*/

public static boolean awpIsSolution(int[][] costC,int pnum,int wnum,int[] lzeroa,boolean[] lzerob,int[] rzerop){

int i,j,rzeropi=0;

for(int p=0;ppnum;p++){ //开始按照匈牙利法划去0所在的行列

//查找0元素个数最少的行

for(i=0;ipnum;i++){

if(lzerob[i]||lzeroa[i]1)continue; //如果某行已经查找过或者没有0元素，可能被划去了

if(lzeroa[pnum]!=-1lzeroa[i]lzeroa[lzeroa[pnum]])lzeroa[pnum]=i;

else if(lzeroa[pnum]==-1) lzeroa[pnum]=i;

}

//没有找到足够的不在同一行同一列的0元素，需要对矩阵进行调整，如果lzeroa[pnum]有值，则说明该行一定能找到

if(lzeroa[pnum]==-1){

return false;

}

//划去找到的行中没有被覆盖的0元素所在的行列

for(j=0;jwnum;j++){

if(costC[lzeroa[pnum]][j]!=0)continue;

//第一次找0元素最少的行

if(rzeropi==0){

rzerop[rzeropi++]=lzeroa[pnum];

rzerop[rzeropi++]=j;

lzerob[lzeroa[pnum]]=true; //找到第lzeroa[pnum]行，第j列0元素

//划去所在的行列时 lzeroa做相应的变化

for(i=0;ipnum;i++){

if(i!=lzeroa[pnum]costC[i][j]==0)

lzeroa[i]-=1;

}

lzeroa[pnum]=-1;

break;

}

//找到的0元素是否被划去

for(i=0;irzeropi(lzeroa[pnum]!=rzerop[i]j!=rzerop[i+1]);i+=2);

//如果被划去则找该行下一个0元素

if(irzeropi)continue;

rzerop[rzeropi++]=lzeroa[pnum];

rzerop[rzeropi++]=j;

lzerob[lzeroa[pnum]]=true;

for(i=0;ipnum;i++){

if(i!=lzeroa[pnum]costC[i][j]==0)

lzeroa[i]-=1;

}

lzeroa[pnum]=-1;

break;

}

}

return true;

}

}