對酒當歌,人生幾何? 譬如朝露,去日苦多

2017年11月

网络流之最大流

1.EK算法

跑一遍bfs找到这条路上的最小边minn,sum+=minn,回溯,正向边-minn,反向边+minn。重复这个过程直到没有路可跑。

2.FF算法

跑dfs找到终点,确定最小边minn,回溯,正向边-minn,反向边+minn,sum+=minn,重复整个过程直到没有路可跑。

3.Dinic算法

bfs建立图层,dfs深搜。

1.学习链接:http://blog.csdn.net/mystery_guest/article/details/51910913

typedef struct node
{
    int data;
    struct node *next;
}node,*linklist;
//node *和linklist同为结构体指针类型
//这两种类型定义本质上是等价的
//为了提高程序的可读性,通常习惯上
//用linklist定义头指针变量

 

1.计算机内存划分

首先把计算机看成一个学生公寓楼,每个房间就是一个内存单元,每个房间号就是存储单元的地址(计算机中地址编码的最基本单位是字节(每个字节由8个二进制位组成))。

2.普通变量与指针变量的区分(其实指针类型的存放的是指针,另外就是指针还能指向另一个地方)

int a;
int *a;

这样几乎没有什么不一样,房间名字都是a,但是一个存放int型变量

一个存放地址。

如果p存放了一个地址,那么*p就指向存放这个地址的房间

#include<stdio.h>
int main()
{
    int *p;//声明p是一个int型的指针
    int a=10;
    p=&a;
    printf("%d\n",*p);//输出指针p所指向的内容
    return 0;
}

还用一种错误用法(我感觉是错的,不然指针意义何在?)

#include<stdio.h>
int main()
{
    int *p;
    scanf("%d",&p);//&p取p的地址,然后把一个数放进去
    //说好的只能存地址呢?
    //还能这样用,也是醉了
    printf("%d\n",p);
    return 0;
}

 

3.定义指针空间和new一个空间的区别

int *p[10];

int *p;
p=new int[10];

 

定义一个指针的空间,是开了几个房间只能存储指针型

而new一个空间则是相当于开了一个数组(不知道内部怎么实现的)

区分办法

这样可以运行

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int *p;
    p=new int[10];
    p[0]=1;
    printf("%d\n",p[0]);
    return 0;
}

 

这样不可以运行

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int *p[10];
    //p=new int[10];
    p[0]=1;
    printf("%d\n",p[0]);
    return 0;
}

 

错误错误用法,跟2的错误用法差不多

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int *a[10];
    for(int i=0;i<3;i++)
    {
        scanf("%d",&a[i]);//取出a[i]的地址,然后向里面放东西
        //没有了指针的意义
    }
    for(int i=0;i<3;i++)
        printf("%d ",a[i]);
    return 0;
}

 

1.数据,数据元素,数据项,数据对象

数据{ {数据对象},{数据元素{数据项} } }

数据元素是数据的基本单位。

数据项是组成数据元素的,有独立含义的,不可分割的最小单位。

2.数据结构

数据结构是相互之间存在一种或多种特定关系的(数据元素)的集合。

(1)逻辑结构

集合结构,线性结构,树结构,图结构

(2)存储结构

顺序存储结构,链式存储结构

3.算法时间复杂度和空间复杂度

只需注意常数的时间复杂度是O(1)

1.c语言下二者的意义

typedef struct用法

#include <stdio.h>
typedef struct node
{
    int x;
    int y;
}stu;
//struct node和stu都代表数据类型
//所以有两种定义变量的形式,如下
//也可以不写node,但是只能用stu定义了
int main()
{
    struct node b;
    stu a;
    a.x=1;
    a.y=2;
    b.x=3;
    b.y=4;
    printf("%d %d\n",a.x,a.y);
    printf("%d %d\n",b.x,b.y);
    return 0;
}

struct 用法

#include <stdio.h>
struct node
{
    int x;
    int y;
};
//struct node代表数据类型
//所以只有一种定义方式
int main()
{
    struct node b;
    b.x=3;
    b.y=4;
    printf("%d %d\n",b.x,b.y);
    return 0;
}

2.c++中两种用法的意义

struct 用法

#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
    int x;
    int y;
}stu;
//数据类型是node,stu是数据元素
int main()
{
    stu.x=1;
    stu.y=2;
    cout<<stu.x<<" "<<stu.y<<endl;
    return 0;
}

typedef struct 的用法

#include<iostream>
#include<algorithm>
using namespace std;
typedef struct node
{
    int x;
    int y;
}stu;
//数据类型是struct node和stu,
//所以定义数据元素有两种方法
int main()
{
    struct node a;
    a.x=1;
    a.y=2;
    stu b;
    b.x=3;
    b.y=4;
    cout<<a.x<<" "<<a.y<<endl;
    cout<<b.x<<" "<<b.y<<endl;
    return 0;
}