板子整理

0
7

板子整理

目录

  • 排序(快排及其原理、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~NM条边,每条边有一个权值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的0i个元素和s的nj个元素的最长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

<

发布回复

请输入评论!
请输入你的名字