day3讲课

清北学堂--刷题班

对拍：

不用加freopen，可以直接 用，加了也没关系
（和cin>>a,cout<<\a,方向相反。。。）
在data，std，brute程序中不需再加上freopen，输出到in.txt,out.txt,ans.txt,如果加上，这里可以这样写system("data.exe");
windows

while (true) 
{
    system("data.exe > in.txt"); // 让date.exe从in.txt读入
    system("std.exe < in.txt > out.txt"); // 让std.exe从in.txt中读入，输出到out.txt
    system("brute.exe < in.txt > ans.txt"); // 让brute.exe从in.txt中读入，输出到out.txt
    if (system("fc out.txt ans.txt")) break; //比较是否相同
}

ubuntu

   while (true) 
    {
        system("./data > in.txt");
        system("./std < in.txt > out.txt");
        system("./brute < in.txt > ans.txt");
        if (system("diff out.txt ans.txt")) break;
    }

自己写了一个

int t = 0;
while (true) { 
    system("data.exe > in.txt");
    system("std.exe < in.txt > out.txt");
    system("dp.exe < in.txt > ans.txt");
    if (system("fc out.txt ans.txt")) break;
    // 查看是否有差异，所以不同时，返回真 
}
测试发现，system，在devcpp下，algorithm，cstdlib，windows.h都包含，而且algorithm不需要命名空间

栈空间：

工具-编译选项-编译时加入以下命令（打勾）-加入下面的东西

-Wl,--stack=64000000

网络流

模型：源点汇点，每个管道有上限，最多流多少水，
一个源点，无限水，汇点，没有水，有许多管道，每个管道有上限，求做多流多少水

dinic
bfs()判断从s到t是否还可以流水，
dfs()流水，
反向边，推回去多少，

建图，反向建边，权值为0

bool bfs()
{
    memset(depth,0,sizeof(depth));
    int front=1,tail=1;
    q[1]=s;depth[s]=1;
    for (;front<=tail;)
    {
        int now=q[front++];
        for (edge *e=v[now];e;e=e->next)
            if (!depth[e->e] && e->f) 
            {
                depth[e->e]=depth[now]+1;
                q[++tail]=e->e;
                if (e->e==t) return true; // 可以流到t
            }
    }
    return false;
}

int dfs(int now,int cur_flow) // now 点，cur_flow可以流多少，
{
    if (now==t) return cur_flow;
    int rest=cur_flow; // 剩余的可以流的量
    for (edge *e=v[now];e;e=e->next)
        if (depth[e->e]==depth[now]+1 && 
            e->f && rest) { // 这条边可以走，有剩余的流量，深度
                int new_flow=dfs(e->e,min(rest,e->f)); // 如果边的容量大于剩余的，让剩余的都流，否则，流最多的，即边的容量。
                rest-=new_flow; // 剩余的可以流的-新流的
                e->f-=new_flow; 
                e->op->f+=new_flow;
            }
    return cur_flow-rest; // 初始的可以流的-现在剩余的=流走的
}

void dinic()
{
    int ans=0;
    while (bfs())
        ans+=dfs(s,INF);
}

二分图匹配
源点S与所有左边的点连边，容量为1，然后建汇点T，让所有右边的点与T连边，容量为1，中间的边容量为1

题目：左边的点有权值，右边的点有权值，中间的边匹配上有权值，
S到左边的点的容量为左边的点的权值，右边的点到T的边的容量为右边的点的权值，中间的边的权值为中间的边的权值，跑网络流最大流，
答案：ans 或者 所有权值-ans

关于考试

留下时间弃疗 （5~10分钟），检查文件位置，文件名，中间调试信息，freopen，编译，文件放在相应的位置
最后调试，很紧张，可能忘记很多细节，忘记很多东西。

中间的调试信息，输出到

一般
freopen("gg.out","w",stdout);
printf(tiaoshixinxi);

改进（不建议使用）
fprintf(stderr,"%d\n",gg); // 输出到屏幕

另一种改进
FILE *f=fopen("gg.debug","w");
fprintf(f,"%d\n",gg);

字符串
strlen 不是O(1),O(长度)
错误

char s[1010];
scanf("%s",s);
for (int a=0; a<stalen(s); ++a) // n^2

正确

char s[1010];
scanf("%s",s);
int len = strlen(s);
for (int a=0; a<len; ++a) 

输入不定长的东西
while (~scanf("%d",&n))
while (scanf("%d",&n)!=EOF)
while (cin>>n)

考前训练模式

每天找一套题，下午评讲完，晚上找点题

数学知识

范围：
人教版任何一本书，都有可能出现

防止并查集被卡的：
按质（an zhi）合并
50%的将p1->p2,50%的将p2->p1
（启发式合并?）

by zhx