The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

#

C++内嵌汇编相关

一、 优点

        使用内联汇编可以在 C/C++ 代码中嵌入汇编语言指令,而且不需要额外的汇编和连接步骤。在 Visual C++ 中,内联汇编是内置的编译器,因此不需要配置诸如 MASM 一类的独立汇编工具。这里,我们就以 Visual Studio .NET 2003 为背景,介绍在 Visual C++ 中使用内联汇的相关知识(如果是早期的版本,可能会有些许出入)。

        内联汇编代码可以使用 C/C++ 变量和函数,因此它能非常容易地整合到 C/C++ 代码中。它能做一些对于单独使用 C/C++ 来说非常笨重或不可能完成的任务。

        内联汇编的用途包括:

        * 使用汇编语言编写特定的函数;
* 编写对速度要求非常较高的代码;
* 在设备驱动程序中直接访问硬件;
* 编写 naked 函数的初始化和结束代码。


二、 关键字

        使用内联汇编要用到 __asm 关键字,它可以出现在任何允许 C/C++ 语句出现的地方。我们来看一些例子:

        * 简单的 __asm 块:

            __asm
{
MOV AL, 2
MOV DX, 0xD007
OUT AL, DX
}

        * 在每条汇编指令之前加 __asm 关键字:

            __asm MOV AL, 2
__asm MOV DX, 0xD007
__asm OUT AL, DX

        * 因为 __asm 关键字是语句分隔符,所以可以把多条汇编指令放在同一行:

            __asm MOV AL, 2      __asm MOV DX, 0XD007      __asm OUT AL, DX

        显然,第一种方法与 C/C++ 的风格很一致,并且把汇编代码和 C/C++ 代码清楚地分开,还避免了重复输入 __asm 关键字,因此推荐使用第一种方法。

        不像在 C/C++ 中的“{}”,__asm 块的“{}”不会影响 C/C++ 变量的作用范围。同时,__asm 块可以嵌套,而且嵌套也不会影响变量的作用范围。

        为了与低版本的 Visual C++ 兼容,_asm 和 __asm 具有相同的意义。另外,Visual C++ 支持标准 C++ 的 asm 关键字,但是它不会生成任何指令,它的作用仅限于使编译器不会出现编译错误。要使用内联汇编,必须使用 __asm 而不是 asm 关键字。


三、 汇编语言

1. 指令集

        内联汇编支持 Intel Pentium 4 和 AMD Athlon 的所有指令。更多其它处理器的指令可以通过 _EMIT 伪指令来创建(_EMIT 伪指令说明见下文)。

2. MASM 表达式

        在内联汇编代码中,可以使用所有的 MASM 表达式(MASM 表达式是指用来计算一个数值或一个地址的操作符和操作数的组合)。

3. 数据指示符和操作符

        虽然 __asm 块中允许使用 C/C++ 的数据类型和对象,但它不能使用 MASM 指示符和操作符来定义数据对象。这里特别指出,__asm 块中不允许 MASM 中的定义指示符(DB、DW、DD、DQ、DT 和 DF),也不允许使用 DUP 和 THIS 操作符。MASM 中的结构和记录也不再有效,内联汇编不接受 STRUC、RECORD、WIDTH 或者 MASK。

4. EVEN 和 ALIGN 指示符

        尽管内联汇编不支持大多数 MASM 指示符,但它支持 EVEN 和 ALIGN。当需要的时候,这些指示符在汇编代码里面加入 NOP 指令(空操作)使标号对齐到特定边界。这样可以使某些处理器取指令时具有更高的效率。

5. MASM 宏指示符

        内联汇编不是宏汇编,不能使用 MASM 宏指示符(MACRO、REPT、IRC、IRP 和 ENDM)和宏操作符(<>、!、&、% 和 .TYPE)。

6. 段

        必须使用寄存器而不是名称来指明段(段名称“_TEXT”是无效的)。并且,段跨越必须显式地说明,如 ES:[EBX]。

7. 类型和变量大小

        在内联汇编中,可以用 LENGTH、SIZE 和 TYPE 来获取 C/C++ 变量和类型的大? ?

        * LENGTH 操作符用来取得 C/C++ 中数组的元素个数(如果不是一个数组,则结果为 1)。
* SIZE 操作符可以获取 C/C++ 变量的大小(一个变量的大小是 LENGTH 和 TYPE 的乘积)。
* TYPE 操作符可以返回 C/C++ 类型和变量的大小(如果变量是一个数组,它得到的是数组中单个元素的大小)。

        例如,程序中定义了一个 8 维的整数型变量:

            int iArray[8];

        下面是 C 和汇编表达式中得到的 iArray 及其元素的相关值:

            __asm                       C                                       Size

            LENGTH iArray               sizeof(iArray)/sizeof(iArray[0])        8
SIZE iArray                 sizeof(iArray)                          32
TYPE iArray                 sizeof(iArray[0])                       4

8. 注释

        内联汇编中可以使用汇编语言的注释,即“;”。例如:

            __asm MOV EAX, OFFSET pbBuff      ; Load address of pbBuff

        因为 C/C++ 宏将会展开到一个逻辑行中,为了避免在宏中使用汇编语言注释带来的混乱,内联汇编也允许使用 C/C++ 风格的注释。

9. _EMIT 伪指令

        _EMIT 伪指令相当于 MASM 中的 DB,但是 _EMIT 一次只能在当前代码段(.text 段)中定义一个字节。例如:

            __asm
{
JMP _CodeLabel

                _EMIT 0x00            ; 定义混合在代码段的数据
_EMIT 0x01

            _CodeLabel:               ; 这里是代码
_EMIT 0x90            ; NOP指令
}

10. 寄存器使用

        一般来说,不能假定某个寄存器在 __asm 块开始的时候有已知的值。寄存器的值将不能保证会从 __asm 块保留到另外一个 __asm 块中。

        如果一个函数声明为 __fastcall 调用方式,则其参数将通过寄存器而不是堆栈来传递。这将会使 __asm 块产生问题,因为函数无法被告知哪个参数在哪个寄存器中。如果函数接收了 EAX 中的参数并立即储存一个值到 EAX 中的话,原来的参数将丢失掉。另外,在所有声明为 __fastcall 的函数中,ECX 寄存器是必须一直保留的。为了避免以上的冲突,包含 __asm 块的函数不要声明为 __fastcall 调用方式。

        * 提示:如果使用 EAX、EBX、ECX、EDX、ESI 和 EDI 寄存器,你不需要保存它。但如果你用到了 DS、SS、SP、BP 和标志寄存器,那就应该用 PUSH 保存这些寄存器。

        * 提示:如果程序中改变了用于 STD 和 CLD 的方向标志,必须将其恢复到原来的值。


四、 使用 C/C++ 元素

1. 可用的 C/C++ 元素

        C/C++ 与汇编语言可以混合使用,在内联汇编中可以使用 C/C++ 变量以及很多其它的 C/C++ 元素,包括:

        * 符号,包括标号、变量和函数名;
* 常量,包括符号常量和枚举型成员;
* 宏定义和预处理指示符;
* 注释,包括“/**/”和“//”;
* 类型名,包括所有 MASM 中合法的类型;
* typedef 名称,通常使用 PTR 和 TYPE 操作符,或者使用指定的的结构或枚举成员。

        在内联汇编中,可以使用 C/C++ 或汇编语言的基数计数法。例如,0x100 和 100H 是相等的。

2. 操作符使用

        内联汇编中不能使用诸如“<<”一类的 C/C++ 操作符。但是,C/C++ 和 MASM 共有的操作符(比如“*”和“[]”操作符),都被认为是汇编语言的操作符,是可以使用的。举个例子:

            int iArray[10];

            __asm MOV iArray[6], BX                 ; Store BX at iArray + 6 (Not scaled)
iArray[6] = 0;                          // Store 0 at iArray+12 (Scaled)

        * 提示:在内联汇编中,可以使用 TYPE 操作符使其与 C/C++ 一致。比如,下面两条语句是一样的:

            __asm MOV iArray[6 * TYPE int], 0       ; Store 0 at iArray + 12
iArray[6] = 0;                          // Store 0 at iArray + 12

3. C/C++ 符号使用

        在 __asm 块中可以引用所有在作用范围内的 C/C++ 符号,包括变量名称、函数名称和标号。但是不能访问 C++ 类的成员函数。

        下面是在内联汇编中使用 C/C++ 符号的一些限制:

        * 每条汇编语句只能包含一个 C/C++ 符号。在一条汇编指令中,多个符号只能出现在 LENGTH、TYPE 或 SIZE 表达式中。
* 在 __asm 块中引用函数必须先声明。否则,编译器将不能区别 __asm 块中的函数名和标号。
* 在 __asm 块中不能使用对于 MASM 来说是保留字的 C/C++ 符号(不区分大小写)。MASM 保留字包含指令名称(如 PUSH)和寄存器名称(如 ESI)等。
* 在 __asm 块中不能识别结构和联合标签。

4. 访问 C/C++ 中的数据

        内联汇编的一个非常大的方便之处是它可以使用名称来引用 C/C++ 变量。例如,如果 C/C++ 变量 iVar 在作用范围内:

            __asm MOV EAX, iVar      ; Stores the value of iVar in EAX

        如果 C/C++ 中的类、结构或者枚举成员具有唯一的名称,则在 __asm 块中可以只通过成员名称来访问(省略“.”操作符之前的变量名或 typedef 名称)。然而,如果成员不是唯一的,你必须在“.”操作符之前加上变量名或 typedef 名称。例如,下面的两个结构都具有 SameName 这个成员变量:

            struct FIRST_TYPE
{
char *pszWeasel;
int SameName;
};

            struct SECOND_TYPE
{
int iWonton;
long SameName;
};

        如果按下面方式声明变量:

            struct FIRST_TYPE ftTest;
struct SECOND_TYPE stTemp;

        那么,所有引用 SameName 成员的地方都必须使用变量名,因为 SameName 不是唯一的。另外,由于上面的 pszWeasel 变量具有唯一的名称,你可以仅仅使用它的成员名称来引用它:

            __asm
{
MOV EBX, OFFSET ftTest
MOV ECX, [EBX]ftTest.SameName           ; 必须使用“ftTest”
MOV ESI, [EBX]. pszWeasel               ; 可以省略“ftTest”
}

        * 提示:省略变量名仅仅是为了书写代码方便,生成的汇编指令还是一样的。

5. 用内联汇编写函数

        如果用内联汇编写函数的话,要传递参数和返回一个值都是非常容易的。看下面的例子,比较一下用独立汇编和内联汇编写的函数:

            ; PowerAsm.asm
; Compute the power of an integer

            PUBLIC          GetPowerAsm
_TEXT           SEGMENT WORD PUBLIC 'CODE'
GetPowerAsm PROC
PUSH        EBP                 ; Save EBP
MOV         EBP, ESP            ; Move ESP into EBP so we can refer
; to arguments on the stack
MOV         EAX, [EBP+4]        ; Get first argument
MOV         ECX, [EBP+6]        ; Get second argument
SHL         EAX, CL             ; EAX = EAX * (2 ^ CL)
POP         EBP                 ; Restore EBP
RET                         ; Return with sum in EAX
GetPowerAsm ENDP
_TEXT           ENDS
END

        C/C++ 函数一般用堆栈来传递参数,所以上面的函数中需要通过堆栈位置来访问它的参数(在 MASM 或其它一些汇编工具中,也允许通过名称来访问堆栈参数和局部堆栈变量)。

        下面的程序是使用内联汇编写的:

            // PowerC.c

            #i nclude <Stdio.h>

            int GetPowerC(int iNum, int iPower);

            int main()
{
printf("3 times 2 to the power of 5 is %d\n", GetPowerC( 3, 5));
}

            int GetPowerC(int iNum, int iPower)
{
__asm
{
MOV EAX, iNum       ; Get first argument
MOV ECX, iPower ; Get second argument
SHL EAX, CL         ; EAX = EAX * (2 to the power of CL)
}
// Return with result in EAX
}

        使用内联汇编写的 GetPowerC 函数可以通过参数名称来引用它的参数。由于 GetPowerC 函数没有执行 C 的 return 语句,所以编译器会给出一个警告信息,我们可以通过 #pragma warning 禁止生成这个警告。

        内联汇编的其中一个用途是编写 naked 函数的初始化和结束代码。对于一般的函数,编译器会自动帮我们生成函数的初始化(构建参数指针和分配局部变量等)和结束代码(平衡堆栈和返回一个值等)。 使用内联汇编,我们可以自己编写干干净净的函数。当然,此时我们必须自己动手做一些有关函数初始化和扫尾的工作。例如:

            void __declspec(naked) MyNakedFunction()
{
// Naked functions must provide their own prolog.
__asm
{
PUSH EBP
MOV ESP, EBP
SUB ESP, __LOCAL_SIZE
}

                .
.
.

                // And we must provide epilog.
__asm
{
POP EBP
RET
}
}

6. 调用 C/C++ 函数

        内联汇编中调用声明为 __cdecl 方式(默认)的 C/C++ 函数必须由调用者清除参数堆栈,下面是一个调用 C/C++ 函数例子:

            #i nclude <Stdio.h>

            char szFormat[] = "%s %s\n";
char szHello[] = "Hello";
char szWorld[] = " world";

            void main()
{
__asm
{
MOV         EAX, OFFSET szWorld
PUSH        EAX
MOV         EAX, OFFSET szHello
PUSH        EAX
MOV         EAX, OFFSET szFormat
PUSH        EAX
CALL        printf

                    // 压入了 3 个参数在堆栈中,调用函数之后要调整堆栈
ADD         ESP, 12
}
}

        * 提示:参数是按从右往左的顺序压入堆栈的。

        如果调用 __stdcall 方式的函数,则不需要自己清除堆栈。因为这种函数的返回指令是 RET n,会自动清除堆栈。大多数 Windows API 函数均为 __stdcall 调用方式(仅除 wsprintf 等几个之外),下面是一个调用 MessageBox 函数的例子:

            #i nclude <Windows.h>

            TCHAR g_tszAppName[] = TEXT("API Test");

            void main()
{
TCHAR tszHello[] = TEXT("Hello, world!");

                __asm
{
PUSH        MB_OK OR MB_ICONINFORMATION
PUSH        OFFSET g_tszAppName             ; 全局变量用 OFFSET
LEA         EAX, tszHello                   ; 局部变量用 LEA
PUSH        EAX
PUSH        0
CALL        DWORD PTR [MessageBox]      &

//****************************************************************************

转自:http://hi.baidu.com/xocoder/blog/item/55dd5a12975d6a28dd5401e7.html

posted @ 2010-04-04 02:11 abilitytao 阅读(527) | 评论 (0)编辑 收藏

TOPCODER SRM 466 小结

     摘要: 第一题 当成背包瞬秒。第二题 有个结论 就是只有完全平方数才有奇数个因子, 开始只是觉得能过样例,不一定对。后来展开公式才发现确实是这么一回事因为 如果 一个数n=a1^k1*a2^k2*a3^k3....就是将它进行素因子分解那么它的约束个数g(n)=(k1+1)*(k2+1)*(k3+1)*....(kn+1)如果要为奇数,那么所有括号里的数均为奇数,显然k1 to kn为偶数,该数必为完全平...  阅读全文

posted @ 2010-04-04 01:47 abilitytao 阅读(1423) | 评论 (0)编辑 收藏

苏东坡突围 —余秋雨

     摘要: 这便是黄州赤壁。赭红色的陡峭石坡直逼着浩荡东去的大江,坡上有险道可以攀登俯瞰,江面有小船可供荡桨仰望,地方不大,但一俯一仰之间就有了气势,有了伟大与渺小的比照,有了视觉空间的变异和倒错,因此也就有了游观和冥思的价值。客观景物只提供一种审美可能,而不同的游人才使这种可能获得不同程度的实现。苏东坡以自己的精神力量给黄州的自然景物注入了意味,而正是这种意味,使无生命的自然形式变成美。因此不妨说,苏东坡不仅是黄州自然美的发现者,而且也是黄州自然美的确定者和构建者。
  阅读全文

posted @ 2010-04-03 21:04 abilitytao 阅读(250) | 评论 (1)编辑 收藏

成熟 余秋雨

成熟,是——

一种明亮而不刺眼的光辉,

一种圆润而不腻耳的音响,

一种不再需要对别人察言观色的从容,

一种终于停止向周围申诉求助的大气,

一种不理会哄闹的微笑,

一种洗涮了偏激的淡漠,

一种无须声张的厚实,

一种并不陡峭的高度。

勃郁的豪情发过的酵,尖利的山峰收住了劲,湍急的溪流汇成了湖。

posted @ 2010-04-03 21:00 abilitytao 阅读(243) | 评论 (4)编辑 收藏

光庭杯 比赛小节

发现自己果然还是处在简单题,中等题能很快搞定,但是难题就是出不来的阶段,这可能和平时训练的题目难度有关。淡定。。。加油。。。
POJ 1830, 高斯消元

posted @ 2010-04-03 19:04 abilitytao 阅读(196) | 评论 (0)编辑 收藏

向量的旋转

向量的旋转

基础的2-D绕原点旋转

在2-D的迪卡尔坐标系中,一个位置向量的旋转公式可以由三角函数的几何意义推出。比如上图所示是位置向量R逆时针旋转角度B前后的情况。在左图中,我们有关系:

  x0 = |R| * cosA

  y0 = |R| * sinA

  =>

  cosA = x0 / |R|

  sinA = y0 / |R|

  在右图中,我们有关系:

  x1 = |R| * cos(A+B)

  y1 = |R| * sin(A+B)

  其中(x1, y1)就是(x0, y0)旋转角B后得到的点,也就是位置向量R最后指向的点。我们展开cos(A+B)和sin(A+B),得到

  x1 = |R| * (cosAcosB - sinAsinB)

  y1 = |R| * (sinAcosB + cosAsinB)

  现在把

  cosA = x0 / |R|

  sinA = y0 / |R|

  代入上面的式子,得到

  x1 = |R| * (x0 * cosB / |R| - y0 * sinB / |R|)

  y1 = |R| * (y0 * cosB / |R| + x0 * sinB / |R|)

  =>

  x1 = x0 * cosB - y0 * sinB

  y1 = x0 * sinB + y0 * cosB

  这样我们就得到了2-D迪卡尔坐标下向量围绕圆点的逆时针旋转公式。顺时针旋转就把角度变为负:

  x1 = x0 * cos(-B) - y0 * sin(-B)

  y1 = x0 * sin(-B) + y0 * cos(-B)

  =>

  x1 = x0 * cosB + y0 * sinB

  y1 = -x0 * sinB + y0 * cosB

  现在我要把这个旋转公式写成矩阵的形式,有一个概念我简单提一下,平面或空间里的每个线性变换(这里就是旋转变换)都对应一个矩阵,叫做变换矩阵。对一个点实施线性变换就是通过乘上该线性变换的矩阵完成的。好了,打住,不然就跑题了。

所以2-D旋转变换矩阵就是:

[cosA  sinA]      [cosA -sinA]
[-sinA cosA] 或者 [sinA cosA]

  我们对点进行旋转变换可以通过矩阵完成,比如我要点(x, y)绕原点逆时针旋转:

          [cosA  sinA]
[x, y] x  [-sinA cosA] = [x*cosA-y*sinA  x*sinA+y*cosA]
为了编程方便,我们把它写成两个方阵

[x, y]   [cosA  sinA]   [x*cosA-y*sinA  x*sinA+y*cosA]
[0, 0] x [-sinA cosA] = [0                        ]

也可以写成

[cosA -sinA]   [x 0]   [x*cosA-y*sinA  0]
[sinA  cosA] x [y 0] = [x*sinA+y*cosA  0]

三、2-D的绕任一点旋转

  下面我们深入一些,思考另一种情况:求一个点围绕任一个非原点的中心点旋转。

  我们刚刚导出的公式是围绕原点旋转的公式,所以我们要想继续使用它,就要把想要围绕的那个非原点的中心点移动到原点上来。按照这个思路,我们先将该中心点通过一个位移向量移动到原点,而围绕点要保持与中心点相对位置不变,也相应的按照这个位移向量位移,此时由于中心点已经移动到了圆点,就可以让同样位移后的围绕点使用上面的公式来计算旋转后的位置了,计算完后,再让计算出的点按刚才的位移向量逆位移,就得到围绕点绕中心点旋转一定角度后的新位置了。看下面的图


 


现在求左下方的蓝色点围绕红色点旋转一定角度后的新位置。由于红色点不在原点,所以可以通过红色向量把它移动到原点,此时蓝色的点也按照这个向量移动,可见,红色和蓝色点的相对位置没有变。现在红色点在原点,蓝色点可以用上面旋转变换矩阵进行旋转,旋转后的点在通过红色向量的的逆向量回到它实际围绕下方红色点旋转后的位置。
在这个过程中,我们对围绕点进行了三次线性变换:位移变换-旋转变换-位移变换,我们把它写成矩阵形式:
设红色向量为(rtx, rty)

[x y 1]   [1    0]   [cosA  sinA 0]   [1      0]   [x' y' -]
[0 1 0] x [0    0] x [-sinA cosA 0] x [0      0] = [-  -]
[0 0 1]   [rtx rty 1]   [0       1]   [-rtx -rty 1]   [-  -]

  最后得到的矩阵的x'和y'就是我们旋转后的点坐标。

线性变换 , 吕新民 你连这么简单的东西都将不清楚。。。。

posted @ 2010-04-03 18:58 abilitytao 阅读(1452) | 评论 (0)编辑 收藏

issue 43 多看看 多记记

43"To be an effective leader, a public official must maintain the highest ethical and moral standards."
   is a public official must maintain the highest ethical and moral standards to be an effective leader ,as the author asserts? I think we should take it to the case-to-case analysis.

   Admittedly, in some cases, such like monarchy countries and religious nations, high ethical and moral standards are remarkable for  leaders. Becaue those leaders are not only the politicians but also the spiritual leader. Their power don’t come from the Democratic elections ,but the religious belief. If their image of ethics collapse, it will threaten the leadership directly. Like dalai lama…Scandals on dalai lama

tends to render social chaos and breakdown of people's belief, which will even lead to a war at last. Therefore, high ethical and moral standards for spiritual or religious leaders are not only crucial, but also necessary.吹。。。。

   But in the democracy society, which operates by its scientific belief ,the leader’s personality or Moral Charm is not that significant as the ancient time. The really thing that count is the leader’s governing philosophy, the Economic Policy which can bring his people to a better life. He moral or ethics charm is just a private thing which are not very crucial.

So , the leaders in the democracy system, is just a screw in a large machine , which could be replaced by any suitable person and it has not much thing to do with the leader’s moral image in he public. Like Bill Clinton ,who are always mentioned by his sex scandal, is of course a good leader in the US history .

On the other hand, even in democratic societies, moral charisma is useful and helpful for political leaders. A candidate with high moral reputation is more likely to win a campaign, which is the beginning to become an effective leader. When it comes to a decision maker, if he or she is famous for good morality, the policies are usually easier to be accepted by public. Let's take the Chinese Premier Wen (Premier Wen in China) as an example, who played an important role in the rescue in Sichuan Earthquake which killed (claimed) more than seventy thousand lives in 2008(灾难常用句型:e.g The hurricane claimed more than 5000 lives。飓风夺去了5000人的生命). His mercy and devoted figure moved millions of people all over the world. As a result, his leadership in rescuing activity    rescue is convincing and his orders are implemented efficiency…Efficiently

 which saved thousands of people buried underground in time. In this case, there is no doubt that the leader's personal moral charm improves the effect of Premier Wen's leadership.

In the final analysis , the ethic and morality of public leader could be very significant in some cases , especially to that spiritual leaders and religious leaders and it also benefits the leaders from democratic society as well. However, we have to notice that the real standard to evaluate a leader should base on his or her political achievement.

 

posted @ 2010-04-03 11:12 abilitytao 阅读(318) | 评论 (0)编辑 收藏

the communication with a great mind ,my points.

Admittedly, every person is different and just as the saying goes there are no two leaves that are exectly the same ,leading the thought differs ,too. But on the other hand, I have to point out that it is perhaps no need to process such a communication when the answer is clear , the response is identified according to the significant principle that I have transmited.

posted @ 2010-04-02 14:00 abilitytao 阅读(148) | 评论 (0)编辑 收藏

特殊用途 Special ues for SGY

呵呵 看来用不着了, 此贴留作纪念^_^

posted @ 2010-03-31 22:12 abilitytao 阅读(172) | 评论 (0)编辑 收藏

POJ 3680 Intervals 最小费用流 神迹一般的构图

刚开始做的时候狂RE啊,还以为是自己的SPFA有问题,检查了很长时间...
更为神迹的是,System 居然返回一个我从来没有看到过的结果,囧~

做法是 先把所有的区间离散化 ,也就是只留端点,然后排序,去重,标号。
增加超级源超级汇s,t.
假设剩下n个点, 加上超级源超级汇是n+2个。超级源为0,汇为n+1.
从0开始,顺序建一条流量为k,费用为0的边,将所有点串起来。然后再根据所输入边的信息,找到对应点的位置,连一条流量是1,费用是-w的边,最后从s到t做最小费用。

比如说
3 1
1 3 2
2 3 4
3 4 8

将 1,3,2,3,3,4排序
变成 1 2 3 3 3 4
去重 1 2 3 4
然后 0->1 1->2 2->3 3->4 4->5 建边
再 1->3 2->3 3->4 建边 即可
注意这里只是数字刚好和位置相同 实际应该用位置信息连边 这个做过网络流的都知道吧 ,最后Minflow即可。

不过我还没有想明白为什么可以这样做,它的正确性如何证明呢?

posted @ 2010-03-30 19:45 abilitytao 阅读(2076) | 评论 (1)编辑 收藏

仅列出标题
共42页: First 16 17 18 19 20 21 22 23 24 Last