顺序结构与选择 2020-07-28 字数统计: 1.7k字 | 阅读时长: 6min 顺序结构与选择循序结构程序由若干条语句组成,各语句按照顺序一条一条地执行,这种结构叫做顺序结构。顺序结构是程序的最基本结构。 如下便是一个简单的顺序结构 1234567891011#include<cstdio>using namespace std;int main(){ int a,b,s; scanf("%d%d",&a,&b); s=a+b; printf("%d",s); return 0;} 展开全文 >>
OI省选知识点 2019-03-17 字数统计: 538字 | 阅读时长: 1min 数据结构 带权并查集 线段树合并 平衡树 Treap 随机平衡二叉树 FHQ Treap 分块 树套树 线段树套平衡树 平衡树套线段树 可并堆 左偏树 KDtree,四分树 可持久化数据结构(主席树等) 黑科技 展开全文 >>
字符串算法集锦 2019-03-02 字数统计: 5.9k字 | 阅读时长: 32min KMP时间复杂度为O(n)的字符串匹配算法。 应用:1.单一子串和模式串匹配P3375 【模板】KMP字符串匹配1234567891011121314151617181920212223242526272829303132333435#include<bits/stdc++.h>using namespace std;int f[1001000];//fail数组下标从1开始 char s1[1001000],s2[1001000];//字符串下表从0开始 int l1,l2;inline void kmp(){ for(register int i=1;i<l2;i++) //处理2~l2的fail数组(f[1]=0) { int j=f[i]; while(j&&s2[j]!=s2[i]) j=f[j]; f[i+1]=(s2[j]==s2[i])?j+1:0; }}inline void get(){ int j=0; for(register int i=0;i<=l1;i++) { while(j&&s1[i]!=s2[j]) j=f[j]; if(s1[i]==s2[j]) j++; if(j==l2) printf("%d\n",i-j+2); }}int main(){ scanf("%s",s1);//主串 scanf("%s",s2);//模式串 l1=strlen(s1); l2=strlen(s2); kmp(); get(); for(register int i=1;i<=l2;i++) printf("%d ",f[i]); return 0;} 字符串 展开全文 >>
二分图有关定理 2019-02-21 字数统计: 1.1k字 | 阅读时长: 3min 最小点覆盖定义:一个点为一条边的任意顶点,则称它为一个点覆盖;用最少点覆盖二分图的所有匹配为二分图的最小点覆盖 一个二分图的最小点覆盖等于该二分图的最大匹配 证明: 反证,若一个二分图的最小点覆盖不等于该二分图的最大匹配,则存在一条边未被覆盖,该二分图存在更大的匹配,不存在,证毕。 DAG的最小不相交路径覆盖 图论 网络流 展开全文 >>
网络流 2019-02-21 字数统计: 2.4k字 | 阅读时长: 14min 板子最大流1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include<bits/stdc++.h>using namespace std;const int INF = 0x7fffffff;const int N = 1e5+100;template<typename T>inline void read(T &a){ T f=1;a=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s<='9'&&s>='0'){a=a*10+s-'0';s=getchar();} a*=f;}int n,m,s,t;struct node{ int ne,to,w;}edge[200100];int head[N],cnt=1;inline void add(int u,int v,int w){ edge[++cnt].to=v; edge[cnt].ne=head[u]; edge[cnt].w=w; head[u]=cnt;}int d[N];queue<int> q;inline bool bfs(){ fill(d+1,d+1+n,-1); d[s]=0; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); for(register int i=head[u];i;i=edge[i].ne) { int v=edge[i].to; if(d[v]!=-1||edge[i].w<=0) continue; d[v]=d[u]+1; q.push(v); } } return d[t]!=-1;}int dinic(int u,int mn){ if(u==t||mn<=0) return mn; int flow=0,tmpf=0; for(register int i=head[u];i;i=edge[i].ne) { int v=edge[i].to; if(d[v]==d[u]+1&&(tmpf=dinic(v,min(mn,edge[i].w)))>0) { mn-=tmpf; flow+=tmpf; edge[i].w-=tmpf; edge[i^1].w+=tmpf; } if(!mn) break; } if(!flow) d[u]=0; return flow;}int u,v,w,ans;int main(){ read(n),read(m),read(s),read(t); for(register int i=1;i<=m;i++) { read(u),read(v),read(w); add(u,v,w); add(v,u,0); } while(bfs()) ans+=dinic(s,INF); printf("%d\n",ans); return 0;} 网络流 展开全文 >>