基本工具
编译器选项
-std=c++11文件读入
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif快速读入
inline int read()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}快速输出
inline void Write(int x) {
static int sta[15];
if (x<0) {putchar('-'); x=-x;}
register int top=0;
do{
sta[top++]=x%10,x/=10;
}while (x);
while (top) putchar(sta[--top]+48);
}常用文件头
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+5;STL
一些函数
// 不自定义比较函数的话记得实现运算符
sort();
// 二分，记得排序，记得实现比较运算符（和同结构体比，和int之类的比），记得排序
// 如果自定了比较函数，则前两个返回第一个不符合比较函数的迭代器，注意返回的是迭代器
lower_bound();
upper_bound();
equel_range();
binary_search()哈希表
unordered_map<int,int> number_map;
number_map.emplace(array1[i],array2[i]);
number_map[height1[i]];上下界
const int maxn = 1e5+5;
int num[maxn],res = 0;
int *p = lower_bound(num,num+res,x,greater<int>());
// greater<int> 找第一个小于等于的数的位置
int *p = upper_bound(num,num+res,x,greater<int>());
// greater<int> 找第一个小于的数的位置优先队列
struct node{
int u,v;
bool operator < (const node &a) const{
return this->v < a.v; // 大顶堆
//return this->v > a.v; // 小顶堆
}
};
int main(){
priority_queue <int,vector<int>,greater<int> > q_min; // 小顶堆 取出来最小
priority_queue <int,vector<int>,less<int> > q_max; //大顶堆 取出来最大
priority_queue <node> q;
for(int i=0;i<10;i++){
q.push({i,20-i});
}
while(!q.empty()){
node temp = q.top();
cout << temp.u << " " << temp.v << endl;
q.pop();
}
} 数据结构
二分查找
template <typename T>
int binary_search(const T* array, int n, T value) {
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == value) {
return mid;
} else if (array[mid] < value) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}并查集
int fa[maxn],size[maxn]; // 祖父节点和大小节点，若fa[i]==i，说明i是这个集合的根
inline void init(int n) // 初始化，每个节点是一个集合
{
for (int i = 1; i <= n; ++i){
fa[i] = i;
size[i] = 1;
}
}
int find(int x) // 查找x节点的集合的根，同时进行路径压缩
{
return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
inline void merge(int i, int j) // 对i节点和j节点进行合并
{
size[find(j)] += size[find(i)];
fa[find(i)] = find(j);
}树状数组（前缀和）
struct Bit {
#define Maxn 1000100
long long val[Maxn];
inline long long lowbit(int x) {return x & -x;} // 最低位1
inline void add(int x, long long v) {while (x < Maxn) {val[x] += v; x += lowbit(x);}} // x位添加v
inline long long ask(int x) {int res = 0; while (x) {res += val[x]; x -= lowbit(x);} return res;} // 返回x位前缀和
inline long long query(int l, int r) {return ask(r) - ask(l - 1);} // 返回[l, r]区间和
} bit;堆
第k小堆
struct Priority_Queue {
int k;
priority_queue<int> q1; // 大根堆，当前集合中最小的 k-1 个元素
priority_queue<int, vector<int>, greater<int> > q2; // 小根堆，保存剩下的所有元素
Priority_Queue() { }
Priority_Queue(int _k) : k(_k) {} // 构造方法，应该用这个
void push(int v) {
q1.push(v);
while (q1.size() >= k) q2.push(q1.top()), q1.pop();
}
void pop() {
if (!q2.empty()) q2.pop();
else if(!q1.empty()) q1.pop();
}
int top() { // 返回当前第k小
if (!q2.empty()) return q2.top();
else if(!q1.empty()) return q1.top();
else return -1;
}
};使用方法：
Priority_Queue pq(3); // 维护第 3 小
pq.push(5);
pq.push(1);
pq.push(7);
// 此时 pq.top() = 当前第 3 小可删除堆
struct p{
int data;
int k;
};
struct H{
#define N 1000000+5
#define type p
type Heap[N];
int HeapSize = 0;
int cmp(const type &a,const type &b){
return a.data<=b.data;
}
void swap(type arr[], int i, int j){
type temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void ShiftDown(int i){
int cur = i;
while(cur<=HeapSize){
int left = cur<<1;
int right = left + 1;
int min = cur;
if(left<=HeapSize&&cmp(Heap[left],Heap[min])) min = left;
if(right<=HeapSize&&cmp(Heap[right],Heap[min])) min = right;
if(min==cur) return;
else{
swap(Heap,cur,min);
cur = min;
}
}
}
void ShiftUp(int i){
int cur = i;
while(cur>1){
int parent = cur>>1;
if(!cmp(Heap[parent],Heap[cur])){
swap(Heap,parent,cur);
cur = parent;
}
else return;
}
}
void push(type num){
Heap[++HeapSize] = num;
ShiftUp(HeapSize);
}
void pop(){
if(HeapSize<=0) return ;
Heap[1] = Heap[HeapSize--];
ShiftDown(1);
}
// 删除第k个元素
void del(int k){
if(HeapSize<=0) return;
Heap[k] = Heap[HeapSize--];
ShiftDown(k);
ShiftUp(k);
}
// 修改第k个元素
void repl(int k,type num){
if(HeapSize<k) return;
Heap[k] = num;
ShiftDown(k);
ShiftUp(k);
}
type top(){
return Heap[1];
}
};分治
归并排序
#include <stdio.h>
int temp[10000];
void merge(int low,int mid,int high,int array[]){
int l = low;
int r = mid+1;
int t = low;
while(l<=mid&&r<=high){
if(array[l]<array[r]){
temp[t++] = array[l++];
}
else{
temp[t++] = array[r++];
}
}
while(l<=mid) temp[t++] = array[l++];
while(r<=high) temp[t++] = array[r++];
for(int i=low;i<=high;i++){
array[i]=temp[i];
}
}
void merge_sort(int low, int high,int array[]){
if(low<high){
int mid = low + (high-low)/2; //小知识点，如果直接相加可能会溢出
merge_sort(low,mid,array);
merge_sort(mid+1,high,array);
merge(low,mid,high,array);
}
}
int main(){
int a[5] = {5,4,3,2,1};
merge_sort(0,4,a);
for(int i=0;i<5;i++){
printf("%d ",a[i]);
}
return 0;
}
顺序统计量
// 9.2
int random_partition(std::vector<int>& a,int p,int r)
{
int ra=rand()%(r+1-p)+p;
std::swap(a[ra],a[r]);
int x=a[r];
int i=p-1;
for(int j=p;j<r;j++)
// 目前是从小到大
if(a[j]<=x)
std::swap(a[++i],a[j]);
std::swap(a[i+1],a[r]);
return i+1;
}
// a中从p到人、（均包含）的第i顺序统计量
int random_select(std::vector<int>& a,int p,int r,int i)
{
if(p==r)
return a[p];
int q=random_partition(a,p,r);
int k=q-p+1;
if(i==k)
return a[q];
else if(i<k)
return random_select(a,p,q-1,i);
else
return random_select(a,q+1,r,i-k);
}
void simu_min_max(const std::vector<int>& a,
int& min,int& max)
{
int begin_index=1;
if(a.size()%2==1)
{
min=max=a[0];
}
else
{
min=std::min(a[0],a[1]);
max=std::max(a[0],a[1]);
begin_index=2;
}
for(int i=begin_index;i<a.size();i+=2)
{
if(a[i]>a[i+1])
{
max=std::max(max,a[i]);
min=std::min(min,a[i+1]);
}
else
{
max=std::max(max,a[i+1]);
min=std::min(min,a[i]);
}
}
}
/* 数组版 */
int random_partition(int a[],int p,int r)
{
int ra=rand()%(r+1-p)+p;
std::swap(a[ra],a[r]);
int x=a[r];
int i=p-1;
for(int j=p;j<r;j++)
if(a[j]<=x)
std::swap(a[++i],a[j]);
std::swap(a[i+1],a[r]);
return i+1;
}
int random_select(int a[],int p,int r,int i)
{
if(p==r)
return a[p];
int q=random_partition(a,p,r);
int k=q-p+1;
if(i==k)
return a[q];
else if(i<k)
return random_select(a,p,q-1,i);
else
return random_select(a,q+1,r,i-k);
}
/* 使用参考 */
#include"chapter9.h"
void main()
{
int array[]={1,2,3,4,5,6,7,8,9,0};
std::vector<int> a(array,
array+sizeof(array)/sizeof(int));
//int rt=random_select(a,0,9,7);
//std::cout<<rt<<std::endl;
int min=0;int max=0;
simu_min_max(a,min,max);
std::cout<<"the min="<<min<<
" ,the max="<<max<<std::endl;
}快速幂
long long binpow(long long a, long long b) {
long long res = 1;
while (b > 0) {
if (b & 1) res = (res * a);
a = (a * a);
b >>= 1;
}
return res;
}动态规划
矩阵连乘
#include <bits/stdc++.h>
using namespace std;
const long long INF = (1LL<<62);
long long p[305];
long long n;
long long m[305][305];
long long MCM(int i, int j){
if (i == j) return 0;
if (m[i][j] != INF) return m[i][j];
long long best = INF;
for (int k = i; k <= j-1; ++k){
long long q = MCM(i, k) + MCM(k+1, j) + p[i-1]*p[k]*p[j];
if (q < best) best = q;
}
return m[i][j] = best;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 0; i <= n; ++i) cin >> p[i];
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= n; ++j){
m[i][j] = (i==j ? 0 : INF);
}
}
cout << MCM(1, n) << "\n";
return 0;
}钢管切割
//钢管切割最小值
#include<iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int length,MIN;//分别为长度和最小值
while(cin >> length)
{
int p[length+1];
for(int i = 1;i<=length;i++)
cin >> p[i];//依据题意，i长度的价值
int price[length+1];//保存每段价值
price[0] = 0;//会使用到price[0]，防止出错初始化
for(int i = 1;i<=length;i++)
{
MIN = 2147483647;//获得最小值时需要设为最大值
for(int j = 1;j<=i;j++)
{
if(MIN > p[j]+price[i-j])
//不断将i长度切割为前j部分和后i-j部分
//以找到i长度切割后的最小值
{
MIN = p[j] + price[i-j];//替换最小值
price[i] = MIN;
}
//状态转移方程介绍见实现解释
}
}
cout << price[length] << '\n';
//输出最长部分（i）切割后的最小值
}
return 0;
}求切割最大值、分割数量和分割方法：
#include <bits/stdc++.h>
using namespace std;
int n;
int p[10009];
long long max, k , a[10009];
long long r[10009], shang[10009]; // r是dp数组代表最大值，shang代表i长度分割出的第一段长度
void fenge(int t){
if(shang[t]==0){
a[++k] = t;
return;
}
fenge(shang[t]);
fenge(t-shang[t]);
}
int main(){
scanf("%d",&n);
for(int i = 1; i<=n; i++) scanf("%d",&p[i]);
for(int i = 1; i<=n; i++){
shang[i] = 0;
r[i] = p[i];
for(int j = 1; j <= i/2; j++){
long long now = r[j] + r[i-j];
if(now>r[i]){
r[i] = now;
shang[i] = j;
}
}
}
printf("%lld\n", r[n]);
k = 0;
fenge(n);
printf("%lld\n",k);
for(int i = 1; i<=k;i++) printf("%lld ",a[i]);
return 0;
}两流水线
//流水线调度基本问题
#include<iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int n;
int fend;
int i;
while(cin >> n)
{
int a[2][n+1],t[2][n];
//两条线上每一家花费的时间
for(i = 1;i<=n;i++)
cin >> a[0][i];
for(i = 1;i<=n;i++)
cin >> a[1][i];
//两条线不同位置转移的时间花费
for(i = 1;i<n;i++)
cin >> t[0][i];
for(i = 1;i<n;i++)
cin >> t[1][i];
//存储两条线不同位置的最小时间
int f[2][n+1];
//初始化防止错误
f[0][1] = a[0][1];
f[1][1] = a[1][1];
for(i = 2;i<=n;i++)
{
//具体状态转移方程介绍见实现解释
if(f[0][i-1]+a[0][i]<f[1][i-1]+t[1][i-1]+a[0][i])
f[0][i] = f[0][i-1]+a[0][i];
else
f[0][i] = f[1][i-1]+t[1][i-1]+a[0][i];
if(f[1][i-1]+a[1][i]<f[0][i-1]+t[0][i-1]+a[1][i])
f[1][i] = f[1][i-1]+a[1][i];
else
f[1][i] = f[0][i-1]+t[0][i-1]+a[1][i];
}
//计算两条线分别的最后时间花费得最小值
if(f[0][n]<f[1][n])
fend = f[0][n];
else
fend = f[1][n];
cout << fend << '\n';
}
return 0;
}多流水线
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int num,n;
int fend;
int i,j;
int tempf;
while(cin >> num >> n)//分别为线路个数和站台个数
{
int a[num][n+1],t[num][num];
for(i = 0;i<num;i++)
for(j = 1;j<=n;j++)
cin >> a[i][j];//i条线j站台的花费
for(i = 0;i<num;i++)
for(j = 0;j<num;j++)
cin >> t[i][j];//i条线到j条线的调度费用
int f[num][n+1];//一维为当前线路，二维为站台位置
for(i = 0;i<num;i++)
{
f[i][1] = a[i][1];//每条线第一个站台的最小花费就是第一个
}
for(i = 2;i<=n;i++)
{
for(j = 0;j<num;j++)
{
tempf = 2147483647;//为了找到最小值先设定最大的
for(int k = 0;k<num;k++)
{//循环判断所有条道路的情况
if(tempf > f[k][i-1]+t[k][j]+a[j][i])
{
tempf = f[k][i-1]+t[k][j]+a[j][i];
}
}
f[j][i] = tempf;//存储j条线在i站台的最小值
}
}
tempf = f[0][n];
for(i = 1;i<num;i++)
{
if(tempf > f[i][n])
{
tempf = f[i][n];
}
}
fend = tempf;//得到最大值
cout << fend << '\n';
}
return 0;
}最长上升子序列
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int a[n],dp[n];
for(int i = 0;i<n;i++)
{
cin >> a[i];
dp[i] = 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[j] + 1;//记录i处最长的上升序列长度
//即前面的序列长度最大长度+1即是i处的最大长度
}
}
}
int max = dp[0];//不一定最后一个是最长的，因此需要获取最大值
for(int i = 1;i<n;i++)
{
if(max < dp[i]) max = dp[i];
}
cout << max << '\n';
return 0;
}最长公共子串
void zichuan(){
int mm = 0;
for(int i = 0; i <l1;i++){
for(int j = 0; j < l2; j++){
m[i][j] = 0;
}
}
for(int i = 0; i <l1;i++){
for(int j = 0; j < l2; j++){
if(i==0){
if(s1[i] == s2[j]) m[i][j] = 1;
continue;
}if(j==0){
if(s1[i] == s2[j]) m[i][j] = 1;
continue;
}
m[i][j] = 0;
if(s1[i] == s2[j]) m[i][j] = m[i-1][j-1] + 1;
}
}
for(int i = 0; i <l1;i++){
for(int j = 0; j < l2; j++){
if(m[i][j] > mm) mm = m[i][j];
}
}
printf("%d" ,mm);
}最长公共子序列
void zixulie(){
for(int i = 0; i <l1;i++){
for(int j = 0; j < l2; j++){
m[i][j] = 0;
}
}
for(int i = 0; i <l1;i++){
for(int j = 0; j < l2; j++){
if(i==0){
if(s1[i] == s2[j]) m[i][j] = 1;
continue;
}if(j==0){
if(s1[i] == s2[j]) m[i][j] = 1;
continue;
}
m[i][j] = m[i-1][j-1];
if(s1[i] == s2[j]) m[i][j]++;
if(m[i][j] < m[i-1][j]) m[i][j] = m[i-1][j];
if(m[i][j] < m[i][j-1]) m[i][j] = m[i][j-1];
}
}
printf(" %d\n",m[l1-1][l2-1]);
return ;
}矩阵连乘
#include<iostream>
using namespace std;
int length;
int cut[2000][2000];
int count;
void printCut(int i,int j)
{
if(i == j)
cout << 'A' << i;
else
{
cout << '(';
printCut(i,cut[i][j]);
printCut(cut[i][j]+1,j);
count++;
cout << ')';
}
}
int main()
{
ios::sync_with_stdio(false);
int n;
cin >> n;
length = n;
int m[n+1];
for(int i = 0;i<=n;i++)
cin >> m[i];
int num[n+1][n+1];//对应矩阵个数即可
for(int i = 1;i<=n;i++)
num[i][i] = 0;
int temp;
count = 0;
for(int l = 2;l<=n;l++)
//l为1的情况不必讨论，因为就是矩阵自己，所以从2到n依次进行
{
for(int i = 1;i<=n-l+1;i++)
//从第一个矩阵一直到最后一个可到达的矩阵
//这样i表示的既是连续l个矩阵的第一个矩阵
//根据输入，第i个矩阵的行数：i-1的值，列数：i的值
{
int j = i+l-1;//当前l个矩阵的最后一个矩阵下标
num[i][j] = 2147483647;//用于比较
for(int k = i;k<=j-1;k++)
//k是节点，代表第k和k+1个矩阵之间的那个下标
//所以需要到达j-1，也就是第j个矩阵前的那个位置才算结束
//由位置可知k的值为第k个矩阵的列数即划分开时需要乘的值
{
temp = num[i][k]+num[k+1][j]+m[i-1]*m[k]*m[j];
//当前划分状态的计算次数，两个num分别为两侧矩阵链的次数，最后一项为合并后的新增次数
if(num[i][j]>temp)
{
num[i][j] = temp;
cut[i][j] = k;
}
}
}
}
printCut(1,n);
cout << '\n';
cout << count << '\n';//切割次数
cout << num[1][n] << '\n';//计算次数
return 0;
}最优搜索树
#include<iostream>
using namespace std;
const int MAX = 2147483647;
double **root;
int di;
int n;
void printOBST(int l,int r)
{
if(l == 1&&r == n)
{
di = 0;
cout << "k" << root[1][n] << "为根" << '\n';
}
int t,lt,rt;
t = root[l][r];
if(l == t)
cout << "d"<<di++ << "是k"<<t << "的左孩子" << '\n';
else
if(l < t)
{
lt = root[l][t-1];
cout << "k"<<lt << "是k"<<t << "的左孩子" << '\n';
printOBST(l,t-1);
}
else return ;
if(r == t)
cout << "d"<<di++ << "是k"<<t << "的右孩子" << '\n';
else
if(r > t)
{
rt = root[t+1][r];
cout << "k"<<rt << "是k"<<t << "的右孩子" << '\n';
printOBST(t+1,r);
}
else return ;
}
int main()
{
int maxi;
double temp;
while(cin >> n)
{
double p[n+1],q[n+1];
for(int i = 1;i<=n;i++)
cin >> p[i];
for(int i = 0;i<=n;i++)
cin >> q[i];
double e[n+2][n+1];//需要存储q的内容，因此n+2
double w[n+2][n+1];//同上
root = new double *[n+1];//只是在p中选root因此n+1即可
for(int i = 0;i<=n;i++)
root[i] = new double[n+1];
for(int i = 1;i<=n+1;i++)
{
e[i][i-1] = q[i-1];
w[i][i-1] = q[i-1];
}
for(int l = 1;l<=n;l++)
{
for(int i = 1;i<=n-l+1;i++)
{
maxi = i+l-1;
//i+l-1就是长度l时能到达的最大的数据下标
e[i][maxi] = MAX;
w[i][maxi] = w[i][maxi-1]+p[maxi]+q[maxi];
//i--j的总概率和即等于i--j-1的加上新增的maxi处的k和d的概率
for(int j = i;j<=maxi;j++)
{
temp = e[i][j-1]+e[j+1][maxi]+w[i][maxi];
if(temp < e[i][maxi])
{
e[i][maxi] = temp;
root[i][maxi] = j;
}
}
}
}
cout << "最小搜索期望为：" << e[1][n] << '\n';
cout << "树的形状如下：" << '\n';
printOBST(1,n);
}
return 0;
}0-1 背包问题
典型例题：求目标sum，求目标sum的方法数量
#include <bits/stdc++.h>
#define ll long long
const int maxn = 1e5;
using namespace std;
int n,bagVol;
int value[maxn],weight[maxn];
ll dp[maxn];
int main(){
// dp[j]表示包括至当前物品，最大容量为j的背包的最优选择
for(int i=0;i<n;i++){
for(int j=bagVol;j>=weight[i];j--){
dp[j] = (ll) max(dp[j],dp[j-weight[i]]+value[i]);
}
}
printf("%lld",dp[bagVol]);
return 0;
} 无穷背包问题
#include <bits/stdc++.h>
#define ll long long
const int maxn = 1e5;
using namespace std;
int n,bagVol;
int value[maxn],weight[maxn];
ll dp[maxn];
int main(){
for(int i=0;i<n;i++){
for(int j=weight[i];j<=bagVol;j++){
dp[j] = (ll) max(dp[j],dp[j-weight[i]]+value[i]);
}
}
printf("%lld",dp[bagVol]);
return 0;
} 区间dp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 305;
ll c[maxn][maxn],p[maxn]; // c[i][j] 表示 i-j个矩阵最优解 DP区间
int s[maxn][maxn];
void print(int i,int j){
if(i==j){
printf("A%d",i);
return;
}
else{
printf("(");
print(i,s[i][j]);
print(s[i][j]+1,j);
printf(")");
}
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<=n;i++) scanf("%lld",&p[i]);
for(int d=2;d<=n;d++){ // 遍历每个区间长度
for(int i=1;i<=n-d+1;i++){
int j = i+d-1;
c[i][j] = LLONG_MAX;
for(int k=i;k<j;k++){
ll newc = c[i][k] + c[k+1][j] + p[i-1]*p[k]*p[j];
if(newc<c[i][j]){
c[i][j] = newc;
s[i][j] = k;
}
}
}
}
print(1,n);
//printf("%lld",c[1][n]);
return 0;
} 方法种数
dp[j] += dp[j - nums[i]];图论算法
DFS
bool is_visit[maxn];
void dfs_visit(int v) {
is_visit[v] = 1;
// 此处添加访问逻辑
for(int edge_inx = h[v]; ~edge_inx; edge_inx = ne[edge_inx]) {
if(!is_visit[e[edge_inx]]) {
dfs_visit(e[edge_inx]);
}
}
// 访问退出时间戳
}
void dfs(int n) {
memset(is_visit, 0, sizeof(bool) * (n + 2));
for(int i = 1; i <= n; i++) {
if(!is_visit[i]) {
dfs_visit(i);
}
}
}BFS
bool is_visit[maxn];
void bfs_visit(int v) {
is_visit[v] = 1;
queue<int> q;
q.push(v);
while (!q.empty()) {
v = q.front();
q.pop();
for(int edge_inx = h[v]; ~edge_inx; edge_inx = ne[edge_inx]) {
if(!is_visit[e[edge_inx]]) {
// 访问逻辑
bfs_visit(e[edge_inx]);
q.push(e[edge_inx]);
}
}
}
}
void bfs(int n) {
memset(is_visit, 0, sizeof(bool) * (n + 2));
for(int i = 1; i <= n; i++) {
if(!is_visit[i]) {
bfs_visit(i);
}
}
}链式前向星
//链式前向星
#define maxn 100000
#define maxm 200000
int h[maxn], e[maxm], ne[maxm], cnt;
long long w[maxm];
void add(int a, int b, long long c){
e[cnt] = b;
w[cnt] = c;
ne[cnt] = h[a];
h[a] = cnt;
cnt++;
}
int main(){
memset(h, -1, sizeof h); //初始化
int u = 4;// u为起点
// 遍历此处结束的标志是不等于-1
for(int i = h[u]; ~i; i = ne[i]) {
printf("%d->%d",u,e[i]);
}
return 0;
}
/* 另一种写法 */
#define MAX_VERTEX 1000005
#define MAX_EDGE 2000005
//链式前向星所使用的边，数组下标为0处不存数据
struct Edge {
//目标顶点
int toV;
//该顶点的下一个边
int nextE;
unsigned long long weight;
}EDGE[MAX_EDGE * 2];
int EDGE_CNT;
void addEdge(int start, int to, unsigned long long weight) {
//初始值为0，先增加，下标为0处空着
EDGE_CNT++;
EDGE[EDGE_CNT].toV = to;
EDGE[EDGE_CNT].weight = weight;
EDGE[EDGE_CNT].nextE = HEAD[start];
HEAD[start] = EDGE_CNT;
}二分图
判断二分图
int color[maxn],n;
bool dfs(int u, int c) {
color[u] = c;
for(int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if(color[j]) {
if(color[j] == c) return 0;
}
else if(!dfs(j, 3 - c)) return 0;
}
return 1;
}
bool check() {
memset(color, 0, sizeof color);
for (int i = 1; i <= n; i ++)
if(!color[i])
if(!dfs(i, 1))
return 0;
return 1;
}二分图匹配
int G[maxn][maxn];
int vis[maxn],match[maxn];
bool dfs(int node,int m){
for(int i = 1; i<=m; i++) {
if(!vis[i]&&G[node][i]){
vis[i] = true;
if(!match[i]||dfs(match[i],m)){
match[i] = node;
return true;
}
}
}
return false;
}
int max_match(int n,int m){ // n 为左边的点的个数
int num = 0;
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i,m)) num++;
}
return num;
}kruskal
struct Edge
{
int u,v,w;
}edge[300005];
int f[50005],n,m,cnt;
long long ans;
bool cmp(Edge a,Edge b)
{
return a.w<b.w;
}
int find(int x)
{
while(x!=f[x]) x=f[x]=f[f[x]];
return x;
}
void kruskal()
{
sort(edge,edge+m,cmp);
for(int i=0;i<m;i++)
{
int u=find(edge[i].u);
int v=find(edge[i].v);
if(u==v) continue;
ans+=edge[i].w;
f[v]=u;
if(++cnt==n-1) break;
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=0;i<m;i++) scanf("%d %d %d",&edge[i].u,&edge[i].v,&edge[i].w);
kruskal();
printf("%lld",ans);
return 0;
}//使用边列表保存图，使用数组模拟并查集，允许重边的自环
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
#define MAX_VERTEX 200005
#define MAX_EDGE 500005
using namespace std;
struct Edge {
int u, v;
long long w;
}EDGE[MAX_EDGE];
//实现类似并查集的功能
//初始时每个元素值均为其下标，表示自己即为各自集合的根
//如果一个元素的值与其下标不同，即表示该元素被合并到其他集合中了
//但不一定被连接到其他集合的根，需要通过遍历，寻找被链接集合的根
int FIND_A[MAX_VERTEX];
//用于C++sort()的排序函数，返回true时表示元素顺序符合要求
bool edge_cmp(Edge left, Edge right);
//输入已经排序好的边列表，以及图的节点个数，元素个数
//能够处理掉重边和自环
long long kruskal(Edge *, int, int);
//寻找输入的顶点所对应的集合的根
int find(int);
int main() {
int n, m, u, v;
long long w;
cin >> n >> m;
for(int i = 0; i < m; i++) {
scanf("%d%d%lld", &EDGE[i].u, &EDGE[i].v, &EDGE[i].w);
}
sort(EDGE, EDGE + m, edge_cmp);
cout << kruskal(EDGE, n, m);
}
bool edge_cmp(Edge left, Edge right) {
return left.w < right.w;
}
long long kruskal(Edge *edges, int v_cnt, int e_cnt) {
//初始化并查集
for(int i = 0; i < v_cnt; i++) {
FIND_A[i] = i;
}
//记录始点在并查集中的根，终点在并查集中的根
int a_e_start, a_e_end;
//当已经插入的边的数目 == n-1 时停止
int r_cnt = 1;
long long length = 0;
for(int i = 0; i < e_cnt && r_cnt < v_cnt; i++) {
a_e_start = find(edges[i].u);
a_e_end = find(edges[i].v);
if(a_e_end == a_e_start) {
continue;
}
//这里需要将目标节点集合整个集合合并到源节点集合中，故不能FIND_A[edges[i].v] = a_e_start，这样只能合并一个或一部分节点
FIND_A[a_e_end] = a_e_start;
length += edges[i].w;
r_cnt++;
}
return length;
}
int find(int vertex) {
while(vertex != FIND_A[vertex]) {
vertex = FIND_A[vertex] = FIND_A[FIND_A[vertex]];
}
return vertex;
}SPFA
//给定一个可能有负环的有向带权图，首先判断其是否有负环，如果没有，给出最短路径
//使用spfa算法，这是bellman_ford算法的改进版
//仍使用链式前向星存储图
#include<stdio.h>
#include<iostream>
#include<queue>
#include<string.h>
#define MAX_VERTEX 2005
#define MAX_ARC 6005
//题目中给出的数值，用于表示正无穷
#define MAX_DIS 1000000000
using namespace std;
struct Arc {
int toV;
long long weight;
int next_index;
}ARCS[MAX_ARC];
int ARC_CNT;
long long DIS[MAX_VERTEX];
//标记目前该节点是否在队中
bool IS_IN_QUEUE[MAX_VERTEX];
//标记目前到该节点的最短路径所经历的弧数量
int VIA_CNT[MAX_VERTEX];
//链式前向星所使用的列表
int A_HEAD[MAX_VERTEX];
//传入以链式前向星表示的图，图的顶点数以及源顶点
bool spfa(Arc *arcs, int *a_head, int n, int s);
void add_arc(int from, int to, long long weight);
int main() {
int t, n = 0, m = 0;
int u, v;
long long w;
cin >> t;
for(int group = 0; group < t; group++) {
cin >> n >> m;
ARC_CNT = 0;
//memset(ARCS, 0, (m + 1) * sizeof(ARCS[0]));
memset(A_HEAD, 0, (n + 1) * sizeof(A_HEAD[0]));
for(int arc_line = 0; arc_line < m; arc_line++) {
scanf("%d%d%lld", &u, &v, &w);
add_arc(u, v, w);
}
if(!spfa(ARCS, A_HEAD, n, 1)) {
printf("boo how\n");
continue;
}
for(int output_v = 1; output_v <= n; output_v++) {
printf("%lld ", DIS[output_v]);
}
printf("\n");
}
return 0;
}
void add_arc(int from, int to, long long weight) {
ARC_CNT++;
ARCS[ARC_CNT].toV = to;
ARCS[ARC_CNT].weight = weight;
ARCS[ARC_CNT].next_index = A_HEAD[from];
A_HEAD[from] = ARC_CNT;
}
bool spfa(Arc *arcs, int *a_head, int n, int s) {
fill(DIS, DIS + n + 1, MAX_DIS);
memset(VIA_CNT, 0, (n + 1) * sizeof(VIA_CNT[0]));
memset(IS_IN_QUEUE, 0, (n + 1) * sizeof(IS_IN_QUEUE[0]));
DIS[s] = 0;
queue<int> q;
q.push(s);
IS_IN_QUEUE[s] = 1;
//该for循环是本题最大的坑点，由于题目要求判断“是否存在负环”，而不是“是否有源顶点能够到达的负环”，故需要将所有顶点入队一次以判断负环
//最严谨的做法是建立超级源点，以0权重通向所有顶点
//一般的spfa算法不需要该for循环
for(int i = 1; i <= n; i++) {
q.push(i);
IS_IN_QUEUE[i] = 1;
}
int vertex, to;
long long w;
while(!q.empty()) {
vertex = q.front();
q.pop();
IS_IN_QUEUE[vertex] = 0;
for(int arc_ind = a_head[vertex]; arc_ind; arc_ind = arcs[arc_ind].next_index) {
to = arcs[arc_ind].toV;
w = arcs[arc_ind].weight;
if(DIS[vertex] + w < DIS[to]) {
DIS[to] = DIS[vertex] + w;
VIA_CNT[to] = VIA_CNT[vertex] + 1;
//当到达该顶点的最短路径包含的弧数达到n时，说明有负环
if(VIA_CNT[to] >= n) {
return false;
}
//只有点该顶点的DIS在本轮被更新，才将该顶点入队，考虑松弛以它为始点的边，当然，如果顶点已经在队列中，则不再重复加入
if(!IS_IN_QUEUE[to]) {
q.push(to);
IS_IN_QUEUE[to] = 1;
}
}
}
}
return true;
}Dijkstra
#define mp make_pair
#define P pair<int,int>//pair<距离，编号>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
struct node {
int v,w,link;
}edge[2 * maxn];
int dis[maxn], head[maxn],cnt = 0;//visist数组全为0
priority_queue<P,vector<P>,greater<P> >q;//最小的元素在队首
void init(){
memset(head,-1,sizeof(head));
}
void add(int u,int v,int w) {
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].link = head[u];
head[u] = cnt;
cnt++;
}
void Dij (int n,int s) {
int visit[maxn];
for(int i = 1; i <= n; i++)
{
dis[i] = inf;
visit[i]=0;
}
dis[s] = 0;
q.push(mp(0,s));
while(q.size()) {
int u= q.top().second;
q.pop();
if(visit[u]==0)
{
visit[u]=1;
for(int i = head[u];i!=-1; i = edge[i].link)
{
int v=edge[i].v;
if(dis[v] > dis[u] + edge[i].w)
{
dis[v] = dis[u] + edge[i].w;
q.push(mp(dis[v],v));
}
}
}
}
}
int main(int argc, char** argv) {
// add(v,u,w);
// Dij (n,s);
}//使用链式前向星保存图，允许环路，重边，但不允许负边
//统计一共有多少条最短路
#include<stdio.h>
#include<iostream>
#include<queue>
#include<string.h>
#define MAX_VERTEX 1000005
#define MAX_EDGE 1600005
#define MOD 998244353
using namespace std;
//链式前向星所使用的边，数组下标为0处不存数据
struct Edge {
//目标顶点
int toV;
//该顶点的下一个边
int nextE;
unsigned long long weight;
}EDGE[MAX_EDGE * 2];
int EDGE_CNT;
//优先队列中顶点集合
struct Vertex {
int num;
unsigned long long dis;
bool operator<(const Vertex &pNext) const{
return dis > pNext.dis;
}
};
priority_queue<Vertex> Q;
//在dijkstra算法中，保存目前已经得到的，各个顶点到源点的最短距离
unsigned long long DIS[MAX_VERTEX];
int IS_VISIT[MAX_VERTEX];
//记录连接到对应顶点的边链表的头数组下标，如果值为0表示没有边
int HEAD[MAX_VERTEX];
// 维护目标
int PATH_CNT[MAX_VERTEX];
//为链式前向星链表添加节点，在链表头添加
void addEdge(int, int, unsigned long long);
//给出使用链式前向星保存的边信息，顶点数目，以及源顶点
void dijkstra(Edge *edges, int * head, int n, int s);
int main() {
int n, m, s, t, u, v;
cin >> n >> m >> s >> t;
EDGE_CNT = 0;
memset(HEAD, 0, sizeof(HEAD[0]) * (n + 1));
unsigned long long w;
for(int i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
addEdge(u, v, 1);
addEdge(v, u, 1);
}
dijkstra(EDGE, HEAD, n, s);
printf("%llu", PATH_CNT[t]);
return 0;
}
void addEdge(int start, int to, unsigned long long weight) {
//初始值为0，先增加，下标为0处空着
EDGE_CNT++;
EDGE[EDGE_CNT].toV = to;
EDGE[EDGE_CNT].weight = weight;
EDGE[EDGE_CNT].nextE = HEAD[start];
HEAD[start] = EDGE_CNT;
}
void dijkstra(Edge *edges, int * head, int n, int s) {
Vertex temp;
// 当前节点编号，和目标节点编号
int t_num, end_v;
memset(DIS, -1, (n + 1) * sizeof(unsigned long long));
// 初始化源顶点信息
DIS[s] = 0;
Q.push((Vertex){s, 0});
PATH_CNT[s] = 1;
while(!Q.empty()) {
temp = Q.top();
Q.pop();
//由于每达到一个顶点，就会对以它为始点的边进行松弛，松弛成功就会把后续点加入队列，因此可能会重复添加
if(IS_VISIT[temp.num]) {
continue;
}
IS_VISIT[temp.num] = 1;
t_num = temp.num;
for(int e_now = head[t_num]; e_now; e_now = edges[e_now].nextE) {
end_v = edges[e_now].toV;
if(DIS[end_v] > DIS[t_num] + edges[e_now].weight) {
DIS[end_v] = DIS[t_num] + edges[e_now].weight;
// 松弛成功，则刷新目标点最短路径数
PATH_CNT[end_v] = PATH_CNT[t_num];
if(!IS_VISIT[end_v]) {
Q.push((Vertex){end_v, DIS[end_v]});
}
}
// 如果松弛时发现路径长度与当前最短路长度相同，则将其最短路径数加和
else if(DIS[end_v] == DIS[t_num] + edges[e_now].weight) {
PATH_CNT[end_v] += PATH_CNT[t_num];
PATH_CNT[end_v] %= MOD;
}
}
}
}拓扑排序
#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5+5;
int n, m, cnt;
struct Edge
{
int to, next;
}edge[maxn];
int head[maxn],indegree[maxn];
void add_edge(int u, int v)
{
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
indegree[v]++;
}
int main()
{
cin >> n >> m;
int u, v;
for (int i = 0; i <= n; i++) head[i] = -1;
for (int i = 1; i <= m; i++)
{
cin >> u >> v;
add_edge(u, v);
}
priority_queue<int> q;
for(int i=n;i>=1;i--){
if(indegree[i]==0){
q.push(i);
}
}
while(!q.empty()){
int cur = q.top();
q.pop();
printf("%d ",cur);
for (int j = head[cur]; j != -1; j = edge[j].next){
indegree[edge[j].to]--;
if(indegree[edge[j].to]==0){
q.push(edge[j].to);
}
}
}
return 0;
}//使用邻接矩阵表示的图，允许有负边、自环、重边
//给出最短路
#include<stdio.h>
#include<string.h>
#define MAXSIZE 10
long long int D0[MAXSIZE][MAXSIZE];
int PI[MAXSIZE][MAXSIZE];
//输入待计算的邻接矩阵，算法执行完毕后二维数组中保存的将是最终结果
void floyd_warshall(long long int d[MAXSIZE][MAXSIZE], int pi[MAXSIZE][MAXSIZE], int n);
//使用floyd_warshell算法计算完毕后，使用该函数输出计算结果
void print_shortest(int u, int v);
void print_vertex(int u, int v);
int main() {
int n, m, q;
int u, v;
long long int temp;
//这种初始化方式要求各边权值，以及各路径长均小于0x3f3f3f3f3f3f3f3f
memset(D0, 0x3f, sizeof(D0));
//输入图的顶点数、边数、查询次数
scanf("%d %d %d", &n, &m, &q);
for(int i = 0; i < m; i++) {
scanf("%d %d %lld", &u, &v, &temp);
//能够同时处理重边
if(temp < D0[u][v]) {
D0[u][v] = temp;
PI[u][v] = u;
}
}
//初始化+处理自环
for(int i = 1; i <= n; i++) {
D0[i][i] = 0;
PI[i][i] = 0;
}
floyd_warshall(D0, PI, n);
for(int i = 0; i < q; i++) {
scanf("%d %d", &u, &v);
if(D0[u][v] != 0x3f3f3f3f3f3f3f3f) {
printf("%lld\n", D0[u][v]);
print_shortest(u, v);
}else {
printf("No So1ution\n");
}
}
}
void floyd_warshall(long long int d[MAXSIZE][MAXSIZE], int pi[MAXSIZE][MAXSIZE], int n) {
for(int k = 1; k <= n; k++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
//注意这里的等于号，去掉等于号不会导致路径长度错误，但会导致求不出来具体路径
if(d[i][j] <= d[i][k] + d[k][j]) {
d[i][j] = d[i][j];
}else {
d[i][j] = d[i][k] + d[k][j];
pi[i][j] = pi[k][j];
/*
该段文字用于简要证明可以直接原表修改元素：
首先我们容易观察到：
对于每个不同的k值，每次比较操作相当于，在自身以及两元素和之间选择最小值，
而这两元素和，分别为（i，j）在第k行和第k列上的投影。
其次：
对于在第k行和第k列的元素，比较操作不会改变其值。
最后：
对于第k行和第k列以外的元素，比较操作只会用到自身的值以及第k行和第k列上元素的值，同时只有可能更改自身的值，
因而前者不会受其他位置元素的操作影响，而后者在本轮操作中恒定不变。
综上：
可以原表修改元素。
*/
}
}
}
}
}
void print_shortest(int u, int v) {
if(PI[u][v] || u == v) {
print_vertex(u, v);
printf("%d\n", v);
}else{
printf("No\n");
}
}
void print_vertex(int u, int v) {
if(u == v) {
return;
}
print_vertex(u, PI[u][v]);
printf("%d ", PI[u][v]);
}Floyd-Warshall
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e14;
long long G[505][505];
int main(){
int n,m,p,u,v,w;
scanf("%d %d %d",&n,&m,&p);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j) G[i][j] = inf;
else G[i][j] = 0;
}
}
for(int i=0;i<m;i++){
scanf("%d %d %d",&u,&v,&w);
G[u][v] = (long long)min((int)G[u][v],w);
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(G[i][j]>G[i][k]+G[k][j]){
G[i][j]=G[i][k]+G[k][j];
}
}
}
}
for(int i=0;i<p;i++){
scanf("%d %d",&u,&v);
if(G[u][v]>=inf) printf("-1\n");
else printf("%lld\n",G[u][v]);
}
return 0;
}有向无环图哈密顿
//判断没有环路没有重边（本算法使用dfs方法允许有重边）的有向图是否存在哈密顿路径
//使用链式前向星保存图
//有机会可以补充一下使用其他方法找寻拓扑排序的算法
#include<stdio.h>
#include<string.h>
#include<string.h>
#include<queue>
#include<algorithm>
#define MAX_VERTEX 100005
#define MAX_ARC 200005
using namespace std;
//链式前向星保存边信息，但没有权重了
struct Arc {
int toV;
int next_index;
}ARCS[MAX_ARC];
int ARC_CNT;
//由于递归调用dfs_visit，为了节省栈空间，尽量少传参数
int N;
bool IS_VISIT[MAX_VERTEX];
int A_HEAD[MAX_VERTEX];
//倒序的拓扑排序序列
int TOPOLOGICAL_LIST[MAX_VERTEX];
int TP_CNT;
//使用dfs方法求出拓扑排序，并判断是否有哈密顿路径
bool topological_sort_dfs();
inline void add_arc(int from, int to);
void dfs_visit(int v);
//判断两顶点之间是否有弧
bool has_arc(int from, int to);
int main() {
int t, u, v, m = -1;
scanf("%d", &t);
for(int group = 0; group < t; group++) {
scanf("%d%d", &N, &m);
ARC_CNT = 0;
memset(A_HEAD, 0, (N + 1) * sizeof(A_HEAD[0]));
for(int arc_line = 0; arc_line < m; arc_line++) {
scanf("%d%d", &u, &v);
add_arc(u, v);
}
if(topological_sort_dfs()) {
printf("yy\n");
}else {
printf("nn\n");
}
}
}
inline void add_arc(int from, int to) {
ARC_CNT++;
ARCS[ARC_CNT].toV = to;
ARCS[ARC_CNT].next_index = A_HEAD[from];
A_HEAD[from] = ARC_CNT;
}
bool topological_sort_dfs() {
memset(IS_VISIT, 0, (N + 1) * sizeof(IS_VISIT[0]));
TP_CNT = 0;
for(int i = 1; i <= N; i++) {
dfs_visit(i);
}
for(TP_CNT--; TP_CNT; TP_CNT--) {
if(!has_arc(TOPOLOGICAL_LIST[TP_CNT], TOPOLOGICAL_LIST[TP_CNT - 1])) {
return 0;
}
}
return 1;
}
void dfs_visit(int v) {
if(IS_VISIT[v]) {
return;
}
IS_VISIT[v] = 1;
for(int arc_now = A_HEAD[v]; arc_now; arc_now = ARCS[arc_now].next_index) {
dfs_visit(ARCS[arc_now].toV);
}
// 最后获得倒序的拓扑序列
TOPOLOGICAL_LIST[TP_CNT++] = v;
}
bool has_arc(int from, int to) {
for(int arc_now = A_HEAD[from]; arc_now; arc_now = ARCS[arc_now].next_index) {
if(ARCS[arc_now].toV == to) {
return 1;
}
}
return 0;
}最大流
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 10010, E = 200010;
int n, m, s, t; LL ans = 0;
LL cnt = 1, first[N], nxt[E], to[E], val[E];
inline void addE(int u, int v, LL w) {
to[++cnt] = v;
val[cnt] = w;
nxt[cnt] = first[u];
first[u] = cnt;
}
int dep[N], q[N], l, r;
bool bfs() {//顺着残量网络，方法是 bfs；这是个bool型函数，返回是否搜到了汇点
memset(dep, 0, (n + 1) * sizeof(int));//记得开局先初始化，<<<清零大小要注意>>>
q[l = r = 1] = s;
dep[s] = 1;
while(l <= r) {
int u = q[l++];
for(int p = first[u]; p; p = nxt[p]) {
int v = to[p];
if(val[p] and !dep[v]) {//按照有残量的边搜过去
dep[v] = dep[u] + 1;
q[++r] = v;
}
}
}
return dep[t];//dep[t] != 0，就是搜到了汇点
}
LL dfs(int u, LL in/*u收到的支持（不一定能真正用掉）*/) {
//注意，return 的是真正输出的流量
if(u == t)
return in;//到达汇点是第一个有效return
LL out = 0;
for(int p = first[u]; p and in; p = nxt[p]) {
int v = to[p];
if(val[p] and dep[v] == dep[u] + 1) {//仅允许流向下一层
LL res = dfs(v, min(val[p], in)/*受一路上最小流量限制*/);
//res是v真正输出到汇点的流量
val[p] -= res;
val[p ^ 1] += res;
in -= res;
out += res;
}
}
if(out == 0)//我与终点（顺着残量网络）不连通
dep[u] = 0;//上一层的点请别再信任我，别试着给我流量
return out;
}
int main() {
scanf("%d %d %d %d", &n, &m, &s, &t);// s为起点 t为终点编号
for(int i = 1; i <= m; ++i) {
int u, v; LL w;
scanf("%d %d %lld", &u, &v, &w);
addE(u, v, w);
addE(v, u, 0);
}
while(bfs())
ans += dfs(s, 1e18);
printf("%lld\n", ans);
return 0;
}//使用链式前向星存储图，使用dinic算法计算最大流，加以多路增广和当前弧优化
#include<stdio.h>
#include<queue>
#include<string.h>
#define MAX_VERTEX 105
#define MAX_ARC 5005
#define MAX_VALUE __LONG_LONG_MAX__
using namespace std;
//链式前向星的弧结构体，直接保存残量网络，在读入边时即创建初始的残量网络，保存当前弧上的残余流量
//第一条弧的下标必须是0，这样就不需要保存反向弧下标
struct Arc {
int toV;
long long rest;
int next;
}ARCS[MAX_ARC * 2];
int ARC_CNT, N;
//链式前向星中记录顶点的弧链表的下标
int A_HEAD[MAX_VERTEX];
int CUR[MAX_VERTEX];
//该数组用于保存bfs给出的节点分层，层间的弧以及比目标点还深的顶点将会被忽略
int DEPTH[MAX_VERTEX];
//添加一条单向弧，在本算法实现中必须两条反向的弧一起添加
void add_arc(int from, int to, long long rest);
//输入源顶点以及目标顶点，使用优化dinic算法计算最大流并返回
long long dinic(int s, int t);
//记源顶点为第一层，将各顶点分层，将在到达目标顶点时停止，返回真
//如果残量网络中不存在源顶点到目标顶点的增广路，则返回假
bool bfs(int s, int t);
//给出期望加载给s的入流量，返回在目标点为t的情况下，s最大能接受的流量
//不同于以往的dfs，该dfs在到达某顶点之后，并不会简单将其标记为“以访问”，而是当起不能再接受流量之后再不再访问，即“多路增广”
//当发现本次分层后，某顶点不能再接受更多流量，即不再询问它能接受多少流量，即“当前弧优化”
long long dfs(int s, int t, long long flow);
int main() {
int t, m, u, v, s, target;
long long cap;
scanf("%d", &t);
for(int group = 0; group < t; group++) {
scanf("%d%d%d%d", &N, &m, &s, &target);
ARC_CNT = 0;
//由于ARCS第一条弧下标为0，故初始值置为-1，表示没有后续弧
memset(A_HEAD, -1, sizeof(A_HEAD));
for(int arc_line = 0; arc_line < m; arc_line++) {
scanf("%d%d%lld", &u, &v, &cap);
//必须同时添加原弧以及反向弧，使得可以直接通过将边下标抑或1获取反向边
add_arc(u, v, cap);
add_arc(v, u, 0);
}
printf("%lld\n", dinic(s, target));
}
}
void add_arc(int from, int to, long long rest) {
ARCS[ARC_CNT].toV = to;
ARCS[ARC_CNT].rest = rest;
ARCS[ARC_CNT].next = A_HEAD[from];
A_HEAD[from] = ARC_CNT;
ARC_CNT++;
}
long long dinic(int s, int t) {
long long result = 0;
while(bfs(s, t)) {
result += dfs(s, t, MAX_VALUE);
}
return result;
}
bool bfs(int s, int t) {
memset(DEPTH, 0, sizeof(DEPTH));
queue<int> q;
int from, to;
DEPTH[s] = 1;
q.push(s);
CUR[s] = A_HEAD[s];
while(!q.empty()) {
from = q.front();
q.pop();
for(int arc_now = A_HEAD[from]; ~arc_now; arc_now = ARCS[arc_now].next) {
to = ARCS[arc_now].toV;
if(ARCS[arc_now].rest && !DEPTH[to]) {
DEPTH[to] = DEPTH[from] + 1;
CUR[to] = A_HEAD[to];
if(to == t) {
return 1;
}
q.push(to);
}
}
}
return false;
}
long long dfs(int from, int t, long long flow) {
if(from == t || !flow) {
return flow;
}
long long rest = flow, acceptable;
int to;
for(int arc_now = CUR[from]; ~arc_now && rest; arc_now = ARCS[arc_now].next){
to = ARCS[arc_now].toV;
// 这个地方是关键优化，搜索到当前弧表示之前的都没了
CUR[from] = arc_now;
if(ARCS[arc_now].rest && DEPTH[to] == DEPTH[from] + 1) {
acceptable = dfs(to, t, min(rest, ARCS[arc_now].rest));
if(!acceptable) {
DEPTH[to] = 0;
}
rest -= acceptable;
ARCS[arc_now].rest -= acceptable;
//反向弧
ARCS[arc_now ^ 1].rest += acceptable;
}
}
//rest为剩下的流量，flow - rest即为能够接受的流量
return flow - rest;
}二分图最大匹配
#include <cstdio>
#include <vector>
const int maxn = 1005;
int n, m, t;
int mch[maxn], vistime[maxn];
std::vector<int> e[maxn];
bool dfs(const int u, const int tag);
int main() {
scanf("%d %d %d", &n, &m, &t);
for (int u, v; t; --t) {
scanf("%d %d", &u, &v);
e[u].push_back(v);
}
int ans = 0;
for (int i = 1; i <= n; ++i) if (dfs(i, i)) {
++ans;
}
printf("%d\n", ans);
}
bool dfs(const int u, const int tag) {
if (vistime[u] == tag) return false;
vistime[u] = tag;
for (auto v : e[u]) if ((mch[v] == 0) || dfs(mch[v], tag)) {
mch[v] = u;
return true;
}
return false;
}计算几何
张正奇的超全版
#include <bits/stdc++.h>
using namespace std;
#define inf 1e100
#define eps 1e-8
//用于浮点数正负判断，根据题目精度修改
const double pi = acos(-1.0); //圆周率
int sgn(double x)
{
if (fabs(x) < eps)
return 0;
if (x < 0)
return -1;
return 1;
} //判断浮点数正负
double sqr(double x) { return x * x; } //距离等运算涉及大量平方，简便
//使用Point时注意部分函数是返回新Point而非修改本身值
struct Point
{
double x, y;
/*构造函数*/
Point() {}
Point(double xx, double yy)
{
x = xx;
y = yy;
}
/*重载一些点的基础运算符*/
bool operator==(Point b) const
{
return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
}
bool operator<(Point b) const
{
return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;
}
Point operator-(const Point &b) const
{
return Point(x - b.x, y - b.y);
}
Point operator+(const Point &b) const
{
return Point(x + b.x, y + b.y);
}
Point operator*(const double &k) const
{
return Point(x * k, y * k);
}
Point operator/(const double &k) const
{
return Point(x / k, y / k);
}
//叉积
double operator^(const Point &b) const
{
return x * b.y - y * b.x;
}
//点积
double operator*(const Point &b) const
{
return x * b.x + y * b.y;
}
/*当前点为p，求角apb大小*/
double rad(Point a, Point b)
{
Point p = *this;
return fabs(atan2(fabs((a - p) ^ (b - p)), (a - p) * (b - p)));
}
/*逆时针旋转90度*/
Point rotleft()
{
return Point(-y, x);
}
/*顺时针旋转90度*/
Point rotright()
{
return Point(y, -x);
}
//两点距离
double dis(Point p)
{
return sqrt(sqr(x - p.x) + sqr(y - p.y));
}
//原点距离
double abs()
{
return sqrt(abs2());
}
double abs2()
{
return sqr(x) + sqr(y);
}
//改变向量长度
Point trunc(double r)
{
double l = abs();
if (!sgn(l))
return *this;
r /= l;
return Point(x * r, y * r);
}
//单位化
Point unit() { return *this / abs(); }
// IO
void input()
{
scanf("%lf%lf", &x, &y);
}
void output()
{
printf("%.7f %.7f\n", x, y);
}
//绕着p点逆时针旋转angle
Point rotate(Point p, double angle)
{
Point v = (*this) - p;
double c = cos(angle), s = sin(angle);
return Point(p.x + v.x * c - v.y * s, p.y + v.x * s + v.y * c);
}
};
struct Line
{
//两点确定直线
Point s, e;
Line() {}
Line(Point ss, Point ee)
{
s = ss;
e = ee;
}
void input()
{
s.input();
e.input();
}
//点在线段上
bool checkPS(Point p)
{
return sgn((p - s) ^ (e - s)) == 0 && sgn((p - s) * (p - e)) <= 0;
}
//直线平行
bool parallel(Line v)
{
return sgn((e - s) ^ (v.e - v.s)) == 0;
}
//点和直线关系
// 1 在左侧
// 2 在右侧
// 3 在直线上
int relation(Point p)
{
int c = sgn((p - s) ^ (e - s));
if (c < 0)
return 1;
else if (c > 0)
return 2;
else
return 3;
}
//线段相交
// 2 规范相交
// 1 非规范相交
// 0 不相交
int checkSS(Line v)
{
int d1 = sgn((e - s) ^ (v.s - s));
int d2 = sgn((e - s) ^ (v.e - s));
int d3 = sgn((v.e - v.s) ^ (s - v.s));
int d4 = sgn((v.e - v.s) ^ (e - v.s));
if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2)
return 2;
return (d1 == 0 && sgn((v.s - s) * (v.s - e)) <= 0) ||
(d2 == 0 && sgn((v.e - s) * (v.e - e)) <= 0) ||
(d3 == 0 && sgn((s - v.s) * (s - v.e)) <= 0) ||
(d4 == 0 && sgn((e - v.s) * (e - v.e)) <= 0);
}
//直线和线段相交
// 2 规范相交
// 1 非规范相交
// 0 不相交
int checkLS(Line v)
{
int d1 = sgn((e - s) ^ (v.s - s));
int d2 = sgn((e - s) ^ (v.e - s));
if ((d1 ^ d2) == -2)
return 2;
return (d1 == 0 || d2 == 0);
}
//两直线关系
// 0 平行
// 1 重合
// 2 相交
int checkLL(Line v)
{
if ((*this).parallel(v))
return v.relation(s) == 3;
return 2;
}
//直线交点
Point isLL(Line v)
{
double a1 = (v.e - v.s) ^ (s - v.s);
double a2 = (v.e - v.s) ^ (e - v.s);
return Point((s.x * a2 - e.x * a1) / (a2 - a1), (s.y * a2 - e.y * a1) / (a2 - a1));
}
//点到直线的距离
double disPL(Point p)
{
return fabs((p - s) ^ (e - s)) / (s.dis(e));
}
//点到线段的距离
double disPS(Point p)
{
if (sgn((p - s) * (e - s)) < 0 || sgn((p - e) * (s - e)) < 0)
return min(p.dis(s), p.dis(e));
return disPL(p);
}
//两线段距离
double disSS(Line v)
{
return min(min(disPS(v.s), disPS(v.e)), min(v.disPS(s), v.disPS(e)));
}
//点在直线上投影
Point proj(Point p)
{
return s + (((e - s) * ((e - s) * (p - s))) / ((e - s).abs2()));
}
//向垂直有向直线的左侧移动x
Line push(double x)
{
Point tmp = e - s;
tmp = tmp.rotleft().trunc(x);
Point ss = s + tmp;
Point ee = e + tmp;
return {ss, ee};
}
};
//多边形面积，需保证A逆时针
double area(vector<Point> A)
{
double ans = 0;
for (int i = 0; i < A.size(); i++)
ans += (A[i] ^ A[(i + 1) % A.size()]);
return ans / 2;
}
int contain(vector<Point> A, Point q)
{ // 2 内部 1 边界 0 外部
int pd = 0;
A.push_back(A[0]);
for (int i = 1; i < A.size(); i++)
{
Point u = A[i - 1], v = A[i];
if (Line(u, v).checkPS(q))
return 1;
if (sgn(u.y - v.y) > 0)
swap(u, v);
if (sgn(u.y - q.y) >= 0 || sgn(v.y - q.y) < 0)
continue;
if (sgn((u - v) ^ (q - v)) < 0)
pd ^= 1;
}
return pd << 1;
}
//凸包
vector<Point> ConvexHull(vector<Point> A, int flag = 1)
{ // flag=0 不严格 flag=1 严格
int n = A.size();
vector<Point> ans(n * 2);
sort(A.begin(), A.end());
int now = -1;
for (int i = 0; i < A.size(); i++)
{
while (now > 0 && sgn((ans[now] - ans[now - 1]) ^ (A[i] - ans[now - 1])) < flag)
now--;
ans[++now] = A[i];
}
int pre = now;
for (int i = n - 2; i >= 0; i--)
{
while (now > pre && sgn((ans[now] - ans[now - 1]) ^ (A[i] - ans[now - 1])) < flag)
now--;
ans[++now] = A[i];
}
ans.resize(now);
return ans;
}
//凸包周长
double convexC(vector<Point> A)
{
double ans = 0;
for (int i = 0; i < A.size() - 1; i++)
{
ans += A[i].dis(A[i + 1]);
}
ans += A[A.size() - 1].dis(A[0]);
return ans;
}
//凸包直径(最远点对)
double convexDiameter(vector<Point> A)
{
int now = 0, n = A.size();
double ans = 0;
for (int i = 0; i < A.size(); i++)
{
now = max(now, i);
while (1)
{
double k1 = A[i].dis(A[now % n]), k2 = A[i].dis(A[(now + 1) % n]);
ans = max(ans, max(k1, k2));
if (k2 > k1)
now++;
else
break;
}
}
return ans;
}
// 最近点对, 先要按照 x 坐标排序
double closepoint(vector<Point> &A, int l, int r)
{
if (r - l <= 5)
{
double ans = 1e20;
for (int i = l; i <= r; i++)
for (int j = i + 1; j <= r; j++)
ans = min(ans, A[i].dis(A[j]));
return ans;
}
int mid = l + r >> 1;
double ans = min(closepoint(A, l, mid), closepoint(A, mid + 1, r));
vector<Point> B;
for (int i = l; i <= r; i++)
if (abs(A[i].x - A[mid].x) <= ans)
B.push_back(A[i]);
sort(B.begin(), B.end(), [&](Point k1, Point k2)
{ return k1.y < k2.y; });
for (int i = 0; i < B.size(); i++)
for (int j = i + 1; j < B.size() && B[j].y - B[i].y < ans; j++)
ans = min(ans, B[i].dis(B[j]));
return ans;
}
int main(){
int n=getint();
for(int i=0;i<n;i++){
double x=getdb(),y=getdb();
p.push_back((Point){x,y});
}
ans=ConvexHull(p,1);
printf("%.6f\n",convexDiameter(ans));
return 0;
}线段关系
inline double Min(double a,double b){return (a<b)?a:b;}
inline double Max(double a,double b){return (a>b)?a:b;}
inline double Fabs(double x){return (x<-EPS)?-x:(x>EPS)?x:0;}
inline bool Equ(double x,double y){return (Fabs(x-y)<EPS);}
inline int Sgn(double x){
if (Fabs(x)==0) return 0;
if (x>0) return 1; else return -1;
}
struct Vector{
double x,y;
void Clean(void){x=y=0;}
void Write(void){printf("%.3lf %.3lf\n",x+EPS,y+EPS);}
Vector operator +(Vector p){return (Vector){x+p.x,y+p.y};}
Vector operator -(Vector p){return (Vector){x-p.x,y-p.y};}
double operator *(Vector p){return x*p.y-y*p.x;}
double operator &(Vector p){return x*p.x+y*p.y;}
};
typedef Vector V;
struct Point{
double x,y;
void Clean(void){x=y=0.0;}
void Write(void){printf("%.3lf %.3lf\n",x+EPS,y+EPS);}
bool operator ==(Point a){return (Equ(x-a.x,0) && Equ(y-a.y,0));}
Point operator +(Point p){return (Point){x+p.x,y+p.y};}
Point operator /(double l){return (Point){x/l,y/l};}
Vector operator -(Point p){return (Vector){x-p.x,y-p.y};}
};
typedef Point P;
inline void SW(P &a,P &b){P t=a; a=b; b=t;}
inline double Dis2(P a,P b){return pow(a.x-b.x,2)+pow(a.y-b.y,2);}
inline double Dis(P a,P b){return pow(pow(a.x-b.x,2)+pow(a.y-b.y,2),0.5);}
struct Circle{
Point o;
double r;
void Clean(void){o.x=o.y=0.0;}
void Write(void){printf("%.3lf %.3lf %.3lf\n",o.x,o.y,r);}
bool operator &(Circle a){return (Dis(o,a.o)+r <= a.r+EPS);}
};
typedef Circle C;
inline double Convex_Size(P a[],int n){
register int i=0,t=0;
double s=0;
P O;
O.x=O.y=0;
for (i=1;i<=n;i++){
t=(i<n)?i+1:1;
s+=(a[i]-O)*(a[t]-O);
}
return s/2;
}
inline bool Point_On_Seg(P x,P y,P z){
double s;
s=(x-y)*(x-z);
if (Fabs(s)>EPS) return 0;
if (Min(y.x,z.x)-EPS>x.x||Max(y.x,z.x)+EPS<x.x) return 0;
if (Min(y.y,z.y)-EPS>x.y||Max(y.y,z.y)+EPS<x.y) return 0;
return 1;
}
inline bool Seg_Cross(P a,P b,P c,P d){
if (Point_On_Seg(a,c,d) || Point_On_Seg(b,c,d) || Point_On_Seg(c,a,b) || Point_On_Seg(d,a,b)) return 1;
if (Sgn((b-a)*(c-a)) * Sgn((b-a)*(d-a)) >= 0) return 0;
if (Sgn((d-c)*(a-c)) * Sgn((d-c)*(b-c)) >= 0) return 0;
return 1;
}凸包
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n;
struct ben
{
double x,y;
}p[maxn],s[maxn];
double check(ben a1,ben a2,ben b1,ben b2)//检查叉积是否大于0，如果是a就逆时针转到b
{
return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);
}
double d(ben p1,ben p2)//两点间距离。。。
{
return sqrt((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));
}
bool cmp(ben p1,ben p2)//排序函数，这个函数别写错了，要不然功亏一篑
{
double tmp=check(p[1],p1,p[1],p2);
if(tmp>0)
return 1;
if(tmp==0&&d(p[0],p1)<d(p[0],p2))
return 1;
return 0;
}
int main()
{
scanf("%d",&n);
double mid;
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
if(i!=1&&p[i].y<p[1].y)//这是找最低点
{
mid=p[1].y;p[1].y=p[i].y;p[i].y=mid;
mid=p[1].x;p[1].x=p[i].x;p[i].x=mid;
}
}
sort(p+2,p+1+n,cmp);//系统快排
s[1]=p[1];//最低点一定在凸包里
int cnt=1;
for(int i=2;i<=n;i++)
{
while(cnt>1&&check(s[cnt-1],s[cnt],s[cnt],p[i])<=0) //判断前面的会不会被踢走，如果被踢走那么出栈
cnt--;
cnt++;
s[cnt]=p[i];
}
s[cnt+1]=p[1];//最后一个点回到凸包起点
double ans=0;
for(int i=1;i<=cnt;i++)
ans+=d(s[i],s[i+1]);//然后s里存好了凸包序列，只需要把两两距离累加就行
printf("%.2lf\n",ans);
return 0;
}多边形面积，点是逆时针
#include <bits/stdc++.h>
using namespace std;
struct point{
int x;
int y;
};
point a[105];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d %d",&a[i].x,&a[i].y);
}
int res = 0;
a[n].x=a[0].x;
a[n].y=a[0].y;
for(int i=0;i<n;i++)
{
res+=(a[i].x*a[i+1].y-a[i+1].x*a[i].y);
}
printf("%d",res/2);
return 0;
}线段相交
#include <bits/stdc++.h>
using namespace std;
struct Line {
int x1;
int y1;
int x2;
int y2;
};
bool intersection(const Line &l1, const Line &l2)
{
//快速排斥实验
if ((l1.x1 > l1.x2 ? l1.x1 : l1.x2) < (l2.x1 < l2.x2 ? l2.x1 : l2.x2) ||
(l1.y1 > l1.y2 ? l1.y1 : l1.y2) < (l2.y1 < l2.y2 ? l2.y1 : l2.y2) ||
(l2.x1 > l2.x2 ? l2.x1 : l2.x2) < (l1.x1 < l1.x2 ? l1.x1 : l1.x2) ||
(l2.y1 > l2.y2 ? l2.y1 : l2.y2) < (l1.y1 < l1.y2 ? l1.y1 : l1.y2))
{
return false;
}
//跨立实验
if ((((l1.x1 - l2.x1)*(l2.y2 - l2.y1) - (l1.y1 - l2.y1)*(l2.x2 - l2.x1))*
((l1.x2 - l2.x1)*(l2.y2 - l2.y1) - (l1.y2 - l2.y1)*(l2.x2 - l2.x1))) > 0 ||
(((l2.x1 - l1.x1)*(l1.y2 - l1.y1) - (l2.y1 - l1.y1)*(l1.x2 - l1.x1))*
((l2.x2 - l1.x1)*(l1.y2 - l1.y1) - (l2.y2 - l1.y1)*(l1.x2 - l1.x1))) > 0)
{
return false;
}
return true;
}
Line L[1005];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d%d%d",&L[i].x1,&L[i].y1,&L[i].x2,&L[i].y2);
}
int res = 0;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
res += intersection(L[i],L[j]);
}
}
printf("%d",res);
}半平面交
#include <bits/stdc++.h>
using namespace std;
const int N=510;
struct Node
{
double x,y;
Node operator - (const Node A) {return (Node){x-A.x,y-A.y};}
Node operator + (const Node A) {return (Node){x+A.x,y+A.y};}
Node operator * (double t) {return (Node){x*t,y*t};}
double crs(Node A) {return x*A.y-y*A.x;}
}A[N],B[N],C[N];
int n,m,tt,node;
void Add(Node a1,Node a2,Node b1,Node b2)
{
Node a=a2-a1,b=b2-b1,c=b1-a1;
double t=b.crs(c)/b.crs(a);
C[++tt]=a1+a*t;
}
void Cut(Node a,Node b)
{
tt=0;A[node+1]=A[1];
for(int i=1;i<=node;i++)
if((a-A[i]).crs(b-A[i])>=0)
{
C[++tt]=A[i];
if((a-A[i+1]).crs(b-A[i+1])<0)
Add(A[i],A[i+1],a,b);
}
else if((a-A[i+1]).crs(b-A[i+1])>=0)
Add(A[i],A[i+1],a,b);
for(int i=1;i<=tt;i++) A[i]=C[i];
node=tt;
}
double CalcS()
{
double res=0;
for(int i=2;i<node;i++) res+=(A[i]-A[1]).crs(A[i+1]-A[1]);
return res/2;
}
int main()
{
cin>>n>>m;node=m;n--;
for(int i=1;i<=m;i++) cin>>A[i].x>>A[i].y;
while(n--)
{
cin>>m>>B[1].x>>B[1].y;B[m+1]=B[1];
for(int i=2;i<=m;i++) cin>>B[i].x>>B[i].y;
for(int i=1;i<=m;i++) Cut(B[i],B[i+1]);
}
return printf("%.3f\n",CalcS()),0;
}旋转卡壳
//旋转卡壳求凸包直径，改改能干别的
double rotatingCalipersConvexDiameter(vector<Point> A)
{
int now = 0, n = A.size();
double ans = 0;
A.push_back(A[0]);
for (int i = 0; i < n; i++)
{
while (((A[i + 1] - A[i]) ^ (A[now] - A[i])) < ((A[i + 1] - A[i]) ^ (A[now + 1] - A[i]))) now = (now + 1) % n;
ans = max(ans, max(A[i].dis(A[now]), A[i + 1].dis(A[now])));
}
return ans;
}FFT
多项式相乘
#include <bits/stdc++.h>
using namespace std;
#define Maxn 1350000
const double Pi=acos(-1);
inline int read()
{
register char ch=0;
while(ch<48||ch>57)ch=getchar();
return ch-'0';
}
int n,m;
struct CP
{
CP (double xx=0,double yy=0){x=xx,y=yy;}
double x,y;
CP operator + (CP const &B) const
{return CP(x+B.x,y+B.y);}
CP operator - (CP const &B) const
{return CP(x-B.x,y-B.y);}
CP operator * (CP const &B) const
{return CP(x*B.x-y*B.y,x*B.y+y*B.x);}
}f[Maxn<<1];//只用了一个复数数组
int tr[Maxn<<1];
void fft(CP *f,bool flag)
{
for (int i=0;i<n;i++)
if (i<tr[i])swap(f[i],f[tr[i]]);
for(int p=2;p<=n;p<<=1){
int len=p>>1;
CP tG(cos(2*Pi/p),sin(2*Pi/p));
if(!flag)tG.y*=-1;
for(int k=0;k<n;k+=p){
CP buf(1,0);
for(int l=k;l<k+len;l++){
CP tt=buf*f[len+l];
f[len+l]=f[l]-tt;
f[l]=f[l]+tt;
buf=buf*tG;
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=0;i<=n;i++)f[i].x=read();
for (int i=0;i<=m;i++)f[i].y=read();
for(m+=n,n=1;n<=m;n<<=1);
for(int i=0;i<n;i++)
tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
fft(f,1);
for(int i=0;i<n;++i)f[i]=f[i]*f[i];
fft(f,0);
for(int i=0;i<=m;++i)
printf("%d ",(int)(f[i].y/n/2+0.49));
return 0;
}大数相乘
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6;
const double PI = acos(-1);
int n, m;
int res, ans[N];
int AA, BB;
int Lim = 1;//
int L;//二进制的位数
int R[N];
inline int read()
{
register int x = 0, f = 1;
register char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-')f = -1;ch =getchar();}
while(ch >= '0' && ch <= '9') {x = x * 1- + ch - '0';ch = getchar();}
return x * f;
}
struct Complex
{
double x, y;
Complex (double x = 0, double y = 0) : x(x), y(y) { }
}A[N], B[N];
Complex operator * (Complex J, Complex Q) {
//模长相乘，幅度相加
return Complex(J.x * Q.x - J.y * Q.y, J.x * Q.y + J.y * Q.x);
}
Complex operator - (Complex J, Complex Q) {
return Complex(J.x - Q.x, J.y - Q.y);
}
Complex operator + (Complex J, Complex Q) {
return Complex(J.x + Q.x, J.y + Q.y);
}
string s1, s2;
inline void FFT(Complex *J, double type)
{
for(int i = 0; i < Lim; ++ i) {
if(i < R[i]) swap(J[i], J[R[i]]);
//i小于R[i]时才交换，防止同一个元素交换两次，回到它原来的位置。
}
//从底层往上合并
for(int mid = 1; mid < Lim; mid <<= 1) {//待合并区间长度的一半，最开始是两个长度为1的序列合并,mid = 1;
Complex wn(cos(PI / mid), type * sin(PI / mid));//单位根w_n^i;
for(int len = mid << 1, pos = 0; pos < Lim; pos += len) {
//for(int pos = 0; pos < Lim; pos += (mid << 1)) {
//len是区间的长度，pos是当前的位置,也就是合并到了哪一位
Complex w(1, 0);//幂,一直乘，得到平方，三次方...
for(int k = 0; k < mid; ++ k, w = w * wn) {
//只扫左半部分，得到右半部分的答案,w 为 w_n^k
Complex x = J[pos + k];//左半部分
Complex y = w * J[pos + mid + k];//右半部分
J[pos + k] = x + y;//蝴蝶变换
J[pos + mid + k] = x - y;
}
}
}
}
int cnt_a, cnt_b;
int main()
{
cin >> s1 >> s2;
n = s1.length();
m = s2.length();
//相当于x=10 的多项式
//读入的数的每一位看成多项式的一项，保存在复数的实部
for (int i = n - 1; i >= 0; -- i) A[cnt_a ++ ].x = s1[i] - 48;
for (int i = m - 1; i >= 0; -- i) B[cnt_b ++ ].x = s2[i] - 48;
while(Lim < n + m) Lim <<= 1, L ++ ;
//Lim = 1 << int(log2(n + m) + 1); // 补成2的整次幂，这里补成了2的整次幂，所以最后输出答案的时候要除以Lim
for (int i = 0; i <= Lim; ++ i) {
//换成二进制序列
R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1));
// 在原序列中 i 与 i/2 的关系是 ： i可以看做是i/2的二进制上的每一位左移一位得来
// 那么在反转后的数组中就需要右移一位，同时特殊处理一下奇数
}
//FFT 把a的系数表示转化为点值表示
FFT(A, 1);
//FFT 把b的系数表示转化为点值表示
FFT(B, 1);
for (int i = 0; i <= Lim; ++ i)
//对应项相乘，O(n)得到点值表示的多项式的解C，利用逆变换完成插值得到答案C的点值表示
A[i] = A[i] * B[i];
//IFFT 把这个点值表示转化为系数表示
FFT(A, -1);
int tot = 0;
//保存答案的每一位（注意进位）
for (int i = 0; i <= Lim; ++ i) {
//取实数四舍五入，此时虚数部分应当为0或由于浮点误差接近0
ans[i] += (int) (A[i].x / Lim + 0.5);
if(ans[i] >= 10) {
ans[i + 1] += ans[i] / 10;
ans[i] %= 10;
Lim += (i == Lim);//进一位
}
}
//删掉前导零
while(!ans[Lim] && Lim >= 1) Lim -- ;
Lim ++ ;
//输出
while(-- Lim >= 0) cout << ans[Lim];
puts("");
return 0;
}字符串
KMP
#include <bits/stdc++.h>
const int maxn = 1e5;
using namespace std;
int ne[maxn];
char pattern[maxn],text[maxn];
void GetNext(char p[],int nex[],int n)
{
nex[0] = -1;
int k = -1;
int j = 0;
while (j < n - 1)
{
//p[k]表示前缀，p[j]表示后缀
if (k == -1 || p[j] == p[k])
{
++k;
++j;
nex[j] = k;
}
else
{
k = nex[k];
}
}
}
int KmpSearch(int m,int n)
{
GetNext(pattern,ne,n);
int pLen = n;
int sLen = m;
int i = 0;
int j = 0;
while(i<sLen){
if(j==n-1&&text[i]==pattern[j]){
printf("found the number %d\n",i-j);
}
if(text[i]==pattern[j]){
i++;
j++;
}
else{
j = ne[j];
if(j==-1){
i++;
j++;
}
}
}
}
int main(){
char t[] = "qwqwqwABABCABAAqABABCABAA";
char p[]= "ABABCABAA";
for(int i=0;i<100;i++){
pattern[i] = p[i];
text[i] = t[i];
}
KmpSearch(40,9);
return 0;
}最长回文子串
#include<cstdio>
#include<string.h>
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
char STR[1000];
int change(char *str, int i, int j) {
// (1)i == st, j == st;
// (2) i == st, j == st + 1;
int len = strlen(str);
while(str[i] == str[j] && i >= 0 && j < len) {
i --;
j ++;
}
return j - i -1;
}
int main()
{
int len, t;
scanf("%d", &t);
while(t--) {
scanf("%s", STR);
len = strlen(STR);
if(len == 0 ) {
printf("0\n");
return 0;
}
int maxLen = 1;
for(int st = 0; st < len - 1; st ++) {
int len1 = change(STR, st, st + 1);
int len2 = change(STR, st, st);
maxLen = max(maxLen, max(len1, len2));
}
printf("%d\n",maxLen);
}
}