第五届上海大学程序的设计联赛冬季赛题目分析.ppt

看个例子： 1 2 4 5 3 1 2 3 4 5 1 2 3 4 5 转化 最大匹配数：3 最小覆盖路径数=5-3=2 至此，简化的问题已经解决，那么原问题怎么解决呢？ 深入的思考后，我们应该可以发现，对原问题来说，两点之间的关系是能否直接或间接地到达。 于是，图的边的关系转化为一种连通关系，即图的传递闭包。我们可以通过Floyd-Warshall算法轻松解决。于是，整个问题就得以解决了。 核心代码(1)——Floyd-Warshall求传递闭包 void prework() { for(int k=0;kN;++k) for(int i=0;iN;++i) { if(i==k) continue; for(int j=0;jN;++j) { if(j==k||j==i) continue; if(G[i][k]G[k][j]) G[i][j]=1; } } for(int i=0;iN;++i) for(int j=0;jN;++j) if(G[i][j]) map[i].push_back(j); } 核心代码(2)——匈牙利算法求二分图最大匹配 int hungary() { int ret=0; memset(matx,0xff,sizeof(matx)); memset(maty,0xff,sizeof(maty)); for(int i=0;inx;++i) { if(matx[i]0) { memset(fy,0,sizeof(fy)); ret+=path(i); } } return ret; } 这道题目有相当的现实意义，在很多图形图像处理软件中，都会出现类似的操作。 题意是这样的，每次对一个星星（多边形）进行4种变换，分别为缩放(S)，以源点为圆心逆时针旋转(A)，平移(L)和反向(R)。 可以看出，这道题目就是一些坐标变换，我们可以手工推一下这些坐标变换的公式即可。 当然，也可以用坐标矩阵变换。 这题应该注意题意的理解。 核心代码(1)——矩阵相乘 void leftMul(Matrix other) { Matrix mtx; REP(i,3) REP(j,3){ mtx.arr[i][j] = 0.0f; REP(k,3){ mtx.arr[i][j] += other.arr[i][k] * arr[k][j]; } } REP(i,3) REP(j,3) arr[i][j] = mtx.arr[i][j]; } void rightMul(Point pt){ Point t; t.x = arr[0][0] * pt.x + arr[0][1] * pt.y + arr[0][2]; t.y = arr[1][0] * pt.x + arr[1][1] * pt.y + arr[1][2]; pt.x=t.x; pt.y=t.y; } 核心代码(2)——矩阵相乘坐标变换 switch( tran.order[k] ){ case S:mtx.arr[0][0] = tran.s; mtx.arr[1][1] = tran.s; break; case A:mtx.arr[0][0] = cos(tran.a); mtx.arr[0][1] = -1 * sin(tran.a); mtx.arr[1][0] = sin(tran.a); mtx.arr[1][1] = cos(tran.a); break; case L:mtx.arr[0][2] = tran.x; mtx.arr[1][2] = tran.y; break; case R: switch(tran.r){ case X:mtx.arr[1][1] = -1; break; case Y:mtx.arr[0][0] = -1; break; } break; } ident.leftMul(mtx); 这题叙述较繁，主要为了做广告。其实题意很简单，做下字符串比较就可以了。 如果不明白的话就多读几遍题吧~~ 核心代码 #include iostream #includestring using namespace std; int main() { string s; int n; cinn; for(int t1=0;t1n;++t1) { cins;