程序对拍
所谓“对拍”，顾名思义，就是让两者相互比对。所谓“两者”，一是你要测试的程序，二是一个答案在该程序在一定范围（时间/空间）内结果必定正确的程序（一般是用暴力求解的程序）。对拍一般需要造数据程序（data.exe），保证正确性的暴力对拍程序（test.exe）与测试程序（以moo.exe为例）。下面是对拍的代码，写在txt中再转成.bat即可。
:loop
data.exe
test.exe
moo.exe
fc moo.out test.out
if %errorlevel% ==0goto loop
pause
图论算法
1、图的遍历-BFS
#include<iostream>
#include <queue>
#define N 5
using namespace std;
int maze[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 1, 0 },
{ 0, 1, 1, 1, 0 },
{ 1, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 0 }
};
int visited[N + 1] = {0, };
void BFS(int start)
{
queue<int> Q;
Q.push(start);
visited[start] = 1;
while (!Q.empty())
{
int front = Q.front();
cout << front << "";
Q.pop();
for (int i = 1; i <= N; i++)
{
if (!visited[i] &&maze[front - 1][i - 1] == 1)
{
visited[i] = 1;
Q.push(i);
}
}
}
}
int main()
{
for (int i = 1; i <= N; i++)
{
if (visited[i] == 1)
continue;
BFS(i);
}
return 0;
}
2、图的遍历-DFS
#include<iostream>
#include <stack>
#define N 5
using namespace std;
int maze[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 0 },
{ 1, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 0 }
};
int visited[N + 1] = {0, };
void DFS(int start)
{
stack<int> s;
s.push(start);
visited[start] = 1;
bool is_push = false;
while (!s.empty())
{
is_push = false;
int v = s.top();
for (int i = 1; i <= N; i++)
{
if (maze[v - 1][i - 1] == 1&& !visited[i])
{
visited[i] = 1;
s.push(i);
is_push = true;
break;
}
}
if (!is_push)
{
cout << v << " ";
s.pop();
}
}
}
int main()
{
for (int i = 1; i <= N; i++)
{
if (visited[i] == 1)
continue;
DFS(i);
}
return 0;
}
3、最小生成树-Kruskal
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN = 30;
int pa[MAXN];
int rank[MAXN];
int n,sum;
struct node{
int x,y;
int w;
}edge[MAXN*MAXN];
bool cmp(node p,node q){
return p.w<q.w;
}
void make_set(int x)
{
pa[x] = x;
rank[x] = 0;
}
int find_set(int x)
{
if(x != pa[x])
pa[x] = find_set(pa[x]);
return pa[x];
}
void union_set(int x, int y,int w)
{
x = find_set(x);
y = find_set(y);
if(x == y)return ;
if(rank[x] > rank[y])
{
pa[y] = x;
}
else
{
pa[x] = y;
if(rank[x] == rank[y])
rank[y]++;
}
sum+=w;
}
int main()
{
// freopen("input.txt","r",stdin);
while(cin>>n){
if(!n) break;
char ch;
int m,k=0;
for (int i = 0; i < n - 1; i++)
{
cin >> ch >> m;
for (int j = 0; j < m; j++)
{
cin >> ch >> edge[k].w;
edge[k].x = i;
edge[k].y = ch - 'A';
k++;
}
}
sort(edge,edge+k,cmp);
for(int i=0;i<MAXN;i++)
make_set(i);
sum=0;
for(int i=0;i<k;i++)
union_set(edge[i].x,edge[i].y,edge[i].w);
cout<<sum<<endl;
}
}
4、最小生成树-Prim
#include<cstdio>
using namespace std;
const int maxn=30;
const int INF=1000000;
int graph[maxn][maxn];
int lowcost[maxn],closet[maxn];
int visited[maxn];
int n;
void createGraph(){
memset(graph,0,sizeof(graph));
memset(lowcost,0,sizeof(lowcost));
memset(closet,0,sizeof(closet));
memset(visited,0,sizeof(visited));
int a;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
scanf("%d",&a);
if(a==0)
graph[i][j]=graph[j][i]=INF;
else
graph[i][j]=graph[j][i]=a;
}
}
void prim(){
int sum=0;
visited[0]=1;
for(int i=0;i<n;i++){
lowcost[i]=graph[i][0];
closet[i]=0;
}
for(int i=1;i<n;i++){
int minn=lowcost[0],k=0;
for(int j=0;j<n;j++){
if(!visited[j] && lowcost[j]<minn){
minn=lowcost[j];
k=j;
}
}
sum+=minn;
visited[k]=1;
for(int t=0;t<n;t++){
if(!visited[t] && lowcost[t]>graph[t][k]){
lowcost[t]=graph[t][k];
closet[t]=k;
}
}
}
printf("%d\n",sum);
}
int main()
{
// freopen("input.txt","r",stdin);
while(~scanf("%d",&n)){
if(!n) break;
createGraph();
prim();
}
}
5、最短路径-SPFA
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;
const int maxn=100005;
struct dqs
{
int f,t,c;
}hh[maxn];
int tot=0,first[maxn],next[maxn],d[maxn];
bool used[maxn];
void build(int f,intt,int c)
{
hh[++tot]=(dqs){f,t,c};
next[tot]=first[f];
first[f]=tot;
}
queue<int>q;
int n,m,s,e;
void spfa(int s)
{
d[s]=0;
q.push(s);
used[s]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
used[x]=0;
for(int i=first[x];i;i=next[i])
{
int u=hh[i].t;
if(d[u]>d[x]+hh[i].c)
{
d[u]=d[x]+hh[i].c;
if(!used[u])
{
q.push(u);
used[u]=1;
}
}
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&e);
for(int i=1;i<=n;i++)
d[i]=1e9;
for(int i=1;i<=m;i++)
{
int f,t,c;
scanf("%d%d%d",&f,&t,&c);
build(f,t,c);
build(t,f,c);
}
spfa(s);
printf("%d\n",d[e]);
return 0;
}
6、最短路径-Dijkstra
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=100005;
struct dqs
{
int f,t,c;
}hh[maxn];
int tot=0,first[maxn],next[maxn],d[maxn];
bool used[maxn];
void build(int f,intt,int c)
{
hh[++tot]=(dqs){f,t,c};
next[tot]=first[f];
first[f]=tot;
}
int n,m,s,e;
void Dijkstra()
{
for(int i=1;i<=n;i++)
d[i]=1e9;
d[s]=0;
while(true)
{
int x=-1;
for(int i=1;i<=n;i++)
{
if(!used[i])
if(x==-1||d[i]<d[x])
x=i;
if(x==-1) break;
used[x]=1;
for(int i=first[x];i;i=next[i])
{
int u=hh[i].t;
if(d[u]>d[x]+hh[i].c)
d[u]=d[x]+hh[i].c;
}
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&e);
......
}
7、最短路径-Floyd
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=1005;
int d[maxn][maxn];
int n,m,s,e;
void floyd()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j&&i!=k&&k!=j)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&e);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=1e9;
for(int i=1;i<=m;i++)
{
int f,t,c;
scanf("%d%d%d",&f,&t,&c);
d[f][t]=c;
d[t][f]=c;
}
floyd();
printf("%d\n",d[s][e]);
return 0;
}
8、最近公共祖先（LCA）-倍增
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=250010;
struct dqs
{
int f,t,c;
}hh[maxn<<1];
int tot=0,fa[maxn][31],next[maxn],first[maxn],f[maxn],d[maxn];
void build(int ff,inttt,int cc)
{
hh[++tot]=(dqs){ff,tt,cc};
next[tot]=first[ff];
first[ff]=tot;
}
int deep[maxn];
void dfs(int x,int sd)
{
deep[x]=sd;
int u;
for(int i=first[x];i;i=next[i])
{
u=hh[i].t;
if(!deep[u]&&u)
{
f[u]=x;
d[u]=d[x]+hh[i].c;
dfs(u,sd+1);
}
}
}
int lca(int x,int y)
{
if(deep[x]<deep[y])
swap(x,y);
int deepcha=deep[x]-deep[y];
for(int i=0;i<=30;i++)
{
if(1<<i&deepcha)
x=fa[x][i];
}
for(int i=30;i>=0;i--)
{
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
}
if(x!=y)
return f[x];
return x;
}
int main()
{
int n;
scanf("%d",&n);
int u,v,c;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&u,&v,&c);
build(u,v,c);
build(v,u,c);
}
dfs(0,0);
for(int i=0;i<n;i++)
fa[i][0]=f[i];
for(int j=1;j<=20;j++)
for(int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
int m;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
int xx=lca(u,v);
printf("%d\n",d[u]+d[v]-2*d[xx]);
}
return 0;
}
支付宝扫一扫
