Herman526 @ 2023-06-24 16:54:16
在解决网络流问题时，我使用了 ISAP。
#include<cstdio>
int h[201],e[5002],x[5002],r[201],d[201],q[201],g[201],n,m,s,t,u,v,z=1;
long long c[5002],w,l;
/*
h,x,c,e 分别为链式前向星的头指针、边的另一点、边权、后继；
r 是弧优化后的头指针，d 是点的深度，q 是队列，g[x] 是深度为 x 的点的个数
*/
bool y[201];
long long _(int a,long long b){
if(a==t)return l+=b,b;
long long f=0,o,p;
for(int i=r[a];i;i=e[i])if(c[i]&&d[x[r[a]=i]]+1==d[a]){
p=c[i];
if(p>b-f)p=b-f;
if(o=_(x[i],p)){
c[i]-=o,c[i^1]+=o;
if((f+=o)==b)return f;
}
}
if(!(--g[d[a]++]))d[s]=n;
g[d[a]]++;
return f;
}//dfs
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
while(m--){
scanf("%d%d%lld",&u,&v,&w);
if(u^v){
x[++z]=v,e[z]=h[u],c[h[u]=z]=w;
x[z|=1]=u,e[z]=h[v],h[v]=z;
}
}//添加双向边
y[q[0]=t]=1;
for(int i=0,j=1;i<j;i++)for(int k=h[q[i]];k;k=e[k])if(!y[x[k]])g[d[q[j++]=x[k]]=d[q[i]]+1]++,y[x[k]]=1;//bfs
while(d[s]<n){for(int i=1;i<=n;i++)r[i]=h[i];_(s,0x7fffffff);}
printf("%lld",l);
}在提交代码时，我遇到了一个意想不到的情况——测试点中，
printf("%d.",m);
scanf("%d%d%lld",&u,&v,&w);
if(u^v){
x[++z]=v,e[z]=h[u],c[h[u]=z]=w;
x[z|=1]=u,e[z]=h[v],h[v]=z;
}不出所料，在输入边
看到这里，我更不明白了，为什么
by Kanbe_Kotori @ 2023-06-24 17:16:03
数组开小了。边要开两倍
by Herman526 @ 2023-06-24 17:31:51
@0ccDreamer 哦，原来是这样！我记得你上次帮我调代码时也是因为数组太短导致错误的，看来这句话果真是对的啊！
by CleanIce @ 2023-06-28 11:17:53
@Herman526
动态数组了解一下？（既能够保证数组空间足够，又能保证数组空间不是很大，有些题目的数据范围故意比输入文件范围要大，卡你的内存）
不过注意释放内存，否则导致内存泄漏。
例如：
#include <cstdio>
using namespace std;
int main()
{
unsigned n; // 数组长度，动态数组长度可以为变量。
scanf("%u", &n); // 输入数组长度
int* array = new int[n]; // 创建动态数组，长度为 n，索引范围 1~n-1，使用 new 关键字（C 语言中使用 malloc() 函数）
// 动态数组的内存分配在内存池而不是栈内存，并返回内存池中分配的空间的指针。由于分配在内存池而不是栈内存，所以在命名空间结束时不会自动释放该动态变量的内存，需要手动释放。
// 因此动态分配 int 型变量应为：
int* a = new int;
*a = 1; // 初始化
// 处理数组……
delete[] array; // 手动释放动态数组内存，否则导致内存泄漏。
delete a; // 手动释放动态变量，否则导致内存泄漏。
// delete 语句是否添加括号取决于使用 new 时是否添加括号
// 不可以对通常变量（自动变量，存储在栈内存中）的指针使用 delete
// 但对空指针使用 delete 时安全的，此时 delete 不会做任何事情
// 同一个动态变量只可以被释放一次，否则可能误删其他数据
// 内存泄漏：某一块内存任然存在，但无法使用，导致无故占用内存，严重时导致操作系统崩溃
// 此处 array 和 a 都是正常的指针变量，命名空间结束后自动释放。但其指针指向的空间需要手动释放。
return 0;by Herman526 @ 2023-07-05 08:05:05
@CleanIce 其实我是会这个的，但是我觉得这样写比较繁琐，就没很常用。下次，如果需要省空间的话，我也可以试一试。
by CleanIce @ 2023-07-08 17:00:05
@Herman526
其实 C 语言的更繁琐……
同一个操作（动态分配一个 int 变量和长度为 100 的 int 型数组），用 C++ 和 C 写出来的代码（你会发现 C 语言的更繁琐，还不直观）：
C++：
int length = 100;
int* a = new int;
int* b = new int[length];
delete a;
delete[] b;C：（需要头文件 stdlib.h ）
int length = 100;
int *a = (int *) malloc(sizeof(int));
int *b = (int *) malloc(sizeof(int) * length);
free(a);
free(b);by Herman526 @ 2023-07-08 21:30:19
@CleanIce 真的是这样，果然 C++ 的会方便许多！但是 C 语言用一个函数就可以申请、释放空间，这是很神奇的，特别是 malloc，这东西看着像函数，前面却有一个数据类型。
by CleanIce @ 2023-07-09 10:12:56
@Herman526
malloc 和 free 本来是 Linux 系统的系统函数，用于在用户态内存的堆中申请内存。后来个大操作系统均有了这种功能，但函数名不一样。C 语言标准组织决定将 malloc 和 free 两个函数纳入标准库中，并且不同平台的编译器会将其解释为所在平台的内存申请函数，做到跨平台。
malloc 函数原型：
void *malloc(size_t size);其参数为所需要的内存大小（单位：字节）。在大多数平台上，size_t 被定义为 unsigned int。
返回值是一个特殊指针：void * 类型。编译器在编译指针时，会判断其指向类型，以判断代码的正确性（例如不能把 double * 类型的指针指向的数据赋给 short 型的变量），但编译后的机器代码中不包含类型信息。
而 void * 类型就是一个通用指针，编译器不会做类型检查。可以通过强制类型转换获得特定类型的指针。（这就是为什么 malloc 函数前有指针类型）
C++ 则把动态内存分配纳入语言中，关键字 new 和 delete 都是操作符。并且 C++ 会做分配检查。若分配失败（可能是堆内存不够，也可能是操作系统不允许），C++ 会产生一个叫 bad_alloc 的异常，使程序终止。但 C 语言的 malloc 函数在堆内存分配失败时仅仅只会返回空指针（即 C 语言头文件 stddef.h 中的宏定义 #define NULL 0，C++11 之后的关键字 null_ptr）。
by Herman526 @ 2023-07-09 10:25:18
@CleanIce 那么，以此看来，C++ 语言的动态内存分配的确更好一点，因为这个功能是 C++ 本身提供的，自然就更加方便，不需要调用任何标准库（好像 C++ 对于分配内存空间的通用性更强了）。另一方面，C++ 语言的安全性好像比 C 强，它可以让程序中止而不是继续运行，这也让我更加感觉到 C++ 语言的优势。