#include <iostream>
#include <algorithm>
using namespace std;
#define initSet(n,Arr) for(int i=0;i<n;++i)Arr[i]=i;
#define MAX 1<<30;
int graph[600][600];
// Stoer-Wagner Algorithm
int globalMinCut(int n){
// A is A set for Stoer-Wagner Algorithm
bool* A=new bool[n];
// V is vertex index
int* V=new int[n];
int* W=new int[n];
initSet(n,V);
int best=MAX;
while(n>1){
//the most tightly connected vertex.
int maxj=1;
// initialize set A and other vertex's weight
A[V[0]] = true;
for(int i=1; i<n; ++i){
A[V[i]]=false;
W[i]=graph[V[0]][V[i]];
if(W[i]>W[maxj])
maxj=i;
}
// find a min-cut
int prev=0,buf=n;
while(--buf){
// add it to A
A[V[maxj]]=true;
if(buf==1){
// update min cut
best=min(best,W[maxj]);
// merge prev and last vertex
for(int k=0; k<n; ++k)
graph[V[k]][V[prev]]=(graph[V[prev]][V[k]]
+=graph[V[maxj]][V[k]]);
V[maxj]=V[--n];
}
prev=maxj;
maxj=-1;
// update the weights
for(int j=1; j<n; ++j)
if(!A[V[j]]){
W[j]+=graph[V[prev]][V[j]];
if(maxj<0 || W[j]>W[maxj])
maxj=j;
}
}
}
delete[] A;
delete[] V;
delete[] W;
return best;
}
int main(){
// n - vertex number
// m - edge number
int n,m;
while(scanf("%d %d",&n,&m)==2){
memset(graph,0,sizeof(graph)/sizeof(bool));
// v-w is an edge with c weight
int v,w,c;
while(m--){
scanf("%d %d %d",&v,&w,&c);
graph[v][w]+=c;
graph[w][v]+=c;
}
// output min cut
printf("%d\n",globalMinCut(n));
}
}
int a=0;
const int *p1=&a; //指常量的指针，此处a可以是常量也可以不是，但结果是(*p1)不能再修改
int *const p2=&a; //常量指针，不可以改变p的指向，功能类似引用（但有区别）
const int *const p3=&a; //指常量的常量指针，上面两个特点综合一下
double a=0.0;
const int &b=a; //其实是先 int tmp=a;然后 const int &b=tmp; 因为b要引一个int对象，所以临时创建了一个
const int &c=0; //其实是先 int tmp=0;然后 const int &c=tmp; 同上，先创建一个对象
int *const &p=a; // 经检验，效果等同 int *const p=a;
// 数组习惯
vector<int> vct(10);
for(int i=0 ; i<vct.size() ; ++i)
vct[i]=i;
// STL 习惯
vector<int> vct;
for(int i=0 ; i<10; ++i)
vct.push_back(i);
for(vector<int>::iterator iter=vct.begin() ; iter!=vct.end() ; ++iter)
cout<< *iter << endl;
#include <iostream> //包含需要使用的头文件
class Sample; // 先声明一下类
// 声明一些会使用到该类的函数
istream& operator >( istream&, Sample&);
// 类定义
class Sample
{
public:
Sample(); //默认构造函数及其他构造函数
Sample( const Sample&); //拷贝构造函数，如果需要
~Sample(); //析构
Sample& operator = (const Sample&); //重载操作符
void setValue(int); //定义成员函数
private:
int _value; //定义成员变量
};
void putValues(int*);
void putValues(int[]);
void putValues(int[ 10 ]);
void putValues(int (&arr)[10]); //参数为10个int的数组，因为参数是引用的，即数组长度成为参数的一部分
void putValues(int matrix[][10], int rowSize); // 第一维长度为rowSize，第二维长度是10
void putValues( vector<int> &vec ); //vector是替代数组的最好类型
int func1(int a,int b=0,int c=0);
int func2(int a,int b,int c=0); // 初始化最右边参数
int func2(int a,int b=0,int c); //可以！此时b c都有缺省参数
int func2(int a,int b=0,int c=0); //错误，bc已经有缺省参数
int func3(int a,int b,int c=func1(1)); //缺省实参可以是任意表达式
int func4(...); // ellipsis 省略号，告知编译器，函数调用时，可以有0或多个实参，而类型未知
Matrix& func()
{
Matrix a;
return a; // 错误，结果将指向一个错误的位置
}
int& get_val( vector<int> &vi, int ix)
{
return vi[ix];
}
int ai[4] = {0,1,2,3};
vectorvec(ai, ai+4);
int main()
{
get_val(vec,0)++;
}
Matrix& get(Matrix *p)
{
Matrix *res = new Matrix(); //动态分配的，函数结束不会结束
*res=*p;
return *res;
}
int cmp1(const string &s1, const string &s2)
{
return 1;
}
int cmp2(const string &s1, const string &s2)
{
return 0;
}
int *pf(const string&, const string&amp;amp;amp;amp;amp;); // 错误，返回类型指针
int (*pv)(const string&, const string&amp;amp;amp;amp;amp;) = 0; //初始化，不指向任何东西
int (*pf)(const string&, const string&amp;amp;amp;amp;amp;) = cmp1; //正确,pf 是指向函数的指针
pf=cmp2; //赋值，可以
pf=&cmp1; //可以，同上
cmp1("a","b");
pf("a","b");
(*pf)("a","b"); //三个效果相同，返回1
int func1(const int &a,const int &amp;amp;amp;amp;amp;b);
int func2(const int &a,const int &amp;amp;amp;amp;amp;b);
typedef int (*PFV)(); //定义函数类型指针的typedef
PFV tc1[10]; // 函数指针数组长度为10
PFV tc2 = { func1, func2 }; // 初始化
tc1[0] = &func1; // 赋值
tc1[0](10,20); //调用
((*tc1)[0])(10,20); // 显式调用
int (*func(int))(int, int); // ff为函数，有一个int参数，返回一个指向函数的指针，该指针类型为 int (*)(int, int);
typedef int (*PF)(int, int);
PF ff( int ); //更优雅
typedef int func(int, int);
func ff(int); // 错误，返回类型不能是函数类型
extern "C" void exit(int);
extern "C"
{
int printf( const char* ...);
int scanf(const char* ...);
}
extern "C"
{
#include <cmath>
}
for( register int ix=0; ix
#include
auto_ptr< type_pointed_to > identifier( ptr_allocated_bynew );
auto_ptr< type_pointed_to > identifier( auto_ptr_of_same_type );
auto_ptr< type_pointed_to > identifier;
auto_ptr< int > pi(new int(1024));
new ( place_address ) type-specifier // 表达式格式
class Foo{};
char *buf = new char [ 1024 ];
Foo *pb = new ( buf ) Foo; //无须delete
delete[] buf;
<div id="soya_menus">
</div>
<script language="JavaScript">
var MENU_ITEMS = [
['Ray',{ href : 'http://raythking.blogspot.com/',target : "_blank" }],
['Google',null,[
['Web',{ href : 'http://www.google.com',target : "_blank"}],
['Image',{ href : 'http://images.google.com',target : "_blank"}],
['Video',{ href : 'http://video.google.com',target : "_blank"}]
]
],
['Baidu', null,[
['Index',{ href : 'http://www.baidu.com/',target : "_blank"}],
['Zhidao',{ href : 'http://zhidao.baidu.com/',target : "_blank"}]
]
],
['Sogou',{ href : 'http://www.sogou.com/',target : "_blank"}],
['About',{ href : 'javascript:alert(" This is a simple javascript menu !")',target : "_self"}]
];
function showSubMenu( tolist ){
var sublist = document.getElementById(tolist);
if(sublist.style.display == ""){
sublist.style.display = "none";
}else{
sublist.style.display = "";
}
}
function insertMenu(divarea){
document.getElementById(divarea).innerHTML=createMenu(MENU_ITEMS,"soya_menu");
showSubMenu("soya_menu");
}
function createMenu(menu_it,id_pre){
var html="<ul id='"+id_pre+"' style='display:none;padding-top:8px' >";
for( var i=0 ; i<menu_it.length; ++i){
var sub_id_pre=id_pre+"m"+i;
html += "<li>";
if(menu_it[i][1]){
html += "<a href='"+menu_it[i][1]+"'>";
html += menu_it[i][0];
html += "</a>";
}else if(menu_it[i][2]){
html += "<a href='"+menu_it[i][1].href+"' target='"+menu_it[i][1].target+"'>";
html += menu_it[i][0];
html += "</a>";
html += createMenu(menu_it[i][2],sub_id_pre);
}else{
html += menu_it[i][0];
}
html += "</li>";
}
html +="</ul>";
return html;
}
insertMenu("soya_menus");
</script>
99年ACM/ICPC 的final有一道蜜蜂的坐标的问题，非常有意思，和队友们讨论了许久都没能解决。记得那天做练习是我和肖筹划着用计算几何的方法估算出结果，虽然做法很独特，但毕竟是估算的，最后没有能过。后来我找了份解题报告，看到了解这类问题神奇地使用笛卡儿坐标，着实让人兴奋啊。所以准备了一份模板、数道类似问题和将蜜蜂坐标放在扫雷游戏里的应用，来一个蜜蜂问题的大汇总。
模板放在SHU ACM群里，含有一些处理正六边形拼成的坐标系的方法。
首先，蜂巢是由许多个正六边行无缝拼接而成的，这是一个美丽而奇特的自然结构，如图（图中程序是在解一道题时写的辅助程序，我也放在群与大家分享）：
题外话，先来讨论下为什么六边形可以无缝的拼接出一个平面，那么七边、八边行不行？其实是一个简单的小学题： 正n边形内角为 (n-2)*180/n ，要保证可以无缝拼接，就是一个圆可以被整数个n边形内角拼接，即 360=k*(n-2)*180/n => 2n=k(n-2)，用这个公式就能算一下是否正n边形能像六边行一样拼出一个平面了。
起初在遇到这样独特的结构时可能无法想象如何将其保存起来，可能会想到是不是做一个带六条链结点的链图？这样做的结果将是一个极难维护的链图，光是想到插入操作就起鸡皮疙瘩。
有一个十分巧妙的方法来储存这个怪异的结构：用二维数组。用二维数组保存四个方向或八个方向的东西肯定是很简单的，其实对于这个六向的结构，我们可以取二维数组的八向中的六向。即东、南、西、北、东北、西南（其实只要注意对称，六向可以随便取），这样相对的坐标向每个方向移动的偏移量就是：
东 南 西 北 东北 西南
x 1 0 -1 0 1 -1
y 0 -1 0 1 1 -1
到底正确与否呢，其实是必然正确的，只是我们损失了两个角（东南、西北），不过不碍事。通过上面这个方法不仅是保存了六边形的怪结构，而且也给这种结构指明了一个坐标表示的方法，在解题中这个概念很重要。
PKU 1134：
与蜜蜂坐标没关系的题目，只是样子是六边行的。题目意思是给出三行，每行代表一个方向，然后可以按任意顺序把数字放在这个方向的任意一列中（以abcba的顺序分配到abc里）。归纳一下可以得到以下结论， 最大的得分就是三行分别乘以下面的系数：
行1： a * 8 + b * 6 + c * 5
行2： a * 7 + b * 7 + c * 5
行3： a * 7 + b * 7 + c * 5 。所以枚举一下就可以求出最大值了。
PKU 2265：
这是非常简单、易上手的题目，熟悉两种坐标系对于解决蜜蜂问题很有帮助，这两个坐标系也是蜜蜂最常用的坐标，转换的方法就是直接上模板。
PKU 1870：
是99年FINAL的题目，除了用模板里的构造点来构造一个六边形结点（带XY轴坐标）以外，模板里有求两点间最短距离的函数。
求最短距离要以一点为原点，即用一点减去另一点的XY坐标。然后对相对的那个点的两种情况做处理：xy同正同负时，距离是max(|x|,|y|)；否则距离为距离是|x-y|。简单得想象一下就知道了。
PKU 1792：
是1870的升级版，除了要求最短的距离外，还需要求两个点间有多少种路径可以用最短的距离。其实求可能的路径数可以归约为求组合数的问题：
上图为例，在x>0 y>0的区域，最短距离是max(|x|,|y|),图中某点的最短距离很明显是 |x|，然后如何求路径数呢？这样思考，为了能到达那个点，所有路径在两点之间准没错吧（出了两点间的区域就不能最短距离了）。那在最短路径为d的情况下，取d中的一点让它或上或下（只要保证还在两点间的那块区域），不就可以得到一条新的路径？这样，在d中取c个点（c为最大的可变的点，或称关节），就是总路径数。那么总的路径数就是combine(d,c)了。巧合的是c的值情况与最短路径的值情况正好相反，即xy同正同负时，c为|x-y|；否则c为max(|x|,|y|)。
模板里有个函数实现此功能，不过自己写写也很简单的吧。
PKU 3036：
哈，在1792有点类似，不过做法完全不一样的题。求的是从原点出发到达距离为n的地方再回来的路径数。其实知道用动态规划和前面讲的六个方向的坐标的话，这道题目是非常简单的。动规方程见下：
dp[i][x][y] i表示距离原点i步；xy是点的坐标。
dp[i][x][y]= dp[i-1][x+1][y] + dp[i-1][x-1][y] + dp[i-1][x][y+1] +dp[i-1][x][y-1] + dp[i-1][x-1][y-1] + dp[i-1][x+1][y+1]
O X X X X O
X X X ===========> X X X
X X O 乘以变换矩阵 O X X
很明显，旋转后的不是原来使用的六向的坐标表示方法了。当然，调整变换矩阵的话，相信还是有办法解决的，但这毕竟是个较麻烦的活儿。
那么从后者的方向来考虑的话，事情就简单了很多。见下图：
按行走路线进行转换的思想就是上图所表现的，显而易见了吧。代码实现也是相当的简单。即将把原来的a方向的操作改为b方向操作等等。
这样的话，先输入第一种走法，正规化一下。然后输入第二种，做七次旋转（包括不转的那种），每次正规化后再比对两个集合就行了。
PKU 1518：
看上去很吓人的题目，跟计算几何又有关系，而且坐标系又是要六向的表示。Take it easy，先来看看一个扫雷游戏吧：
在扫雷游戏中有这样一个问题，鼠标点击了之后要出发事件，事件的参数只有鼠标点击的点的坐标(x,y)。求鼠标点击的是哪块雷区，知道了哪块雷区才可以做相应操作嘛。
通过平面坐标求六边形的坐标的方法其实满多的，在这里介绍一个简单的方法：
首先，要判断点是否在六边形内，经常使用的是用叉乘判断点对于凸边形的每个顶点是左转还是右转可以做到。不过这里不需要这么做，因为六边行都是紧凑得在一起，而且都是正多边形，所以求一下点到每个多边形中心的距离，然后取最小值可以找到它所在的六边形了（如果正好在边上，随便取哪个都一样）。
为了优化一点，不用对每个六边形都求一下它的中心与目标点的距离。可以先从距离估算出目标点的大致位置，然后包括大致位置的六边形在内，相邻的六个六边形再确定出最终点所在的六边形。
估算的方法是简单的计算几何（d是六边形边长，td是sqrt(3)*d/2，p是目标点）：
x = (int) Math.round((p.x * 2 / (3 * d)));
y = (int) Math.round(((-p.y + x * td) / (2 * td)));
知道了六边行的坐标，接下来的事情就容易了。求两坐标间最短路径，然后路径乘以2*td。再将具体的两个点与六边形中心的距离相加。就是结果了，当然要注意在同一个六边形内的两点是直接计算两点距离。
链接：
Ray's Blog: http://raythking.blogspot.com/
SHU-ACM-Group: http://groups-beta.google.com/group/shu-acm-group
Mineray: https://mineray.dev.java.net/
