板子整理
2019-12-16 09:09:28来源：博客园 阅读 ()
板子整理
板子整理
目录
- 排序（快排及其原理、sort、归并、以及STL中的compare写法）
- 递归（排列问题、dfs、斐波拉契）
- 二分（主要为例题）
- dp问题汇总（背包、子序列、树形dp例题等等）
- 计算几何（凸包、叉积）
- 图算法（最小生成树、最大流、最短路径、二分图）
- 字符串匹配（有限自动机、KMP）
- FFT（各类应用）
- 常见小技巧（关闭输入输出流、快速幂）
一、排序
快排原理
int Partition(int i,int j){
while(i<=j){
while(a[i]<mid) i++;//mid是自己给出的分割线，小的在左，大的在右
while(a[j]>mid) j--;
if(i<=j){
int tmp;
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
i++;
j--;
}
}//结束后i即为分割点的下标
return i;
}sort
#include<algorithm>
sort(begin,end,cmp);//sort函数的写法，cmp可省略
sort(begin,end,less<int>());//升序
sort(begin,end,greater<int>());//降序
sort(str.begin(),str.end());//字符类型排序
sort(str.rbegin(),str.rend());//反向迭代器完成逆序
sort(x,x+4,cmp);//结构体排序
bool cmp(node x,node y)
{
if(x.a==y.a)
return x.b>y.b;
return x.a>y.a;
}归并排序
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
long long count=0;
void merge(int x[ ],int tmp[ ],int left,int leftend,int rightend)
{
int i=left, j=leftend+1, q=left;
while(i<=leftend && j<=rightend)
{
if(x[i]<=x[j]){
//count[4]++;
tmp[q++]=x[i++];
}
else{
count+=leftend-i+1;//这里为答案
tmp[q++]=x[j++];
}
}
while(i<=leftend)
tmp[q++]=x[i++];
while(j<=rightend)
tmp[q++]=x[j++];
for(i=left; i<=rightend; i++)
x[i]=tmp[i];
}
void mSort(int k[],int tmp[],int left,int right){
int center;
if (left<right){
center=(left+right)/2;
mSort(k,tmp,left,center);
mSort(k,tmp,center+1,right);
merge(k,tmp,left,center,right);
}
}
void mergeSort(int k[],int n){
int *tmp;
tmp=(int *)malloc(sizeof(int)*n);
if(tmp!=NULL){
mSort(k,tmp,0,n-1);
free(tmp);
}
}
int main(){
int n,a[100001];
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
mergeSort(a,n);
cout<<count;
}优先队列及其cmp写法
priority_queue<int,vector<int>,less<int> > q;// 从大到小
priority_queue<int,vector<int>,greater<int> > q;// 从小到大
priority_queue<pair<int,int> > q;//第一个为准，相等比第二个
priority_queue<node> q;//结构体，自定义排序
//(1) 重载bool operator<，写在结构体外面
struct node{
int x, y;
node(int x=0, int y=0):x(x),y(y){}
};
bool operator<(node a, node b){//可写成const node &a或者const node a
if(a.x > b.x) return 1;
else if(a.x == b.x)
if(a.y >= b.y) return 1;
return 0;
}
//(2) 重载bool operator<，写在结构体里面
struct node{
int x, y;
node(int x=0, int y=0):x(x),y(y){}
bool operator<(const node &b) const{
if(x > b.x) return 1;
else if(x == b.x)
if(y >= b.y) return 1;
return 0;
}
};
//(3) 友元函数
struct node{
int x, y;
node(int x=0, int y=0):x(x),y(y){}
friend bool operator<(const node&a, const node &b){
if(a.x > b.x) return 1;
else if(a.x == b.x)
if(a.y >= b.y) return 1;
return 0;
}
};
//(4) 重载(),自定义cmp
priority_queue<int, vector<int>, cmp> q;
struct node{
int x, y;
node(intx=0, int y=0):x(x),y(y){}
};
struct cmp{
bool operator()(const node &a, const node &b){
if(a.x> b.x) return 1;
else if(a.x == b.x)
if(a.y>= b.y) return 1;
return 0;
}
};二、递归
排列问题
//全排列
#include<stdio.h>
int n,a[50],b[50];
void f(int depth){
if(depth==0){
for(int i=0;i<n;i++){
printf("%d ",a[i]);
}
printf("\n");
}
else{
for(int i=1;i<=n;i++){
if(b[i]==0){
a[n-depth]=i;
b[i]=1;
f(depth-1);
b[i]=0;
}
}
}
}
int main(){
scanf("%d",&n);
f(n);
}
//给定n,m，输出从 1～n中选择 m个数的所有排列。 要求按照字典序输出。
void f(int depth){
int i;
if (depth==n-m){
for (i=0;i<m;i++){
printf("%d ",a[i]);
}
printf("\n");
return;
}
for (i=1;i<=n;i++){
if (b[i]==0){
a[n-depth]=i;
b[i]=1;
f(depth-1);
b[i]=0;
}
}
}
//从1~n中选取任意多（大于0）个数字，输出所有可能的选择方案
void f(int depth,int cur)
{
for (int i=cur+1;i<=n;i++)//从该数的下一个数开始递归
{
if (b[i]==0)
{
a[depth]=i;
b[i]=1;
for(int j=1;j<=depth;j++){
printf("%d",a[j]);
}
printf("\n");
f(depth+1,i);
b[i]=0;
}
}
}
int main(){
scanf("%d",&n);
f(1,0);
}
//类循环排列
#include <stdio.h>
#define MAX_N 10
int n, m;//相当于n重循环，每重循环长度为m
int rcd[MAX_N]; //记录每个位置填的数
void loop_permutation(int l){
int i;
if (l == n) { //相当于进入了n重循环的内层
for (i=0; i<n; i++){
printf("%d", rcd[i]);
if (i < n-1) printf(" ");
}
printf("\n");
return ;
}
for (i=0; i<m; i++){ //每重循环长度为m
rcd[l] = i; //在l位置放i
loop_permutation(l+1); //填下一个位置
}
}
int main(void){
while (scanf("%d%d", &n, &m) != EOF)
loop_permutation(0);
return 0;
} 食物链
现在给你n个物种和m条能量流动关系，求其中的食物链条数。
物种的名称为从1到n的编号。m条能量流动关系形如a b 表示能量从物种a 流向物种b。注意单独的一种孤立生物不算一条食物链。求食物链总数
//备忘录式递归
#include<stdio.h>
#include<stdlib.h>
#include<vector>
using namespace std;
vector<int> g[100005];
int in[100005]={},out[100005]={},vis[100005]={};
int dfs(int temp){
int sum=0;
if(in[temp]&&!out[temp]){
vis[temp]=1;
return 1;
}
if(vis[temp]) return vis[temp];
else{
for(int i=0;i<g[temp].size();i++){
sum+=dfs(g[temp][i]);
}
}
vis[temp]=sum;
return sum;
}
int main(){
int n,m,a,b,ans=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
g[a].push_back(b);
out[a]++;
in[b]++;
}
for(int i=1;i<=n;i++){
if(!in[i]&&out[i]){
ans+=dfs(i);
}
}
printf("%d",ans);
} 斐波拉契
//兔子问题
f(n)=f(n-1)+f(n-2);//普通情况
f(n)=f(n-1)+f(n-2)-f(n-10);//十天后衰老
f(n)=f(n-1)+f(n-2)-f(n-10);
f(n)=f(n)-f(n-10);//十天后死去,这是在循环完后再减
f(n)=f(n-1)+f(n-2)-f(n-10);
f(n)=f(n)-f(n-15);//十天后衰老,十五天后死去,这是在循环完后再减
//青蛙上台阶
f(n)=f(n-1)+f(n-2);//可以跳一阶或者两阶
f(n)=2*f(n-1);//可以跳1~n阶
f(n)=f(n-1)+f(n-2)+f(n-4)+f(n-5);//跳了一次三阶后，之后需要隔一次才能再跳三阶的汉诺塔
void hanoi(int n,char from,char tmp,char to){
if (n>0) {
hanoi(n - 1, from, to, tmp);
move(from,to);//输出函数
hanoi(n - 1, tmp, from, to);
}
}
void move(char from,char to){
cout << "get game from board " << from << endl;
cout << "playing" << endl;//这一行可以省略
cout << "put game to board " << to << endl;
}三、二分
二分普遍写法
int r=1e6,l=0,mid,ans;
while(l<=r){
mid=(l+r)/2;
if(check(mid)) ans=mid,r=mid-1;//check()即为检验函数
else l=mid+1;
}
//看到是求最大值最小、最小值最大这一类的，就肯定为二分
//时间复杂度为nlogn时，也应该往二分靠拢二分查找大于等于v的第一个值
//保证l<=r,返回值l合理
int bs(int a[],int l,int r,int v){
int m;
while(l<r){
m=(l+r)>>1;
if(a[m]<v) l=m+1;
else r=m;
}
return l;
}放一道例题
一个无向图，N个点编号1~N。M条边，每条边有一个权值c。对于一个点集A，这个点集的权值S定义为SA=max cij，其中i∈A∧j∈A∧i≠j。现在将N个点分割为两个点集A、B，请问max(SA,SB)max(SA,SB) 的最小值
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define max 300005
using namespace std;
typedef long long ll;
struct node {
int a,b,c;
} ver[max];
struct Edge {
int v;
int c;
int next;
} e[max];
int head[max],e_num=0;
int n,m,S,T;
ll mid;
int color[max],vis[max];
void add(int u,int v,int c) {
e[e_num].v=v;
e[e_num].c=c;
e[e_num].next=head[u];
head[u]=e_num;
e_num++;
}
void insert(int u,int v,int c) {
add(u,v,c);
add(v,u,c);
}
bool dfs(int u, int c)
{
vis[u]=1;
color[u]=c;
for(int i=head[u];~i;i=e[i].next)
{
int j=e[i].v;
if(!color[j])
{
if(!dfs(j, 3-c)) return false;
}
else if(color[j]==c) return false;
}
return true;
}
bool check() {
memset(vis,0,sizeof(vis));
memset(head,-1,sizeof(head));
memset(color,0,sizeof(color));
for(int i=1; i<=m; i++) {
if(ver[i].c>mid)
insert(ver[i].a,ver[i].b,ver[i].c);//如果大则连边
}
for(int i=1; i<=n; i++){
if(!vis[i]){
if(!dfs(i,1)) return false;
}
}
return true;
}
int main() {
int a,b,c;
ll ans;
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++) {
scanf("%d%d%d",&ver[i].a,&ver[i].b,&ver[i].c);
}
ll l=0,r=3*1e10;
while(l<=r){
mid=((l+r)>>1);
if(check()) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%lld",ans);
}四、DP问题
背包问题
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct node{
int value;
int price;
int num;
};
struct node a[505];
int b[30005]={},val;
int max(int n,int m){
if(n>=m) return n;
return m;
}
void ZeroOnePack(int *b,int price,int value){
int v;
for(v=val;v>=price;v--){
b[v]=max(b[v],b[v-price]+value);
}
}
void CompletePack(int *b,int price,int value){
int v;
for(v=price;v<=val;v++){
b[v]=max(b[v],b[v-price]+value);
}
}
void MultiplePack(int *b,int price,int value,int num){
if (price*num>=val){
CompletePack(b,price,value);
return;
}
int k=1;
while(k<num){
ZeroOnePack(b,k*price,k*value);
num=num-k;
k=2*k;
}
ZeroOnePack(b,price*num,value*num);
}
int main(){
int n,i,j,v;
while(~scanf("%d%d",&n,&val)){
for(i=1;i<=n;i++){
scanf("%d%d%d",&a[i].price,&a[i].value,&a[i].num);
}
for(i=0;i<=val;i++){
b[i]=0;
}
for(i=1;i<=n;i++){
MultiplePack(b,a[i].price,a[i].value,a[i].num);
}
printf("%d\n",b[val]);
}
}股票问题
#include<iostream>
#include<cstdio>
using namespace std;
int max(int n,int m){
if(n>=m) return n;
return m;
}
int main(){
int n,k,a[100005]={};
long long buy[1005],sell[1005];
while(~scanf("%d%d",&n,&k)){
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=k;i++){
buy[i]=-1000000001;
sell[i]=0;
}
for(int i=1;i<=n;i++){
buy[1]=max(buy[1],-a[i]);
sell[1]=max(sell[1],buy[1]+a[i]);
for(int j=2;j<=k;j++){
buy[j]=max(buy[j],sell[j-1]-a[i]);
sell[j]=max(sell[j],buy[j]+a[i]);
}
}
printf("%lld\n",sell[k]);
}
}树形dp例题
二叉树
最长链为这棵二叉树中一条最长的简单路径，即不经过重复结点的一条路径。可以容易证明，二叉树中最长链的起始、结束结点均为叶子结点。现给出一棵N(N<=100000)个结点二叉树，问这棵二叉树中最长链的长度为多少，保证了1号结点为二叉树的根。
#include<stdio.h>
#include<stdlib.h>
int max(int a,int b){
if(a>b) return a;
return b;
}
int l[100005],r[100005];
int g[100005],f[100005];
void DFS(int depth){
if(depth!=0){
DFS(l[depth]);
DFS(r[depth]);
g[depth]=max(g[l[depth]],g[r[depth]])+1;
}
else{
g[depth]=0;
}
}
int main()
{
int tmax=-1;
int n,i;
scanf("%d",&n);
for (i=1;i<=n;i++){
scanf("%d%d",&l[i],&r[i]);
}
DFS(1);
for(int i=1;i<=n;i++){
f[i]=1+g[l[i]]+g[r[i]];
if(f[i]>tmax){
tmax=f[i];
}
}
printf("%d",tmax-1);
}子序列问题
最长有序子序列LOS
从一个数字序列中找出他的最长上升（下降，非下降，非上升）序列
上升为例 输入14235，输出长度4，及序列1235
#include<stdio.h>
#define max ...
int main(){
int dp[max],a[max],n;
int ans[max],cnt=0;// 序列记录数组
// 输入n及a[]
dp[0]=1;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(a[i]>a[j]){ // 上升子序列
if(dp[i]<dp[j]+1){// 这里需要加一的原因是在dp[i]更新后要保持一致，不然会出错
dp[i]=dp[j]+1;
pre[i]=j;// 代表子序列前一个数的下标
}
}
}
}
}最长公共序列 LCS
从两个数字序列中找出他们的最长公共子序列
输入14235 12435，输出长度4，序列1235
dp[i][j]表示s1序列前i个元素和s2序列前j个元素的最长公共子序列长度
#define max ...
int main(){
int dp[max][max],s1[max],s2[max];
int n1,n2;
//输入s1，s2
dp[0][0]=0;
for(int i=1;i<=n1;i++){
for(int j=1;j<=n2;j++){
if(s1[i-1]==s2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
pre[i][j]=0;// 同时减一即可
}
else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
if(dp[i][j]==dp[i-1][j]) pre[i][j]=1;// n1-1
else pre[i][j]=2;// n2-1
}
}
}
}
// 打印子序列(逆序的)
void prin(int n1,int n2){
if(n1==0||n2==0) return;
if(!pre[n1][n2]){
printf("%d",s1[n1-1]);
prin(n1-1,n2-1);
}
else if(pre[n1][n2]==1) prin(n1-1,n2);
else prin(n1,n2-1);
}最长公共递增子序列 LCIS
从两个数字序列中找出他的最长公共递增子序列，公共的同时需要递增
输入1254367 125836，输出长度4，序列1236
dp[i][j]为s1的前i元素和s2前j元素中，以s2[j]结尾的LCIS
#define max ...
int main(){
int dp[max][max],s1[max],s2[max];
int n1,n2;
//输入s1，s2
dp[0][0]=0;
for(int i=1;i<=n1;i++){
int max_len=0;
for(int j=1;j<=n2;j++){
if(s1[i-1]>s2[j-1]&&dp[i-1][j]>max_len) max_len=dp[i-1][j];
if(s1[i-1]==s1[j-1]) dp[i][j]=max_len+1;
else dp[i][j]=dp[i-1][j];
}
}
}
//序列问题暂时没有想到较好的方法最长回文子序列 LPS
从一个数字序列中找出他的最长回文子序列（左右元素相等，有对称轴）
输入：1254332，输出：长度4，2332
dp[j][i]为s的0~i个元素和s的n~j个元素的最长LPS
//最简单的解决方案：逆转后对两个数组取LCS，多了逆转和新数列，时间空间占用较大
//...
//正常做法如下
#define max ...
int main(){
int dp[max][max],s[max];
int n;
//输入s1，s2
for(int i=0;i<n;i++){
dp[i][i]=1;
for(int j=i-1;j>=0;j--){
if(s[i]==s[j]){
dp[j][i]=dp[j+1][i-1]+2;
//pre[j+1][i+1]=0;
}
else{
if(dp[j+1][i]>dp[j][i-1]){
dp[j][i]=dp[j+1][i];
//pre[j+1][i+1]=1;
}
if(dp[j+1][i]<dp[j][i-1]){
dp[j][i]=dp[j][i-1];
//pre[j+1][i+1]=2;
}
}
}
}
}最长等差子序列
现有一数字序列，从中取出一些数字元素，就可以组成一个等差数列，我们想知道这个等差数列最多能有多少个元素，原序列每个元素最多只能取一次
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
short int dp[10001][10001];
int a[10001]= {};
int main() {
int n,ans,i,j,k;
while(~scanf("%d",&n)) {
for(i=0; i<n; i++) {
scanf("%d",&a[i]);
}
sort(a,a+n);
for(i=0; i<n; i++) {
for(j=i+1; j<n; j++) {
dp[i][j]=2;
}
}
ans=2;
for(j=n-2; j>0; j--) {
i=j-1,k=j+1;
while(i>=0&&k<n) {
if(a[i]+a[k]>2*a[j]) {
i--;
} else if(a[i]+a[k]<2*a[j]) {
k++;
} else {
dp[i][j]=dp[j][k]+1;
if(dp[i][j]>ans) ans=dp[i][j];
i--,k++;
}
}
}
printf("%d\n",ans);
}
}五、计算几何
对于两根向量a? ×b?
$$
\vec{a}\times\vec{b}=x_ay_b-x_by_a<0那么\vec{a}在\vec{b}的逆时针方向
$$
(通俗的理解，假设朝上的话，那么a在b的左边)，反之亦然。
算面积和周长（凸包）
#include<cstdio>
#include<algorithm>
#include<cmath>
#define rint register int
using namespace std;
struct node {
double x,y;
} a[100005];
int n,p,st[100005],top;
double ans,miny=2e9,minx=2e9;
int cmp(node b,node c) { //极角排序
if (fabs((b.y-miny)*(c.x-minx)-(c.y-miny)*(b.x-minx))<=1e-8) return fabs(minx-b.x)<fabs(minx-c.x);
return (b.y-miny)*(c.x-minx)<(c.y-miny)*(b.x-minx);
}
int check(int b,int c,int d) { //叉积判断
return ((a[b].x*a[c].y)+(a[c].x*a[d].y)+(a[d].x*a[b].y)-(a[b].x*a[d].y)-(a[c].x*a[b].y)-(a[d].x*a[c].y))>0;
}
double dist(double x1,double y1,double x2,double y2) { //计算两点间的欧几里得距离
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main() {
rint i;
scanf("%d",&n);
for (i=1; i<=n; ++i) {
scanf("%lf%lf",&a[i].x,&a[i].y);
if (a[i].y<miny) { //寻找最下方的点
miny=a[i].y;
minx=a[i].x;
}
}
sort(a+1,a+1+n,cmp); //极角排序
st[1]=1;
st[2]=2;
top=2; //将两个点加入栈中
for (i=3; i<=n; ++i) { //扫描
while (!check(st[top-1],st[top],i)) top--;
st[++top]=i;
}
for (i=2; i<=top; ++i) //计算答案
ans+=dist(a[st[i-1]].x,a[st[i-1]].y,a[st[i]].x,a[st[i]].y);
ans+=dist(a[st[top]].x,a[st[top]].y,a[1].x,a[st[1]].y);
double area=0;
for(i=1;i<top;i++){
area+=(a[st[i]].x*a[st[i+1]].y-a[st[i+1]].x*a[st[i]].y);
}
area+=(a[st[top]].x*a[st[1]].y-a[st[1]].x*a[st[top]].y);
area/=2;
printf("%.2lf %.2lf",ans,area);
return 0;
}
/*板子求凸包
CALL:nr=graham(point pnt[],int n,point res[])pnt[]为输入的点积
O(NlogN)
res[]即为求得的凸包得点积
*/
struct point {
double x, y;
};
bool mult(point sp, point ep, point op) {
return (sp.x - op.x) * (ep.y - op.y) >= (ep.x - op.x) * (sp.y - op.y);
}
bool operator < (const point &l, const point &r) {
return l.y < r.y || (l.y == r.y && l.x < r.x);
}
int graham(point pnt[], int n, point res[]) {
int i, len, k = 0, top = 1;
sort(pnt, pnt + n);
if (n == 0) return 0;
res[0] = pnt[0];
if (n == 1) return 1;
res[1] = pnt[1];
if (n == 2) return 2;
res[2] = pnt[2];
for (i = 2; i < n; i++) {
while (top && mult(pnt[i], res[top], res[top-1]))
top--;
res[++top] = pnt[i];
}
len = top;
res[++top] = pnt[n - 2];
for (i = n - 3; i >= 0; i--) {
while (top!=len && mult(pnt[i], res[top], res[top-1])) top--;
res[++top] = pnt[i];
}
return top; // 返回凸包中点的个数
}凸包相交
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
class Point {
public:
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {}
Point operator+(Point a) {
return Point(a.x + x, a.y + y);
}
Point operator-(Point a) {
return Point(x - a.x, y - a.y);
}
bool operator<(const Point &a) const {
if (x == a.x)
return y < a.y;
return x < a.x;
}
bool operator==(const Point &a) const {
if (fabs(x - a.x) < eps && fabs(y - a.y) < eps)
return 1;
return 0;
}
double length() {
return sqrt(x * x + y * y);
}
};
typedef Point Vector;
double cross(Vector a, Vector b) {
return a.x * b.y - a.y * b.x;
}//叉积
double dot(Vector a, Vector b) {
return a.x * b.x + a.y * b.y;
}//点积
bool isclock(Point p0, Point p1, Point p2) {
Vector a = p1 - p0;
Vector b = p2 - p0;
if (cross(a, b) < -eps)
return true;
return false;
}//判断平行也就是夹角很小很小
double getDistance(Point a, Point b) {
return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
typedef vector<Point> Polygon;
Polygon Andrew(Polygon s){
Polygon u,l;
if(s.size()<3) return s;
sort(s.begin(), s.end());//根据x坐标排序
u.push_back(s[0]);
u.push_back(s[1]);
l.push_back(s[s.size()-1]);
l.push_back(s[s.size()-2]);
for(int i=2;i<s.size();++i){
for(int n=u.size();n>=2&&!isclock(u[n-2],u[n-1],s[i]);--n){
u.pop_back();
}
u.push_back(s[i]);
}
for(int i = s.size() - 3 ; i >= 0 ; --i) {
for(int n = l.size() ; n >=2 && !isclock(l[n-2],l[n-1],s[i]); --n) {
l.pop_back();
}
l.push_back(s[i]);
}
for(int i = 1 ; i < u.size() - 1 ; i++) l.push_back(u[i]);
return l;
}
int dcmp(double x) {
if (fabs(x) <= eps)
return 0;
return x > 0 ? 1 : -1;
}
// 判断点在线段上
bool OnSegment(Point p, Point a1, Point a2) {
return dcmp(cross(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) < 0;
}
// 判断线段相交
bool Intersection(Point a1, Point a2, Point b1, Point b2) {
double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1),
c3 = cross(b2 - b1, a1 - b1), c4 = cross(b2 - b1, a2 - b1);
return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
}
// 判断点在凸包内
int isPointInPolygon(Point p, vector<Point> s) {
int wn = 0, cc = s.size();
for (int i = 0; i < cc; i++) {
Point p1 = s[i];
Point p2 = s[(i + 1) % cc];
if (p1 == p || p2 == p || OnSegment(p, p1, p2)) return -1;
int k = dcmp(cross(p2 - p1, p - p1));
int d1 = dcmp(p1.y - p.y);
int d2 = dcmp(p2.y - p.y);
if (k > 0 && d1 <= 0 && d2 > 0) wn++;
if (k < 0 && d2 <= 0 && d1 > 0) wn--;
}
if (wn != 0) return 1;
return 0;
}
void solve(Polygon s1, Polygon s2) {
int c1 = s1.size(), c2 = s2.size();
for(int i = 0; i < c1; ++i) {
if(isPointInPolygon(s1[i], s2)) {//点是否包含
printf("NO\n");
return;
}
}
for(int i = 0; i < c2; ++i) {
if(isPointInPolygon(s2[i], s1)) {//同上
printf("NO\n");
return;
}
}
for (int i = 0; i < c1; i++) {
for (int j = 0; j < c2; j++) {
if (Intersection(s1[i], s1[(i + 1) % c1], s2[j], s2[(j + 1) % c2])) {//线段相交判断
printf("NO\n");
return;
}
}
}
printf("YES\n");
}
int main() {
int n,m;
while (cin>>n>>m){
if(n==0&&m==0) break;
Polygon s1,s2;
for (int i=0;i<n;++i){
double x1, x2;
scanf("%lf%lf",&x1,&x2);
s1.push_back(Point(x1, x2));
}
for (int i=0;i<m;++i){
double x1, x2;
scanf("%lf%lf",&x1,&x2);
s2.push_back(Point(x1,x2));
}
if(s1.size()) s1=Andrew(s1);
if(s2.size()) s2=Andrew(s2);
solve(s1,s2);
}
return 0;
}线段相交
#include<stdio.h>
#include<iostream>
#include<cmath>
using namespace std;
class Point{
public:
double x,y;
Point(double x=0, double y=0):x(x),y(y) {}
Point operator + (Point p){
return Point(x+p.x,y+p.y);//重定义加法，点的加法即坐标相加，也可能是点和向量相加
}
Point operator - (Point p){
return Point(x-p.x,y-p.y);//重定义减法，点的减法即坐标相减
}
Point operator * (double a){
return Point(a*x,a*y);//重定义乘法，点乘常数即以坐标乘常数
}
};
typedef Point Vector;//因为向量Vector也能用X,Y表示
int flag;
struct Segment{ //Segment 线段
Point p1,p2;
};
double cross(Vector a, Vector b) {//向量的外积
return a.x*b.y - a.y*b.x;
}
double crossx(Point p1,Point p2,Point q1,Point q2){//也是外积不过是具体的点之间的
return (p1.x-p2.x)*(q1.y-q2.y)-(p1.y-p2.y)*(q1.x-q2.x);//p1p2 x q1q2
}
bool issame(Point P1,Point P2,Point Q1,Point Q2) {
if((P1.x==Q1.x&&P1.y==Q1.y)&&(!(P2.x==Q2.x&&P2.y==Q2.y))) { //P1=Q1
printf("%lf %lf\n",P1.x,P1.y);
return true;
} else if((!(P1.x==Q1.x&&P1.y==Q1.y))&&(P2.x==Q2.x&&P2.y==Q2.y)) { //P2=Q2
printf("%lf %lf\n",P2.x,P2.y);
return true;
} else if((P2.x==Q1.x&&P2.y==Q1.y)&&(!(P1.x==Q2.x&&P1.y==Q2.y))) { //P2=Q1
printf("%lf %lf\n",P2.x,P2.y);
return true;
} else if((!(P2.x==Q1.x&&P2.y==Q1.y))&&(P1.x==Q2.x&&P1.y==Q2.y)) { //P1=Q2
printf("%lf %lf\n",P1.x,P1.y);
return true;
} else return false;
}
bool isch(Point P1,Point P2,Point Q1,Point Q2){
if(//存在两个端点均与另一线段重合
((P2.y-Q1.y)*(Q1.x-P1.x)==(Q1.y-P1.y)*(P2.x-Q1.x)&&(((P1.x<=Q1.x)&&(P2.x>=Q1.x))||((P1.x>=Q1.x)&&(P2.x<=Q1.x)))&&(((P1.y<=Q1.y)&&(P2.y>=Q1.y))||((P1.y>=Q1.y)&&(P2.y<=Q1.y)))&&
(P2.y-Q2.y)*(Q2.x-P1.x)==(Q2.y-P1.y)*(P2.x-Q2.x)&&(((P1.x<=Q2.x)&&(P2.x>=Q2.x))||((P1.x>=Q2.x)&&(P2.x<=Q2.x)))&&(((P1.y<=Q2.y)&&(P2.y>=Q2.y))||((P1.y>=Q2.y)&&(P2.y<=Q2.y))))||
((Q2.y-P1.y)*(P1.x-Q1.x)==(P1.y-Q1.y)*(Q2.x-P1.x)&&(((Q1.x<=P1.x)&&(Q2.x>=P1.x))||((Q1.x>=P1.x)&&(Q2.x<=P1.x)))&&(((Q1.y<=P1.y)&&(Q2.y>=P1.y))||((Q1.y>=P1.y)&&(Q2.y<=P1.y)))&&
(Q2.y-P2.y)*(P2.x-Q1.x)==(P2.y-Q1.y)*(Q2.x-P2.x)&&(((Q1.x<=P2.x)&&(Q2.x>=P2.x))||((Q1.x>=P2.x)&&(Q2.x<=P2.x)))&&(((Q1.y<=P2.y)&&(Q2.y>=P2.y))||((Q1.y>=P2.y)&&(Q2.y<=P2.y))))
)
return true;
return false;
}
bool judge(Point p1,Point p2,Point q1,Point q2){//判断是否相交
if(crossx(p1,q1,p1,p2)*crossx(p1,q2,p1,p2)<0&&crossx(q1,p1,q1,q2)*crossx(q1,p2,q1,q2)<0)
return true;//正常相交
else if((crossx(p1,q1,p1,p2)*crossx(p1,q2,p1,p2)<0&&crossx(q1,p1,q1,q2)*crossx(q1,p2,q1,q2)==0)||
(crossx(p1,q1,p1,p2)*crossx(p1,q2,p1,p2)==0&&crossx(q1,p1,q1,q2)*crossx(q1,p2,q1,q2)<0))
return true;//存在一端点在另一条线段上而不是端点处的相交
else if(crossx(p1,q1,p1,p2)*crossx(p1,q2,p1,p2)==0&&crossx(q1,p1,q1,q2)*crossx(q1,p2,q1,q2)==0){//共线
if(isch(p1,p2,q1,q2)) return false;
else if(issame(p1,p2,q1,q2)){//存在一组端点重合
flag=1;//不是正常相交，需要自己算，之后就不算
return true;
}
else return false;
}
return false;
}
Point getCrossPoint(Segment s1,Segment s2){
Vector base;//向量
base=s2.p2-s2.p1;
double d1=fabs(cross(base,s1.p1-s2.p1));
double d2=fabs(cross(base,s1.p2-s2.p1));//算三角形面积，只是没有除以2
double t=d1/(d1+d2);//面积之比等于线段之比，可理解为t=AO/(AO+BO)
return s1.p1+(s1.p2-s1.p1)*t;//通过A点坐标加上向量OA然后求得O点坐标
}
int main() {
Segment s1,s2;
Point p;
while(~scanf("%lf%lf%lf%lf",&s1.p1.x,&s1.p1.y,&s1.p2.x,&s1.p2.y)) {
flag=0;
scanf("%lf%lf%lf%lf",&s2.p1.x,&s2.p1.y,&s2.p2.x,&s2.p2.y);
if(!judge(s1.p1,s1.p2,s2.p1,s2.p2)) printf("none\n");
else {
if(!flag) {
p=getCrossPoint(s1,s2);//交点坐标
printf("%lf %lf\n",p.x,p.y);
}
}
}
}
//简单板子，只判断是否相交重合也当作相交
const double eps=1e-10;
struct point {
double x, y;
};
double min(double a, double b) {
return a < b ? a : b;
}
double max(double a, double b) {
return a > b ? a : b;
}
bool inter(point a, point b, point c, point d) {
if ( min(a.x, b.x) > max(c.x, d.x) || min(a.y, b.y) > max(c.y, d.y) || min(c.x, d.x) > max(a.x, b.x) || min(c.y, d.y) > max(a.y, b.y) ) return 0;
double h, i, j, k;
h = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
i = (b.x - a.x) * (d.y - a.y) - (b.y - a.y) * (d.x - a.x);
j = (d.x - c.x) * (a.y - c.y) - (d.y - c.y) * (a.x - c.x);
k = (d.x - c.x) * (b.y - c.y) - (d.y - c.y) * (b.x - c.x);
return h * i <= eps && j * k <= eps;
}ACM计算几何板子汇总
/*==================================================*\
| Liuctic的计算几何库 | p-Lpoint ln,l - Lline ls - Llineseg lr - Lrad
| 求平面上两点之间的距离 p2pdis
| 返回(P1-P0)*(P2-P0)的叉积。 xmulti
| 确定两条线段是否相交 lsinterls
| 判断点p是否在线段l上 ponls
| 判断两个点是否相等 Euqal_Point
| 线段非端点相交 lsinterls_A
| 判断点q是否在多边形Polygon内 pinplg
| 多边形的面积 area_of_polygon
| 解二次方程 Ax^2+Bx+C=0 equa
| 点到直线距离 p2lndis
| 直线与圆的交点，已知直线与圆相交 lncrossc
| 点是否在射线的正向 samedir
| 射线与圆的第一个交点 lrcrossc
| 求点p1关于直线ln的对称点p2 mirror
| 两直线夹角（弧度） angle_LL
\*==================================================*/
#define infinity 1e20
#define EP 1e-10
const int MAXV = 300 ;
const double PI = 2.0*asin(1.0); //高精度求PI
struct Lpoint {double x,y;}; //点
struct Llineseg {Lpoint a,b;}; //线段
struct Ldir {double dx,dy;}; //方向向量
struct Lline {Lpoint p;Ldir dir;}; //直线
struct Lrad {Lpoint Sp;Ldir dir;}; //射线
struct Lround {Lpoint co;double r;};//圆
// 求平面上两点之间的距离
double p2pdis(Lpoint p1,Lpoint p2) {
return (sqrt((p1.x-p2.x) * (p1.x-p2.x) + (p1.y-p2.y) * (p1.y-p2.y)));
}
/*******************************************************
| (P1-P0)*(P2-P0)的叉积 若结果为正，则<P0,P1>在<P0,P2>的顺时针方向； 若
为0则<P0,P1><P0,P2>共线； 若为负则<P0,P1>在<P0,P2>的在逆时针方向;
可以根据这个函数确定两条线段在交点处的转向, 比如确定p0p1和p1p2在p1处是左转还是右转，
只要求 (p2-p0)*(p1-p0)，若<0则左转，>0则右转，=0则共线
********************************************************/
double xmulti(Lpoint p1,Lpoint p2,Lpoint p0){
return((p1.x-p0.x) * (p2.y-p0.y) -(p2.x-p0.x) * (p1.y-p0.y));
}
// 确定两条线段是否相交
double mx(double t1,double t2) {
if(t1>t2) return t1;
return t2;
}
double mn(double t1,double t2) {
if(t1<t2) return t1;
return t2;
}
int lsinterls(Llineseg u,Llineseg v) {
return( (mx(u.a.x,u.b.x)>=mn(v.a.x,v.b.x))&&
(mx(v.a.x,v.b.x)>=mn(u.a.x,u.b.x))&&
(mx(u.a.y,u.b.y)>=mn(v.a.y,v.b.y))&&
(mx(v.a.y,v.b.y)>=mn(u.a.y,u.b.y))&&
(xmulti(v.a,u.b,u.a)*xmulti(u.b,v.b,u.a)>=0)&&
(xmulti(u.a,v.b,v.a)*xmulti(v.b,u.b,v.a)>=0)
);
}
//判断点p是否在线段l上
int ponls(Llineseg l,Lpoint p) {
return( (xmulti(l.b,p,l.a)==0) &&
( ((p.x-l.a.x)*(p.x-l.b.x)<0 ) ||
((p.y-l.a.y)*(p.y-l.b.y)<0 )) );
}
//判断两个点是否相等
int Euqal_Point(Lpoint p1,Lpoint p2) {
return((fabs(p1.x-p2.x)<EP)&&(fabs(p1.y-p2.y)<EP));
}
//线段相交判断函数 当且仅当u,v相交并且交点不是u,v的端点时函数为true;
int lsinterls_A(Llineseg u,Llineseg v) {
return((lsinterls(u,v)) && (!Euqal_Point(u.a,v.a))&&
(!Euqal_Point(u.a,v.b)) && (!Euqal_Point(u.b,v.a))&&
(!Euqal_Point(u.b,v.b)));
}
/*===============================================
| 判断点q是否在多边形内 其中多边形是任意的凸或凹多边形，
Polygon中存放多边形的逆时针顶点序列
================================================*/
int pinplg(int vcount,Lpoint Polygon[],Lpoint q) {
int c=0,i,n;
Llineseg l1,l2;
l1.a=q;
l1.b=q;
l1.b.x=infinity;
n=vcount;
for (i=0; i<vcount; i++) {
l2.a=Polygon[i];
l2.b=Polygon[(i+1)%n];
if ( (lsinterls_A(l1,l2))||
(
(ponls(l1,Polygon[(i+1)%n]))&&
(
(!ponls(l1,Polygon[(i+2)%n]))&&
(xmulti(Polygon[i],Polygon[(i+1)%n],l1.a) *
xmulti(Polygon[(i+1)%n],Polygon[(i+2)%n],l1.a)>0)
||
(ponls(l1,Polygon[(i+2)%n]))&&
(xmulti(Polygon[i],Polygon[(i+2)%n],l1.a) *
xmulti(Polygon[(i+2)%n],Polygon[(i+3)%n],l1.a)>0)
)
)
)
c++;
}
return(c%2!=0);
}
/*==================================================*\
| 计算多边形的面积
| 要求按照逆时针方向输入多边形顶点
| 可以是凸多边形或凹多边形
\*==================================================*/
double areaofp(int vcount,double x[],double y[],Lpoint plg[]) {
int i;
double s;
if (vcount<3) return 0;
36 lncrossc(ln2,Y,p1,p2);
s=plg[0].y*(plg[vcount-1].x-plg[1].x);
for (i=1; i<vcount; i++) s+=plg[i].y*(plg[(i-1)].x-plg[(i+1)%vcount].x);
return s/2;
}
/*********************\
| 解二次方程 Ax^2+Bx+C=0 返回-1表示无解 返回1 表示有解
\*********************/
int equa(double A,double B,double C,double& x1,double& x2) {
double f=B*B-4*A*C;
if(f<0) return -1;
x1=(-B+sqrt(f))/(2*A);
x2=(-B-sqrt(f))/(2*A);
return 1;
}
//计算直线的一般式 Ax+By+C=0
void format(Lline ln,double& A,double& B,double& C) {
A=ln.dir.dy;
B=-ln.dir.dx;
C=ln.p.y*ln.dir.dx-ln.p.x*ln.dir.dy;
}
//点到直线距离
double p2ldis(Lpoint a,Lline ln) {
double A,B,C;
format(ln,A,B,C);
return(fabs(A*a.x+B*a.y+C)/sqrt(A*A+B*B));
}
//直线与圆的交点，已知直线与圆相交
int lncrossc(Lline ln,Lround Y,Lpoint& p1,Lpoint& p2) {
double A,B,C,t1,t2;
int zz=-1;
format(ln,A,B,C);
if(fabs(B)<1e-8) {
p1.x=p2.x=-1.0*C/A;
zz=equa(1.0,-2.0*Y.co.y,Y.co.y*Y.co.y
+(p1.x-Y.co.x)*(p1.x-Y.co.x)-Y.r*Y.r,t1,t2);
p1.y=t1;
p2.y=t2;
} else if(fabs(A)<1e-8) {
p1.y=p2.y=-1.0*C/B;
zz=equa(1.0,-2.0*Y.co.x,Y.co.x*Y.co.x
+(p1.y-Y.co.y)*(p1.y-Y.co.y)-Y.r*Y.r,t1,t2);
p1.x=t1;
p2.x=t2;
} else {
zz=equa(A*A+B*B,2.0*A*C+2.0*A*B*Y.co.y
-2.0*B*B*Y.co.x,B*B*Y.co.x*Y.co.x+C*C+2*B*C*Y.co.y
+B*B*Y.co.y*Y.co.y-B*B*Y.r*Y.r,t1,t2);
p1.x=t1,p1.y=-1*(A/B*t1+C/B);
p2.x=t2,p2.y=-1*(A/B*t2+C/B);
}
return 0;
}
//点是否在射线的正向
bool samedir(Lrad ln,Lpoint P) {
double ddx,ddy;
ddx=P.x-ln.Sp.x;
ddy=P.y-ln.Sp.y;
if((ddx*ln.dir.dx>0||fabs(ddx*ln.dir.dx)<1e-7)
&&(ddy*ln.dir.dy>0||(fabs(ddy*ln.dir.dy)<1e-7)))
return true;
else return false;
}
//射线与圆的第一个交点 已经确定射线所在直线与圆相交返回-1表示不存正向交点 ，否则返回1
int lrcrossc(Lrad ln, Lround Y, Lpoint& P) {
Lline ln2;
Lpoint p1,p2;
int res=-1;
double dis=1e20;
ln2.p=ln.Sp,ln2.dir=ln.dir;
if(samedir(ln,p1)) {
res=1;
if(p2pdis(p1,ln.Sp)<dis) {
dis=p2pdis(p1,ln.Sp);
P=p1;
}
}
if(samedir(ln,p2)) {
res=1;
if(p2pdis(p2,ln.Sp)<dis) {
dis=p2pdis(p2,ln.Sp);
P=p2;
}
}
return res;
}
//求点p1关于直线ln的对称点p2
Lpoint mirror(Lpoint P,Lline ln) {
Lpoint Q;
double A,B,C;
format(ln,A,B,C);
Q.x=((B*B-A*A)*P.x-2*A*B*P.y-2*A*C)/(A*A+B*B);
Q.y=((A*A-B*B)*P.y-2*A*B*P.x-2*B*C)/(A*A+B*B);
return Q;
}
//两直线夹角（弧度）
double angle_LL(Lline line1, Lline line2) {
double A1, B1, C1;
format(line1, A1, B1, C1);
double A2, B2, C2;
format(line2, A2, B2, C2);
if( A1*A2+B1*B2 == 0 ) return PI/2.0; // 垂直
else {
double t = fabs((A1*B2-A2*B1)/(A1*A2+B1*B2));
return atan(t);
}
}六、图论
最短路径
Dijkstra算法
最朴素(邻接矩阵)
#define max ....
#define INF ....
int sweight[max]={},map[max][max]，spath[max];
void Dijkstra(int v0){
int i,j,v,minweight;
char wfound[max]={0};
for (i=1;i<=n;i++){
sweight[i]=map[v0][i];
spath[i]=v0;
}
sweight[v0]=0;
wfound[v0]=1;
for (i=1;i<=n-1;i++){//i从0取还是从1取，取决于顶点编号
minweight=INFINITY;
for (j=1;j<=n;j++)
if (!wfound[j]&&(sweight[j]<minweight)){
v=j;
minweight=sweight[j];
}
wfound[v]=1;
for (j=1;j<=n;j++){
if (!wfound[j]&&(minweight+map[v][j]<sweight[j])){
sweight[j]=minweight+map[v][j];
spath[j]=v;
}
}
}
}
//别忘了map数组初始化为最大值INF优先队列优化
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define maxn 10005
#define inf 0x3f3f3f3f
using namespace std;
int dis[maxn];
int judge[maxn];
int n, m, s, t, u;
struct node{
int v, w;
node() {}
node(int v, int w) : v(v), w(w) {}
bool operator < (const node &a) const {
return w > a.w;
}
}tmp;
vector<struct node> Adj[maxn];
void Dijkstra(int s)
{
memset(dis,0x3f,sizeof(dis)); // 赋最大值
dis[s] = 0;
priority_queue<struct node> Q;
tmp.v = s; tmp.w = 0;
Q.push(tmp);
node nd;// 临时存储
while(!Q.empty()) {
nd = Q.top(); Q.pop();
if(judge[nd.v]) continue;
judge[nd.v] = 1;
for(int i = 0; i < Adj[nd.v].size(); i++)
{
int j = Adj[nd.v][i].v;
int k = Adj[nd.v][i].w;
if(nd.w + k < dis[j] && !judge[j]) {// 松弛
dis[j] = nd.w + k;
tmp.v = j, tmp.w = dis[j];
Q.push(tmp);
}
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i = 1, u, v, w; i <= m; i++)
{
scanf("%d%d%d",&u, &v, &w);
tmp.v = v;tmp.w = w;
Adj[u].push_back(tmp);
tmp.v = u;tmp.w = w;
Adj[v].push_back(tmp);
}
Dijkstra(s);
printf("%d\n",dis[t]);
return 0;
}SPFA
邻接矩阵
#include<cstdio>
#include<cstring>
#include<queue>
#define max 2600
#define inf 1000000000
int map[max][max],n,m,s,t;
int dis[max],visit[max],num[max];//num[max]用来保存入队次数，visit[max]判断是否入队；
std::queue<int> q;
void init(){
memset(visit,0,sizeof(visit));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) map[i][j]=0;
else map[i][j]=inf;
}
}
for(int i=1;i<=n;i++){
if(i==s) dis[i]=0;
else dis[i]=inf;
}
while(!q.empty()) q.pop();
}
void spfa(){
int temp,i;
q.push(s);
visit[s]=1;
while(!q.empty()){
temp=q.front();
q.pop();
visit[temp]=0;
for(i=1;i<=n;i++){
if(map[temp][i]!=inf){
if(dis[i]>dis[temp]+map[temp][i]){
dis[i]=dis[temp]+map[temp][i];
if(!visit[i]){
q.push(i);
visit[i]=1;// 这后面可以通过num[i]判断是否存在负环
}
}
}
}
}
}
int main(){
int a,b,c;
scanf("%d%d%d%d",&n,&m,&s,&t);// 如果没有输入s，记得自己给出s
init();
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
map[a][b]=map[b][a]=c;
}
spfa();
printf("%d",dis[t]);
}邻接表
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#define max 2000
#define inf 1000000000
std::queue<int> q;
int n,m,s,t;
int head[max],dis[max],visit[max],cnt=0,num[max];
//head的下标表示节点的编号，存的是以这个节点为起点的添加进来的边的最后一个编号
struct edge{
int to;
int c;
int next;//next表示这条边指向的下一条相同起点的边的编号
}e[max];
void add(int u,int v,int w){
e[cnt].c=w;
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt++;
}
void insert(int u,int v,int w){
add(u,v,w);
add(v,u,w);
}
void init(){
memset(visit,0,sizeof(visit));
memset(head,-1,sizeof(head));
//memset(num,0,sizeof(num));
}
void spfa(){
int tmp,i;
while(!q.empty()) q.pop();
//s=1;
for(i=1;i<=n;i++){
if(i==s) dis[i]=0;
else dis[i]=inf;
}
visit[s]=1;
q.push(s);
while(!q.empty()){
tmp=q.front();
q.pop();
visit[tmp]=0;
for(i=head[tmp];~i;i=e[i].next){
int to=e[i].to;////i为边的编号，i连接tmp和to两个顶点
if(dis[to]>dis[tmp]+e[i].c){
dis[to]=dis[tmp]+e[i].c;
if(!visit[to]){
visit[to]=1;
q.push(to);
}
}
}
}
}
int main(){
int u,v,w;
scanf("%d%d%d%d",&n,&m,&s,&t);
init();
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
insert(u,v,w);
}
spfa();
printf("%d",dis[t]);
}Floyd
邻接矩阵
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];//e[i][j]代表i到j的最短路径最大流
Edmonds-Karp算法
邻接矩阵
#include<...>
#define max ...
int n,m,map[max][max];// n为点数，m为边数，map里存容量
int path[max],flow[max];// flow[]存流过当前顶点的流量，path[]存当前顶点的前序顶点
int start=0,end=n;
std:queue<int> q;
int EK_bfs() {
int i,t;
while(!q.empty()) q.pop();
memset(path,-1,sizeof(path));
path[start]=0;
flow[start]=INF;
q.push(start);
while(!q.empty()) {
t=q.front();
q.pop();
if(t==end) break;
for(i=1; i<=n; i++) {
if(i!=start && path[i]==-1 && map[t][i]) {
flow[i]=flow[t]<map[t][i]?flow[t]:map[t][i];// 更新流量，但不能超过容量，取更小
q.push(i);
path[i]=t;
}
}
}
if(path[end]==-1) return -1;
return flow[n];
}
int EK() {
int max_flow=0,step,now,pre;
while((step=EK_bfs())!=-1) {
max_flow+=step;
now=end;
while(now!=start) {
pre=path[now];
map[pre][now]-=step;// 更新残余网络，因为流更新后，残余网络也更新了
map[now][pre]+=step;
now=pre;
}
}
return max_flow;
}
int main(){
memset(map,0,sizeof(map));
//输入map[][]
printf("%d",EK());
}Dinic算法
邻接表
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#define INF 2147483647
#define max 1000
int min(int a,int b){
if(a<b) return a;
return b;
}
struct Edge{
int v;
int c;
int next;
}e[max];
int head[max],e_num=-1;
int n,m,S,T;
void add(int u,int v,int c){
e_num++;
e[e_num].v=v;
e[e_num].c=c;
e[e_num].next=head[u];
head[u]=e_num;
}
void insert(int u,int v,int c){
add(u,v,c);
add(v,u,0);
}
int depth[max];// 层次网络
bool bfs()
{
std::queue<int> q;//定义一个bfs寻找分层图时的队列
while (!q.empty()) q.pop();
memset(depth,-1,sizeof(depth));
depth[S]=0;//源点深度为0
q.push(S);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=e[i].next){
int v=e[i].v;
if(e[i].c>0&&depth[v]==-1){
q.push(v);
depth[v]=depth[u]+1;
}
}
}
return (depth[T]!=-1);
}
int dfs(int u,int flow){ //flow表示当前搜索分支的流量上限
if(u==T){
return flow;
}
int res=0;
for(int i=head[u];i!=-1;i=e[i].next){
int v=e[i].v;
if(e[i].c>0&&depth[u]+1==depth[v]){
int tmp=dfs(v,min(flow,e[i].c)); // 递归计算顶点 v，用 c(u, v) 来更新当前流量上限
flow-=tmp;
e[i].c-=tmp;
res+=tmp;
e[i^1].c+=tmp; // 修改反向弧的容量
if(flow==0){ // 流量达到上限，不必继续搜索了
break;
}
}
}
if(res==0){ // 当前没有经过顶点 u 的可行流，不再搜索顶点 u
depth[u]=-1;
}
return res;
}
int dinic(){ // 函数返回值就是最大流的结果
int res=0;
while(bfs()){
res+=dfs(S,INF); // 初始流量上限为 INF
}
return res;
}
int main(){
scanf("%d%d",&m,&n);//m为边
memset(head,-1,sizeof(head));
for(int i=0;i<m;i++){
int u,v,flow;
scanf("%d%d%d",&u,&v,&flow);
insert(u,v,flow);
}
//给出S和T
printf("%d",dinic());
return 0;
}Sap算法
邻接矩阵
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 1002
#define INF 0x3f3f3f3f
int e[N][N];
int pre[N]; //记录当前点的前驱。
int d[N]; //记录距离标号 i-t距离的下界。
int num[N]; //gap优化，每个距离下标下的节点编号有多少个，为0的话，说明s-t不连通
int SAP(int s,int t){
memset(pre,-1,sizeof(pre));
memset(d,0,sizeof(d));
memset(num,0,sizeof(num));
num[0]=t;
int v,u=pre[s]=s,flow=0,aug=INF;
while(d[s]<t){ //else 残量网络中不存在s-t路。
//寻找可行弧
for(v=1;v<=t;v++){
if(e[u][v]>0&&d[u]==d[v]+1){
break;
}
}
if(v<=t){
pre[v]=u;
u=v;
if(v==t){
aug=INF;
//寻找当前找到路径上的最大流
for(int i=v;i!=s;i=pre[i]){
if(aug>e[pre[i]][i]) aug=e[pre[i]][i];
}
flow+=aug;
//更新残留网络。
for(int i=v;i!=s;i=pre[i]){
e[pre[i]][i]-=aug;
e[i][pre[i]]+=aug;
}
u=s; //从源点开始继续搜。
}
}else{
//找不到可行弧
int minlevel=t;
//寻找与当前点连接的最小的距离标号。
for(v=1;v<=t;v++){
if(e[u][v]>0&&minlevel>d[v]){
minlevel=d[v];
}
}
num[d[u]]--; //当前标号的数目减一
if(!num[d[u]]) break; //出现断层。
d[u]=minlevel+1;
num[d[u]]++;
u=pre[u];
}
}
return flow;
}
int main()
{
int n,m,u,v,w; //m,边数，n,节点数.
while(~scanf("%d%d",&n,&m);){
memset(e,0,sizeof(e));
while(m--){
scanf("%d%d%d",&u,&v,&w);
e[u][v]+=w;
e[v][u]+=w;
}
printf("%d\n",SAP(1,n));
}
return 0;
}邻接表
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX_N=5000; //顶点数上限
const int MAX_M=500000; //总的边数上限
struct edge{
int v,c,next; //v指另一个顶点，c表示容量。
}e[MAX_M];
int p[MAX_N],eid;
void init(){
memset(p,-1,sizeof(p));
eid=0;
}
void insert(int u,int v,int c){ //插入一条从u向v，容量为c的弧。
e[eid].v=v;
e[eid].next=p[u];
e[eid].c=c;
p[u]=eid++;
}
void addedge(int u,int v,int c){ //用insert插入网络中的弧
insert(u,v,c);
insert(v,u,0); //插入一条反方向，当前容量为0的弧
}
int num[MAX_N];
int d[MAX_N];
int cur[MAX_N];
int pre[MAX_N];
int SPA(int s,int t,int n){ //S是源点，T是汇点。
int cur_flow,flow_ans=0,u,tmp,neck,i;
memset(num,0,sizeof(num));
memset(d,0,sizeof(d));
memset(pre,-1,sizeof(pre));
for(i=1;i<=n;i++){
cur[i]=p[i];
}
num[0]=n;
u=s;
while(d[s]<n){
if(u==t){
cur_flow=INF;
for(i=s;i!=t;i=e[cur[i]].v){
if(cur_flow>e[cur[i]].c){ //增广成功，寻找瓶颈边
neck=i;
cur_flow=e[cur[i]].c;
}
}
for(i=s;i!=t;i=e[cur[i]].v){
tmp=cur[i];
e[tmp].c-=cur_flow;
e[tmp^1].c+=cur_flow;
}
flow_ans+=cur_flow;
u=neck; //下次增广从瓶颈边开始
}
//寻找可行弧
for(i=cur[u];i!=-1;i=e[i].next){
if(e[i].c&&d[u]==d[e[i].v]+1) break;
}
if(i!=-1){
cur[u]=i;
pre[e[i].v]=u;
u=e[i].v;
}else{
if(0==--num[d[u]]) break;
cur[u]=p[u];
for(tmp=n,i=p[u];i!=-1;i=e[i].next){
if(e[i].c){
tmp=min(tmp,d[e[i].v]);
}
}
d[u]=tmp+1;
num[d[u]]++;
if(u!=s) u=pre[u];
}
}
return flow_ans;
}
int main() {
int n,m;
while(~scanf("%d%d",&n,&m)){
init();
for(int i=0;i<m;i++){
int u,v,flow;
scanf("%d%d%d",&u,&v,&flow);
addedge(u,v,flow);
}
printf("%d",SPA(1,n,n));
//cout<<SPA(1,n,n)<<endl;
}
return 0;
}
转载于： https://blog.csdn.net/qq_40679299/article/details/81108783
hlpp算法
邻接表
#include<bits/stdc++.h>
#define re register
#define il inline
#define inc(i,j,k) for(re int i=j;i<=k;++i)
#define ra(i,u) for(re int i=head[u];i!=-1;i=a[i].nxt)
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxm=120010;
const int maxn=2010;
struct node
{
int to,nxt,flow;
}a[maxm<<1];
int head[maxn],gap[maxn],h[maxn],e[maxn];
bool vis[maxn];
int cnt=-1,n,m,st,ed;
struct cmp {il bool operator () (int x,int y)const{return h[x]<h[y];}};
priority_queue<int,vector<int>,cmp> pq;
queue<int> q;
il void add(int u,int v,int w)
{
a[++cnt].to=v;
a[cnt].nxt=head[u];
a[cnt].flow=w;
head[u]=cnt;
}
il bool bfs()
{
memset(h,inf,sizeof(h));
h[ed]=0;
q.push(ed);
while(!q.empty())
{
int t=q.front();
q.pop();
ra(i,t)
{
int v=a[i].to;
if(a[i^1].flow && h[v]>h[t]+1)
{
h[v]=h[t]+1;
q.push(v);
}
}
}
return h[st]!=inf;
}
il void push(int u)
{
ra(i,u)
{
int v=a[i].to;
if((a[i].flow) && (h[v]+1==h[u]))
{
int df=min(e[u],a[i].flow);
a[i].flow-=df;
a[i^1].flow+=df;
e[u]-=df;
e[v]+=df;
if((v!=st)&&(v!=ed)&&(!vis[v]))
{
pq.push(v);
vis[v]=1;
}
if(!e[u])break;
}
}
}
il void relabel(int u)
{
h[u]=inf;
ra(i,u)
{
int v=a[i].to;
if((a[i].flow)&&(h[v]+1<h[u]))h[u]=h[v]+1;
}
}
inline int hlpp()
{
if(!bfs())return 0;
h[st]=n;
memset(gap,0,sizeof(gap));
inc(i,1,n) if(h[i]!=inf)gap[h[i]]++;
ra(i,st)
{
int v=a[i].to;
if(int f=a[i].flow)
{
a[i].flow-=f;a[i^1].flow+=f;
e[st]-=f;e[v]+=f;
if(v!=st&&v!=ed&&!vis[v])
{
pq.push(v);
vis[v]=1;
}
}
}
while(!pq.empty())
{
int t=pq.top();pq.pop();
vis[t]=0;push(t);
if(e[t])
{
gap[h[t]]--;
if(!gap[h[t]])
{
inc(v,1,n)
{
if(v!=st&&v!=ed&&h[v]>h[t]&&h[v]<n+1)
{
h[v]=n+1;
}
}
}
relabel(t);gap[h[t]]++;
pq.push(t);vis[t]=1;
}
}
return e[ed];
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
st=1,ed=n;
inc(i,1,m)
{
int x,y;
ll f;
scanf("%d%d%lld",&x,&y,&f);
add(x,y,f);
add(y,x,0);
}
ll maxf=hlpp();
printf("%lld",maxf);
return 0;
}转载于： https://www.cnblogs.com/ZzTzZ/p/11638644.html
ISAP算法
邻接表
#include <iostream>
#include <cstdio>
#include <climits>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef struct {ll v,next,val;} edge;
const int MAXN=20010;
const int MAXM=500010;
edge e[MAXM];
ll p[MAXN],eid;
inline void init(){memset(p,-1,sizeof(p));eid=0;}
//有向
inline void insert1(ll from,ll to,ll val)
{
e[eid].v=to;e[eid].val=val;
e[eid].next=p[from];
p[from]=eid++;
swap(from,to);
e[eid].v=to;e[eid].val=0;
e[eid].next=p[from];
p[from]=eid++;
}
//无向
inline void insert2(ll from,ll to,ll val)
{
e[eid].v=to;e[eid].val=val;
e[eid].next=p[from];
p[from]=eid++;
swap(from,to);
e[eid].v=to;e[eid].val=val;
e[eid].next=p[from];
p[from]=eid++;
}
ll n,m;//n为点数 m为边数
ll h[MAXN];
ll gap[MAXN];
ll source,sink;
inline ll dfs(ll pos,ll cost)
{
if (pos==sink) return cost;
ll j,minh=n-1;
ll lv=cost,d;
for (j=p[pos];j!=-1;j=e[j].next)
{
ll v=e[j].v,val=e[j].val;
if(val>0)
{
if (h[v]+1==h[pos])
{
if (lv<e[j].val) d=lv;
else d=e[j].val;
d=dfs(v,d);
e[j].val-=d;
e[j^1].val+=d;
lv-=d;
if (h[source]>=n) return cost-lv;
if (lv==0) break;
}
if (h[v]<minh) minh=h[v];
}
}
if (lv==cost)
{
--gap[h[pos]];
if (gap[h[pos]]==0) h[source]=n;
h[pos]=minh+1;
++gap[h[pos]];
}
return cost-lv;
}
ll isap(ll st,ll ed)
{
source=st;sink=ed;
ll ret=0;
memset(gap,0,sizeof(gap));
memset(h,0,sizeof(h));
gap[st]=n;
while (h[st]<n)
{
ret+=dfs(st,INT_MAX);
}
return ret;
}
int main()
{ ll sp,tp;
//freopen("in.txt","r",stdin);
cin >> n >>m;//>> sp>> tp;
init();
for(ll i=0;i<m;i++)
{
ll u,v,c;
scanf("%lld%lld%lld",&u,&v,&c);
insert2(u,v,c);
}
printf("%lld\n",isap(1,n)); //这里是从1走到n
return 0;
}二分图
匈牙利算法
邻接矩阵
#include<iostream>
#include<cstdio>
#include<cstring>
int ans=0,n;
int link[10005],use[10005],map[10005][10005];//map数组为邻接矩阵，use表示当前点是否匹配，link[i]表示与顶点i所连的点
bool dfs(int x) {
for(int i=1;i<=n;i++){
if(!use[i]&&map[x][i]) { //若不在交替路中
use[i] = 1;//则加入交替路
if(!link[i] || dfs(link[i])) {
link[i] = x;
return true;
}
}
}
return false;
}
void xyl( ) {
memset(link, 0, sizeof(link));
for(int i=1;i<=n;i++) {
memset(use,0,sizeof(use));
if(dfs(i)) ans++;
}
}
int main() {
int i;
int a[10005],b[10005];
while(~scanf("%d",&n)) {
ans=0;
memset(map, false, sizeof(map));
/*for(i=1; i<=n; i++) {
scanf("%d",&a[i]);
map[i][a[i]]=true;
}
for(i=1; i<=n; i++) {
scanf("%d",&b[i]);
map[b[i]][i]=true;
}*/ //输入map
xyl();
printf("%d\n",ans);// ans为最大匹配数
}
}邻接表
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=50010;//边数的最大值
struct Edge
{
int to,next;
}edge[maxn];
//to 是该边指向的点 next是这个点上次用的边的编号，用来找到这个点上次和其他点维持的边关系 edge的下标代表边的编号
int head[maxn],tot;
void init()
{
tot=0;
memset(head,-1,sizeof(head));
}//初始化函数
void addedge(int u,int v)
{
edge[tot].to=v;//对边进行编号
edge[tot].next=head[u];//将U这个点上一次连接的点记录如果没有即为-1
head[u]=tot++;//等于边的编号，之后edge[head[u]]即可调用这个边
}//加边函数
int linker[maxn];
bool used[maxn];
int n;
bool dfs(int u)
{
for(int i=head[u];i!=-1;i = edge[i].next)//顺着边过去，一直遍历和这个点连接过的点和边
{
int v=edge[i].to;
if(!used[v])
{
used[v]=true;
if(linker[v]==-1 || dfs(linker[v]))
{
linker[v]=u;
return true;
}
}
}
return false;
}
int hungary()
{
int res=0;
memset(linker,-1,sizeof(linker));
for(int u=1;u<=n;u++)
{
memset(used,false,sizeof(used));
if(dfs(u)) res++;
}
return res;
}
int main ()
{
//int a[maxn],b[maxn];
while(~scanf("%d",&n)){
init();
/*for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]!=0)
addedge(i,a[i]);
//addedge(a[i],i);
}
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
if(b[i]!=0)
addedge(b[i],i);
//addedge(i,b[i]);
}*/
printf("%d\n",hungary());
}
}HK算法
邻接矩阵
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define inf 2147483647
int ans=0,n,dis;
int dx[10005],dy[10005],cx[10005],cy[10005];
bool used[10005];
int map[10005][10005];//map数组为邻接矩阵，use表示当前点是否匹配，link[i]表示与顶点i所连的点
bool searchP()
{
std::queue<int> q;
dis=inf;
memset(dx,-1,sizeof(dx));
memset(dy,-1,sizeof(dy));
for(int i=1;i<=n;i++){
if(cx[i]==-1) {q.push(i);dx[i]=0;}//对于未遍历的点入队
}
//准备分层
while(!q.empty())
{
int u=q.front();
q.pop();
if(dx[u]>dis) break;//如果目前的层次大于最小增广长度，那么退出
for(int j=1;j<=n;j++)//对于一切可能的点遍历
{
if(map[u][j]==true&&dy[j]==-1){//只对未分层的点遍历
dy[j]=dx[u]+1;
if(cy[j]==-1) dis=dy[j];
else{
dx[cy[j]]=dy[j]+1;
q.push(cy[j]);
}
}
}
}
return dis!=inf;
}
bool findpath(int x)
{
for(int j=1;j<=n;j++)
{
if(!used[j]&&map[x][j]&&dy[j]==dx[x]+1)//符合继续搜索的条件有三个：未访问过，图上联通和层次符合
{
used[j]=1;
if(cy[j]!=-1&&dis==dy[j]) continue;//如果下一个点还是匹配点且目前已经到达增广最小层次，不需要扩展了
if(cy[j]==-1||findpath(cy[j]))
{
cy[j]=x;cx[x]=j;
return true;
}
}
}
return false;
}
int hk()
{
int ans=0;
memset(cx,-1,sizeof(cx));
memset(cy,-1,sizeof(cy));
while(searchP())
{
memset(used,0,sizeof(used));
for(int i=1;i<=n;i++){
if(cx[i]==-1)
{
if(findpath(i)) ans++;
}
}
}
return ans;
}
int main( ) {
int i;
int a[10005],b[10005];
while(~scanf("%d",&n)) {
memset(map, false, sizeof(map));
/*for(i=1; i<=n; i++) {
scanf("%d",&a[i]);
map[i][a[i]]=true;
}
for(i=1; i<=n; i++) {
scanf("%d",&b[i]);
map[b[i]][i]=true;
}*/ //输入map
printf("%d\n",hk());
}
}二分图判定（染色法）
#include <cstdio>
#include <vector>
const int MAX_V = 1000 + 7; // 定点最大个数
using namespace std;
vector<int> g[MAX_V]; // 邻接表
int color[MAX_V]; // 顶点i的颜色
bool dfs(int v, int c)
{
color[v] = c; // 把顶点染成颜色c
for(int i=0; i<g[v].size(); i++) // 查询与这个顶点相邻的顶点
{
if(color[g[v][i]] == c) // 如果相邻的顶点也为c，则染色不成功
return false;
if(color[g[v][i]] == 0 && !dfs(g[v][i], -c)) // 相邻的顶点没有染色，就染成-c，并判断能否染色成功
return false;
}
return true;
}
int main()
{
int V; // 顶点个数
int a, b; // a->b有一条边
scanf("%d", &V);
for(int i=0; i<MAX_V; i++)
g[i].clear(); // 清空邻接表
while(scanf("%d%d", &a, &b) != EOF)
{
g[a].push_back(b); // 无向图
g[b].push_back(a);
}
for(int i=0; i<V; i++)
{
if(color[i] == 0)
{
if(!dfs(i, 1)) // 如果顶点还没有染色，就染色成1
{
printf("No\n");
return 0;
}
}
}
printf("Yes\n");
return 0;
}最小生成树
Kruskal
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct Node {
int a,b,val;
friend bool operator < (const Node& x,const Node& y) {
return x.val< y.val; //对于sort重载的话，从小到大用小于号
}
} load[1000];
int sum=0;
int n,m;
int fa[1000];
int cnt=0;
int Find(int a) {
return fa[a]==a ? a : fa[a]=Find(fa[a]);
}
void init(int a,int b) {
fa[Find(b)]=Find(a);
}
void kruskal() {
for(int i=0; i<m; i++) {
int x,y,z;
x=load[i].a;
y=load[i].b;
z=load[i].val;
if(Find(x)!=Find(y)) {
init(x,y);
cnt++;
sum+=z;
}
if(cnt==n-1) {
break;
}
}
}
int main() {
cin>>n>>m;
for(int i=0; i<m; i++) {
cin>>load[i].a>>load[i].b>>load[i].val;
}
for(int i=1; i<=n; i++) {
fa[i]=i;
}
sort(load,load+m);
kruskal();
cout<<sum<<endl;
return 0;
}Prim
#include<iostream>
#include<stdio.h>
#include<queue>
#include<vector>
#include<stack>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
struct Node {
int d,len;
friend bool operator < (const Node& a,const Node& b) {
return a.len > b.len; //对于优先队列，从小到大排序用大于号
}
};
int n,m;
int cnt,sum;
int vis[1000];
vector <Node> v[1000];
priority_queue< Node > q;
void prim() {
vis[1]=1;
for(int i=0; i<v[1].size(); i++) {
q.push(v[1][i]);
}
while(!q.empty()) {
Node now = q.top();
q.pop();
if(vis[now.d]) {
continue;
}
vis[now.d]=1;
cnt++;
sum+=now.len;
for(int i=0; i<v[now.d].size(); i++) {
if(vis[v[now.d][i].d]) continue;
q.push(v[now.d][i]);
}
if(cnt==n-1) break;
}
}
int main() {
while(cin>>m>>n) {
if(m==0) break;
cnt=sum=0;
while(!q.empty()) {
q.pop();
}
for(int i=0; i<=n; i++) {
v[i].clear();
}
memset(vis,0,sizeof(vis));
for(int i=0; i<m; i++) {
int x,y,z;
cin>>x>>y>>z;
Node tmp;
tmp.d=y;
tmp.len=z;
v[x].push_back(tmp);
tmp.d=x;
v[y].push_back(tmp);
}
prim();
if(cnt==n-1) {
cout<<sum<<endl;
} else {
cout<<'?'<<endl;
}
}
return 0;
}七、字符串匹配
有限自动机
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<vector>
using namespace std;
bool Matching_Prefix_Suffix(char* P,int k,int q,char c)
{ //P为模式串 K为要验证的前缀和后缀的字符串长度
if(k==0) //q为当前自动机主线长度
return true; //k=0 空字符串 前缀和后缀肯定相等
if(k==1){ //只有一个字符串 证明自动机刚好开始创建
return P[0]==c; //如果模式串的第一个和其中的c相等 前缀等于后缀
}
return P[k-1]==c&& (!strncmp(P,P+q-k+1,k-1)); //检验P[0...k-1]==P[q-k+1]
}
vector<map<char,int> > Compute_Transition_Function( char *P,const char* input_character)
{ //计算转移函数的值
int m=strlen(P); //模式串的长度
int j=0,k;
printf("The main length of Finite_Automaton_Matcher is %d\n",m);
vector<map<char,int> >transition_map(m+1); //创建一个vector 一共有m+1个数据
for(int i=0;i<m;i++){ //对于模式串的长度
j=0;
while(input_character[j]!='\0'){ //对于输入串的每一种可能字符
k= min(m+1,i+2); //因为对于长度为i的字符串 它的转移函数最大值为i
do{ //数组下标从0开始 再加上后面k一来就减1 所以为i+2
k=k-1; //找到一个最大值k使得模式串的P[0...k]==P[...n-1]
}while(!Matching_Prefix_Suffix(P,k,i,input_character[j]));
transition_map[i][input_character[j]]=k;//δ(q,a)=k a为输入字母表中的字母，q为状态
j++;
}
}
return transition_map; //返回一个vector 每一个元素为 map<char,int>
} //char 为自动机中的字符 int 为转移函数值
void Finite_Automaton_Matcher(char* T,char* P,vector<map<char,int> >transition_map)
{
int n=strlen(T); //文本串长度
int m=strlen(P); //模式串长度
int q=0; //转移函数的值
for(int i=0;i<n;i++){ //对于文本串中的每一个字符
q = transition_map[q][T[i]]; //迭代 前一个字符的转移函数值
if(q==m) //转移函数的值等于模式串的长度
printf("Pattern occurs with shift %d\n",i+1-m); //模式串的有效位移为i-m+1
}
}
int main()
{
const char* input_character="abc"; //输入字母表
char T[]="abababacaba"; //文本串
char P[]="ababaca"; //模式串
vector<map<char,int> >transition_map=Compute_Transition_Function(P,input_character);
Finite_Automaton_Matcher(T,P,transition_map);
return 0;
}优化后的自动机
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<vector>
#define MAX 200
using namespace std;
int next[MAX];
void getnext(int next[],char* t) {
int k=0;
next[1]=0;
int lent=strlen(t);
for(int q=2;q<=lent;q++){
while(k>0&&t[k+1]!=t[q]){
k=next[k];
}
if(t[k+1]==t[q]) k=k+1;
next[q]=k;
}
}
bool Matching_Prefix_Suffix(char* P,int k,int q,char c) {
//P为模式串 K为要验证的前缀和后缀的字符串长度
if(k==0) //q为当前自动机主线长度
return true; //k=0 空字符串 前缀和后缀肯定相等
if(k==1) { //只有一个字符串 证明自动机刚好开始创建
return P[0]==c; //如果模式串的第一个和其中的c相等 前缀等于后缀
}
return P[k-1]==c&& (!strncmp(P,P+q-k+1,k-1)); //检验P[0...k-1]==P[q-k+1]
}
vector<map<char,int> > Compute_Transition_Function( char *P,const char* input_character) {
//计算转移函数的值
int m=strlen(P); //模式串的长度
int j=0,k;
getnext(next,P);
printf("The main length of Finite_Automaton_Matcher is %d\n",m);
vector<map<char,int> >transition_map(m+1);//创建一个vector 一共有m+1个数据
for(int i=0; i<=m; i++) { //对于模式串的长度
j=0;
while(input_character[j]!='\0') { //对于输入串的每一种可能字符
if(P[i+1]==input_character[j]) transition_map[i][input_character[j]]=i+1;
else if(P[i+1]!=input_character[j]||i==m)
transition_map[i][input_character[j]]=transition_map[next[i]][input_character[j]];
j++;
}
}
return transition_map; //返回一个vector 每一个元素为 map<char,int>
} //char 为自动机中的字符 int 为转移函数值
void Finite_Automaton_Matcher(char* T,char* P,vector<map<char,int> >transition_map) {
int n=strlen(T); //文本串长度
int m=strlen(P); //模式串长度
int q=0; //转移函数的值
for(int i=0; i<n; i++) { //对于文本串中的每一个字符
q = transition_map[q][T[i]]; //迭代 前一个字符的转移函数值
if(q==m-1) //转移函数的值等于模式串的长度
printf("Pattern occurs with shift %d\n",i+1-m);//模式串的有效位移为i-m+1
}
}
int main() {
const char* input_character="abc"; //输入字母表
char T[MAX],P[MAX];
scanf("%s%s",T,P);
//char T[]="abababacaba"; //文本串
//char P[]="ababaca"; //模式串
vector<map<char,int> >transition_map=Compute_Transition_Function(P,input_character);
Finite_Automaton_Matcher(T,P,transition_map);
return 0;
}KMP算法
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 200
using namespace std;
int next[MAX];
void getnext(int next[],char* t) {
int j=0,k=-1;
next[0]=-1;
int lent=strlen(t);
while(j<lent) {
if(k == -1 || t[j] == t[k]) {
j++;
k++;
next[j]=k;
}
else k = next[k];
}
}
int KMP(char* s,char* t) {
int i=0,j=0;
getnext(next,t);
int lens,lent;
lens=strlen(s),lent=strlen(t);
while(i<lens&&j<lent) {
if(j==-1 || s[i]==t[j]) {
i++;
j++;
}
else j=next[j]; //j回退。。。
}
if(j>=lent)
return i-j; //匹配成功，返回子串的位置
else
return 0; //没找到
}
int main(){
char s[MAX],t[MAX];
scanf("%s%s",s,t);
printf("%d",KMP(s,t));
}
//计算子串出现次数，直接使用即可
int KMPcount(char *s,char *t){///计算模式串在子串出现的次数
getnext(next,t);
int i=0,j=0;
int lens=strlen(s),lent=strlen(t);
int ans=0;
while(i<lens){
while(j!=-1&&t[j]!=s[i])
j=next[j];
i++,j++;
if(j==lent)
ans++;
}
return ans;///返回模式串在主串中出现的次数(可重叠出现)
}扩展KMP
定义母串S，和字串T，设S的长度为n，T的长度为m，求T与S的每一个后缀的最长公共前缀，也就是说，设extend数组,extend[i]表示T与S[i,n-1]的最长公共前缀，要求出所有extend[i](0<=i<n)。
#include <iostream>
#include <string>
#include<string.h>
#define MAX 200
using namespace std;
/* 求解 T 中 next[]，注释参考 GetExtend() */
void GetNext(char* T, int &m, int next[]){
int a=0,p=0;
next[0]=m;
for (int i=1;i<m;i++){
if (i>=p||i+next[i-a]>=p){
if(i>=p)
p=i;
while(p<m&&T[p]==T[p-i])
p++;
next[i]=p-i;
a=i;
}
else
next[i]=next[i-a];
}
}
/* 求解 extend[] */
void GetExtend(char *S,int& n,char* T,int& m,int extend[],int next[]){
int a=0,p=0;
GetNext(T,m,next);
for (int i=0;i<n;i++){
if (i>=p||i+next[i-a]>=p){ // i >= p 的作用：举个典型例子，S 和 T 无一字符相同
if(i>=p)
p=i;
while(p<n&&p-i<m&&S[p]==T[p-i])
p++;
extend[i]=p-i;
a=i;
}
else
extend[i]=next[i-a];
}
}
int main(){
int next[100];
int extend[100];
//string S, T;
char S[MAX],T[MAX];
int n,m;
while (~scanf("%s%s",S,T)){
n=strlen(S);
m=strlen(T);
GetExtend(S,n,T,m,extend,next);
//打印 next
printf("next: ");
for (int i=0;i<m;i++)
printf("%d ",next[i]);
//打印 extend
for (int i=0;i<n;i++)
printf("%d ",extend[i]);
puts("");
}
return 0;
}KMP例题
/*字符串是循环节循环构成的（循环节可以是其本身）
输出该循环节出现的次数*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define Memset(x, a) memset(x, a, sizeof(x))
using namespace std;
const int N=1e6+10;
int next[N];
char s[N];
void getNext(const char P[],int next[]) {
int m=strlen(P);
int i=0,j;
j=next[0]=-1;
while(i<m) {
while(-1!=j && P[i]!=P[j])j=next[j];
next[++i]=++j;
}
}
int main() {
while(~scanf("%s",s)) {
if(s[0]=='.') break;
Memset(next,0);
getNext(s,next);
int len=strlen(s);
if(len%(len-next[len])==0) printf("%d\n",len/(len-next[len]));
else printf("1\n");
}
return 0;
}
/*与上文类似只是有些微区别
给你一个字符串，求这个字符串到第i个字符为止的循环节的次数。
前提是存在循环，如果不存在，则不输出，例如：
in:abab out: 4 2
in:a out:无
in:abcabcd out: 6 2
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define Memset(x, a) memset(x, a, sizeof(x))
using namespace std;
const int N=1e6+10;
char s[N];
int next[N];
int n;
void getNext(const char P[],int next[]) {
int m=strlen(P);
int i=0,j;
j=next[0]=-1;
while(i<m) {
while(-1!=j && P[i]!=P[j])j=next[j];
next[++i]=++j;
}
}
int main() {
int kase=0;
while(~scanf("%d",&n)&&n) {
scanf("%s",s);
Memset(next,0);
getNext(s,next);
printf("Test case #%d\n",++kase);
for(int i=2; i<=n; i++) {
if(next[i]>0&&i%(i-next[i])==0)printf("%d %d\n",i,i/(i-next[i]));
}
printf("\n");
}
return 0;
}
/*给定S，求出S的所有可能的相同前后缀的长度
next[len-1]为最长的相同前后缀并设为S1，然后S1的最长的
相同前后缀设为S2，表示为next[S1.size()-1]，肯定也是S的
相同前后缀，这样循环即可求出所有，别忘记其本身*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define Memset(x, a) memset(x, a, sizeof(x))
using namespace std;
const int N=4e5+10;
int next[N],ans[N];
char s[N];
void getNext(const char P[],int next[]) {
int m=strlen(P);
int i=0,j;
j=next[0]=-1;
while(i<m) {
while(-1!=j && P[i]!=P[j])j=next[j];
next[++i]=++j;
}
}
int main() {
while(~scanf("%s",s)) {
Memset(next,0);
getNext(s,next);
int cnt=0;
int len=strlen(s);
int j=next[len];
while(j>0) {
ans[++cnt]=j;
j=next[j];
}
for(int i=cnt; i>0; i--)printf("%d ",ans[i]);
printf("%d\n",len);
}
return 0;
}
/*1题目要求的是给定一个字符串，问我们还需要添加几个字符可以构成一个由n个循环节组成的字符串。
2可知我们应该先求出字符串的最小循环节的长度：假设字符串的长度为len，那么最小的循环节就是cir = len-next[len];如果有len%cir == 0,那么这个字符串就是已经是完美的字符串，不用添加任何字符；如果不是完美的那么需要添加的字符数就是cir - (len-(len/cir)*cir))，相当与需要在最后一个循环节上面添加几个。
3如果cir = 1，说明字符串只有一种字符例如“aaa” ; 如果cir = m说明最小的循环节长度为m，那么至少还需m个；如果m%cir == 0，说明已经不用添加了*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 100010
char s[N];
int nextval[N];
int len;
void getnext(const char *s){
int i = 0, j = -1;
nextval[0] = -1;
while(i != len){
if(j == -1 || s[i] == s[j])
nextval[++i] = ++j;
else
j = nextval[j];
}
}
int main(){
int ncase;
int length, add;
scanf("%d", &ncase);
while(ncase--){
scanf("%s", s);
len = strlen(s);
getnext(s);
/*for(int i = 0; i <= len; ++i) //查看next数组的内容
cout<<nextval[i]<<" ";
cout<<endl;*/
length = len - nextval[len]; //循环节的长度
cout << length <<endl;
if(len != length && len % length == 0) //循环多次
printf("0\n");
else{
add = length - nextval[len] % length; //取余的作用：abcab，去掉abc
printf("%d\n",add);
}
}
return 0;
}
/*难题
给定一个大矩阵，求出求最小覆盖矩阵，大矩阵可由这个小矩阵拼成。
允许最后有超出的地方，如：abababa,ab可覆盖，abab也可
输出该矩阵的面积*/
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxr=10002;
const int maxc=80;
char grid[maxr][maxc]; //大矩阵
int row,col;//行和列
int rnext[maxr][maxc]; //rnext[i]：对应第i行字符串的next函数
int cnext[maxr]; //求纵向的next，每次比较的是整行
int rlen[maxr]; //rlen[i]：第i行字符串的最小循环子串的长度
int cnt[maxc];//cnt[i]：统计各宽度出现的次数
int ans_c,ans_r; //最小覆盖矩阵的宽度和高度
void rgetNext(int r,char*str){
int k=0;
rnext[r][1]=0;
for(int i=1;i<col;i++){
while(k&&str[k]!=str[i])
k=rnext[r][k];
if(str[k]==str[i])
k++;
rnext[r][i+1]=k;
}
rlen[r]=col-rnext[r][col];
int i;
for(i=rlen[r];i<=col;i+=rlen[r]){
cnt[i]++;
}
i-=rlen[r];
//直接通过比较来判断，是否还有可能存在的串，如aaabcaaa，除了5，还可能为6,7,8
//即判断第i+1个字符后的后缀是否和前缀相同
for(int j=i+1;j<=col;j++){
int x=0,y=j;//分别从索引0和y处开始比较
while(str[x]==str[y]){
x++;y++;
}
if(y==col)
cnt[j]++;
}
}
void cgetNext(){
int k=0;
cnext[1]=0;
for(int i=1;i<row;i++){
while(k&&strcmp(grid[k],grid[i])!=0)
k=cnext[k];
if(strcmp(grid[k],grid[i])==0)
k++;
cnext[i+1]=k;
}
ans_r=row-cnext[row];
}
int main(){
scanf("%d%d",&row,&col);
for(int i=0;i<row;i++)
scanf("%s",grid[i]);
memset(cnt,0,sizeof(cnt));
for(int i=0;i<row;i++)
rgetNext(i,grid[i]);
cgetNext();
for(int i=1;i<=col;i++){
if(cnt[i]==row){
ans_c=i;
break;
}
}
printf("%d\n",ans_c*ans_r);
return 0;
}
/*最短公共祖先问题
给定两个串，用其组成一个新串使得新串包含这两串
求该新串的最短长度*/
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1000100;
char a[3][2*N];
int fail[2*N];
inline int max(int a, int b){
return (a>b)?a:b;
}
int kmp(int &i,int &j,char* str,char* pat){
int k;
memset(fail,-1,sizeof(fail));
for (i=1;pat[i];++i){
for(k=fail[i-1];k>=0&&pat[i]!=pat[k+1];k=fail[k]);
if(pat[k+1]==pat[i]){
fail[i]=k+1;
}
}
i=j=0;
while(str[i]&&pat[j]){
if (pat[j]==str[i]){
i++;
j++;
}
else if(j==0)
i++;
else j=fail[j-1]+1;
}
if(pat[j]) return -1;
else return i-j;
}
int main(int argc,const char* argv[]){
int T;
scanf("%d",&T);
while (T--){
int i,j,l1=0,l2=0;
scanf("%s%s",a[0],a[1]);
//cin >> a[0] >> a[1];
int len1=(int)strlen(a[0]),len2=(int)strlen(a[1]),val;
val=kmp(i,j,a[1],a[0]);
if(val!=-1)
l1=len1;
else{
if(i==len2&&j-1>=0&&a[1][len2-1]==a[0][j-1])
l1=j;
}
val=kmp(i,j,a[0],a[1]);
if(val!=-1)
l2=len2;
else{
if(i==len1&&j-1>=0&&a[0][len1-1]==a[1][j-1])
l2=j;
}
printf("%d\n",len1+len2-max(l1, l2));
}
return 0;
}八、FFT
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define N 150010
const double pi = 3.141592653;
char s1[N>>1], s2[N>>1];
double rea[N], ina[N], reb[N], inb[N];
int ans[N>>1];
void Swap(double *x, double *y)
{
double t = *x;
*x = *y;
*y = t;
}
int Rev(int x, int len)
{
int ans = 0;
int i;
for(i = 0; i < len; i++){
ans<<=1;
ans |= (x & 1);
x>>=1;
}
return ans;
}//二进制的反转x->ans
//作用就是把这n个数分成我们想要的lgn个部分，且每个部分仅有两个待处理的，然后再处理
//不太明白的可以看看网上关于FFT中的二进制的翻转问题的博客啥的
void FFT(double *reA, double *inA, int n, bool flag)
{
int s;
double lgn = log((double)n) / log((double)2);//定义log(2)(n),也就是代表分裂次数
int i;
for(i = 0; i < n; i++){
int j = Rev(i, lgn);
if(j > i){
Swap(&reA[i], &reA[j]);
Swap(&inA[i], &inA[j]);
}
}
for(s = 1; s <= lgn; s++){//共进行lgn次
int m = (1<<s);
double reWm = cos(2*pi/m), inWm = sin(2*pi/m);//本原根
if(flag) inWm = -inWm;//对C来说就要转换为负的
int k;
for(k = 0; k < n; k += m){
double reW = 1.0, inW = 0.0;
int j;
for(j = 0; j < m / 2; j++){
int tag = k+j+m/2;//可以对照上文的公式看
double reT = reW * reA[tag] - inW * inA[tag];
double inT = reW * inA[tag] + inW * reA[tag];
double reU = reA[k+j], inU = inA[k+j];
reA[k+j] = reU + reT;
inA[k+j] = inU + inT;
reA[tag] = reU - reT;
inA[tag] = inU - inT;
double rew_t = reW * reWm - inW * inWm;
double inw_t = reW * inWm + inW * reWm; //这里实现迭代
reW = rew_t;
inW = inw_t;
}
}
}
if(flag){//对C来说需要除以n
for(i = 0; i < n; i++){
reA[i] /= n;
inA[i] /= n;
}
}
}
int main(){
while(~scanf("%s%s", s1, s2)){
int flag=0;
memset(ans, 0 , sizeof(ans));
memset(rea, 0 , sizeof(rea));
memset(ina, 0 , sizeof(ina));
memset(reb, 0 , sizeof(reb));
memset(inb, 0 , sizeof(inb));//初始化
int i, lent, len = 1, len1, len2;
len1 = strlen(s1);
len2 = strlen(s2);
/*if(s1[0]=='-'){
for(int i=0;i<len1;i++){
s1[i]=s1[i+1];
}
len1--;
flag^=1;
}
if(s2[0]=='-'){
for(int i=0;i<len2;i++){
s2[i]=s2[i+1];
}
len2--;
flag^=1;
}*///符号的判断
lent = (len1 > len2 ? len1 : len2);
while(len < lent) len <<= 1;
len <<= 1;// 保证长度为2的幂次，才能逐渐二分
for(i = 0; i < len; i++){
if(i < len1) rea[i] = (double)s1[len1-i-1] - '0';//将数组s1反转，并保存为double
if(i < len2) reb[i] = (double)s2[len2-i-1] - '0';//将数组s2反转，并保存为double
ina[i] = inb[i] = 0.0;
}
FFT(rea, ina, len, 0);//对A进行FFT
FFT(reb, inb, len, 0);//对B进行FFT
for(i = 0; i < len; i++){
double rec = rea[i] * reb[i] - ina[i] * inb[i];
double inc = rea[i] * inb[i] + ina[i] * reb[i];
rea[i] = rec; ina[i] = inc;
}//获得C的点值表达
FFT(rea, ina, len, 1);
for(i = 0; i < len; i++)
ans[i] = (int)(rea[i] + 0.4);//舍入
/*for(i = 0; i < len; i++){
ans[i+1] += ans[i] / 10;
ans[i] %= 10;
}*///消除进位
int len_ans = len1 + len2 + 2;
while(ans[len_ans] == 0 && len_ans > 0) len_ans--;
//if(flag) printf("-");
for(i = len_ans; i >= 0; i--)
printf("%d", ans[i]);
printf("\n");
}
return 0;
}九、常见技巧
关闭输入输出流
inline void init_cin() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}快速幂
long long qpow2(long long a, long long b){
long long ans=1;
if(b==0){
return 1;
}
if(b==1){
return a%M;
}
while(b>0){
if(b&1){
ans=(ans%M)*(a%M)%M;
}
a=(a%M)*(a%M)%M;
b>>=1;
}
return ans%M;
}差分
B[i]=A[i]-A[i-1];
//要使A[l,r]每个数加上一个d，可以转换为操作：B[l]+d，B[r+1]-d原文链接:https://www.cnblogs.com/dbettkk-1216/p/12049404.html
如有疑问请与原作者联系
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
相关文章
- 快速幂||取余运算（模板）... 2019-04-29
- 收集整理的一些c++书籍(推荐) 2019-04-28
- STL用法整理 2019-04-11
- 『嗨威说』常见的C++函数模板整理（一） 2019-02-27
- 剑指Offer整理笔记 2019-01-11
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
热门词条
最新资讯
热门关注
热门标签