最短路径（Floyd）
typedef struct
{
char vertex[VertexNum]; //顶点表
int edges[VertexNum][VertexNum]; //邻接矩阵,可看做边表
int n,e; //图中当前的顶点数和边数
}MGraph;
void Floyd(MGraph g)
{
int A[MAXV][MAXV];
int path[MAXV][MAXV];
int i,j,k,n=g.n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
A[i][j]=g.edges[i][j];
path[i][j]=-1;
}
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(A[i][j]>(A[i][k]+A[k][j]))
{
A[i][j]=A[i][k]+A[k][j];
path[i][j]=k;
}
}
}
最小生成树（Kruskal）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#define MAX_N 510
using namespace std;
int f[MAX_N] = {0}, max_e;//用于搜索父节点
int t, n, e = 0;//e记录边数
int map[MAX_N][MAX_N];
struct Edge {
int i;
int j;
int l;//length
} edge[MAX_N * MAX_N];
bool cmp(Edge a, Edge b) {
return a.l < b.l;
}
int findf(int x) {//得到父节点
return x == f[x] ? x : findf(f[x]);
}
int Kruskal()
{
for (int i = 1; i <= n; ++i)//初始化父亲指针,一开始每个点的父亲都是自己
f[i] = i;
for (int i = 0; i < e; ++i)
{
int x = findf(edge[i].i);
int y = findf(edge[i].j);
if (x != y)
{
//if (edge[i].l > max_e)
max_e += edge[i].l;
f[x] = y;//合并两颗树，只需把y当做x的父亲就可以了
}
}
return max_e;
}
int main() {
while (scanf("%d", &n)!=EOF) {
max_e = 0;
e = 0;
memset(f,0,sizeof(f));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &edge[e].l);
if (i < j) {
edge[e].i = i;
edge[e].j = j;
e++;
}
}
}
sort(edge,edge+e,cmp);//排序所有读入的边 从小到大
cout << Kruskal() << endl;
}
return 0;
}
DFS n皇后
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n;
int ans=0;
bool a[20];
bool x1[20];
bool y1[20];
void dfs(int x)
{
if (x>n)
{
ans++;
return;
}
for (int i=1;i<=n;i++)
{
if (x1[i+x]==false&&y1[i-x+n]==false&&a[i]==false)
{
x1[x+i]=true;
y1[i-x+n]=true;
a[i]=true;
dfs(x+1);
a[i]=false;
x1[x+i]=false;
y1[i-x+n]=false;
}
}
}
int main()
{
scanf ("%d",&n);
memset(a,false,sizeof(a));
memset(x1,false,sizeof(x1));
memset(y1,false,sizeof(y1));
dfs(1);
printf ("%d",ans);
return 0;
}
BFS迷宫最短路径
# include<stdio.h>
# include<stdlib.h>
int map[5][5];
int dir[4][2]={1,0,-1,0,0,1,0,-1}; //可走的四个方向
struct node{
int x,y;
};
struct node queue[50],record[5][5];//queue记录可走的点，广搜；record记录改点的前驱
void bfs()
{
int head,tail,i;
struct node cur,next;//cur为当前位置，next为下一个位置
head=tail=0;
cur.x=queue[tail].x;
cur.y=queue[tail].y;
tail++;
while(head<tail)
{
cur=queue[head++];
for(i=0;i<4;i++)
{
next.x=cur.x+dir[i][0];
next.y=cur.y+dir[i][1];
if(next.x>=0&&next.y>=0&&next.x<5&&next.y<5&&map[next.x][next.y]==0)
{
record[next.x][next.y].x=cur.x;
record[next.x][next.y].y=cur.y;//记录next的前驱，即next的坐标（因为next记录的是第一个到达该地点的前驱，随后被标记走过，故不用担心被后来的前驱坐标所覆盖）
if(next.x==4&&next.y==4)
return ;
else
{
map[next.x][next.y]=1;//标记走过
queue[tail++]=next;
}
}
}
}
}
int main()
{
int i,j,k,m,n;
struct node cur;
for(i=0;i<5;i++)
for(j=0;j<5;j++)
scanf("%d",&map[i][j]);
cur.x=0;
cur.y=0;
map[0][0]=1;
queue[0]=cur;
bfs();
k=0;
queue[k].x=4;
queue[k++].y=4;
i=j=4;
while(i!=0||j!=0)//根据record的记录，从后往前回溯其路径，并存在queue中
{
m=i;n=j;
i=record[m][n].x;
j=record[m][n].y;
queue[k].x=i;
queue[k++].y=j;
}
for(i=k-1;i>=0;i--)//输出路径
printf("(%d, %d)\n",queue[i].x,queue[i].y);
return 0;
}
背包问题
#include<iostream>
#include<algorithm>
using namespace std;
struct node {
int w, d;
} p[4000];
int main() {
int n, m;
int dp[12881] = {0};
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> p[i].w >> p[i].d;
for (int i = 0; i < n; i++) {
for (int j = m; j >= p[i].w; j--) {
dp[j] = max(dp[j], dp[j - p[i].w] + p[i].d);
}
}
cout << dp[m] << endl;
return 0;
}
最长上升子序列
#include <stdio.h>
const int M = 40005;
int stack[M];
int binarysearch(int l,int r,int k)
{
while (l < r){
int m = l + (r - l)/2;
if (stack[m] >= k) r = m;
else l = m + 1;
}
return l;
}
int main ()
{
int T,n,i,top,num;
scanf ("%d",&T);
while (T --)
{
top = 0;
stack[0] = -1;
scanf ("%d",&n);
for (i = 1;i <= n;i ++)
{
scanf ("%d",&num);
if (num > stack[top])
stack[++top] = num;
else {
int pos = binarysearch(1,top,num);
stack[pos] = num;
}
}
printf ("%d\n",top);
}
return 0;
}
最长公共子序列
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
#define N 10000
int dp[N+1][N+1];
char str1[N],str2[N];
int maxx(int a,int b)
{
if(a>b)
return a;
return b;
}
int LCSL(int len1,int len2)
{
int i,j;
int len=maxx(len1,len2);
for(i=0; i<=len; i++)
{
dp[i][0]=0;
dp[0][i]=0;
}
for(i=1; i<=len1; i++)
for(j=1; j<=len2; j++)
{
if(str1[i-1]==str2[j-1])
{
dp[i][j]=dp[i-1][j-1]+1;
}
else
{
dp[i][j]=maxx(dp[i-1][j],dp[i][j-1]);
}
}
return dp[len1][len2];
}
int main()
{
while(scanf("%s",str1)!=EOF)
{
cin>>str2;
int len1=strlen(str1);
int len2=strlen(str2);
cout<<LCSL(len1,len2)<<endl;
}
return 0;
}
归并排序
#include<iostream>
using namespace std;
#define MAXSIZE 10
//将两个有序数列a[first...mid] 和 a[mid...last] 合并。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; ++i)
a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //左边有序
mergesort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将两个有序数列合并
}
}
bool MergeSort(int a[], int n)
{
int *p = new int[n];
if (p == NULL)
return false;
mergesort(a, 0, n - 1, p);
delete[] p;
return true;
}
void PrintArr(int ar[],int n)
{
for(int i = 0; i < n; ++i)
cout<<ar[i]<<" ";
cout<<endl;
}
int main()
{
int ar[MAXSIZE] = {23, 34, 45, 78, 90, 12, 49, 92, 32, 19};
PrintArr(ar, MAXSIZE);
bool bValue = MergeSort(ar, MAXSIZE);
if(!bValue)
{
cout<<"MergeSort Failed!! "<<endl;
}
PrintArr(ar, MAXSIZE);
return 0;
}
并查集
#include<iostream>
using namespace std;
int pre[1050];
bool t[1050]; //t 用于标记独立块的根结点
int Find(int x)
{
int r=x;
while(r!=pre[r])
r=pre[r];
int i=x,j;
while(pre[i]!=r)
{
j=pre[i];
pre[i]=r;
i=j;
}
return r;
}
void mix(int x,int y)
{
int fx=Find(x),fy=Find(y);
if(fx!=fy)
{
pre[fy]=fx;
}
}
int main()
{
int N,M,a,b,i,j,ans;
while(scanf("%d%d",&N,&M)&&N)
{
for(i=1; i<=N; i++) //初始化
pre[i]=i;
for(i=1; i<=M; i++) //吸收并整理数据
{
scanf("%d%d",&a,&b);
mix(a,b);
}
memset(t,0,sizeof(t));
for(i=1; i<=N; i++) //标记根结点
{
t[Find(i)]=1;
}
for(ans=0,i=1; i<=N; i++)
if(t[i])
ans++;
printf("%d\n",ans-1);
}
return 0;
}//dellaserss
二分图查找（匈牙利算法）
#include<iostream>
#include<cstring>
using namespace std;
int n,k; //n矩阵规格，k星体数量
int V1,V2; //二分图顶点集
/*矩阵的行列分别属于二分图的两个顶点集V1、V2，其中行x∈V1，列y∈V2*/
bool grid[501][501]; //存储数据方式：可达矩阵
bool vis[501]; //记录V2的点每个点是否已被搜索过
int link[501]; //记录 V2中的点y 在 V1中 所匹配的点x的编号
int m; //最大匹配数
/*Hungary Algorithm*/
bool dfs(int x)
{
for(int y=1; y<=V2; y++)
if(grid[x][y] && !vis[y]) //x到y相邻(有边) 且 节点y未被搜索
{
vis[y]=true; //标记节点y已被搜索
if(link[y]==0 || dfs(link[y])) //link[y]==0 : 如果y不属于前一个匹配M
{
//find(link[y] : 如果被y匹配到的节点可以寻找到增广路
link[y]=x; //那么可以更新匹配M'(用M替代M')
return true; //返回匹配成功的标志
}
}
return false; //继续查找V1下一个x的邻接节点
}
void search(void)
{
for(int x=1; x<=V1; x++)
{
memset(vis,false,sizeof(vis)); //清空上次搜索时的标记
if(dfs(x)) //从V1中的节点x开始寻找增广路
m++;
}
return;
}
int main(void)
{
cin>>n>>k;
V1=V2=n;
int x,y; //坐标(临时变量)
for(int i=1; i<=k; i++)
{
cin>>x>>y;
grid[x][y]=true; //相邻节点标记
}
/*增广轨搜索*/
search();
/*Output*/
cout<<m<<endl;
return 0;
}
Java大数
import java.math.BigDecimal;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
BigDecimal R = in.nextBigDecimal();
int n = in.nextInt();
R = R.pow(n);
String str = R.stripTrailingZeros().toPlainString();
if (str.startsWith("0."))
str = str.substring(1);
System.out.println(str);
}
}
}