ACM

2020-03-02 19:08:40 来源：范文大全收藏下载本文

Dijkstra 模板

/*************************************** * About:

有向图的Dijkstra算法实现 * Author:

Tanky Woo * Blog:

www.daodoc.com ***************************************/

#include using namespace std;

const int maxnum = 100; const int maxint = 999999;

// 各数组都从下标1开始

int dist[maxnum];

// 表示当前点到源点的最短路径长度

int prev[maxnum];

// 记录当前点的前一个结点, 用于需要输出最短路径的路径是使用 int c[maxnum][maxnum];

// 记录图的两点间路径长度，用于记录当前的图 int n, line;

// 图的结点数和路径数

void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum]) {

bool s[maxnum];

// 判断是否已存入该点到S集合中

for(int i=1; i

{

dist[i] = c[v][i];

s[i] = 0;

// 初始都未用过该点

if(dist[i] == maxint)

prev[i] = 0;

else

prev[i] = v;

}

dist[v] = 0;

s[v] = 1;

// 依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中

// 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度

for(int i=2; i

{

int tmp = maxint;

int u = v;

//使用u=v 是为了防止出现有多个连通分量的问题。当需要到达的点无法到达时，该点的dist[x]值必为maxint

// 找出当前未使用的点j的dist[j]最小值

for(int j=1; j

if((!s[j]) && dist[j]

{

u = j;

// u保存当前邻接点中距离最小的点的号码

tmp = dist[j];

}

s[u] = 1;

// 表示u点已存入S集合中

// 更新dist for(int j=1; j

if((!s[j]) && c[u][j]

{

//加上目前到达的点到他邻接的点的距离和其他到达该点的路径长度

int newdist = dist[u] + c[u][j];

if(newdist

{

dist[j] = newdist;

prev[j] = u;

}

} }

void searchPath(int *prev,int v, int u) //用于返回具体的路径 {

int que[maxnum];

int tot = 1;

que[tot] = u;

tot++;

int tmp = prev[u];

while(tmp != v)

{

que[tot] = tmp;

tot++;

tmp = prev[tmp];

}

que[tot] = v;

for(int i=tot; i>=1; --i)

if(i != 1)

cout \";

else

cout

int main() {

freopen(\"input.txt\", \"r\", stdin);

// 各数组都从下标1开始

// 输入结点数

cin >> n;

// 输入路径数

cin >> line;

int p, q, len;

// 输入p, q两点及其路径长度

// 初始化c[][]为maxint

for(int i=1; i

for(int j=1; j

c[i][j] = maxint;

for(int i=1; i

{

cin >> p >> q >> len;

if(len

// 有重边 {

c[p][q] = len;

// p指向q

c[q][p] = len;

// q指向p，这样表示无向图

} }

for(int i=1; i

printf(\"%8d\", c[i][j]); printf(\"\\n\"); }

Dijkstra(n, 1, dist, prev, c);

// 最短路径长度

cout

// 路径

cout

例题：

最少换乘

时间限制：2000 ms | 内存限制：65535 KB

欧洲某城是一个著名的旅游胜地，每年都有成千上万的人前来观光旅行。Dr.Kong决定利用暑假好好游览一番。。

年轻人旅游不怕辛苦，不怕劳累，只要费用低就行。但Dr.Kong年过半百，他希望乘坐BUS从住的宾馆到想去游览的景点，期间尽可量地少换乘车。

Dr.Kon买了一张旅游地图。他发现，市政部门为了方便游客，在各个旅游景点及宾馆，饭店等地方都设置了一些公交站并开通了一些单程线路。每条单程线路从某个公交站出发，依次途经若干个站，最终到达终点站。

但遗憾的是，从他住的宾馆所在站出发，有的景点可以直达，有的景点不能直达，则他可能要先乘某路BUS坐上几站，再下来换乘同一站的另一路BUS, 这样须经过几次换乘后才能到达要去的景点。

为了方便，假设对该城的所有公交站用1，2，……，N编号。Dr.Kong所在位置的编号为1，他将要去的景点编号为N。

请你帮助Dr.Kong寻找一个最优乘车方案,从住处到景点，中间换车的次数最少。

输入第一行： K 表示有多少组测试数据。（2≤k≤8）

接下来对每组测试数据：

第1行: M N 表示有M条单程公交线路，共有N站。（1

第2~M+1行：每行描述一路公交线路信息，从左至右按运行顺序依次给出了该线路上的所有站号，相邻两个站号之间用一个空格隔开。

输出对于每组测试数据，输出一行，如果无法乘坐任何线路从住处到达景点，则输出\"N0\"，否则输出最少换车次数，输出0表示不需换车可以直达。样例输入

2 3 7 6 7 4 7 3 6 2 1 3 5 2 6 1 3 5 2 6 4 3

样例输出

2 NO

#include #include #include using namespace std; int arr[505][505]; int temp[505];

void disj(int m,int n){ //dis用来计算最小换乘的次数，多少条线路

int i, j, index=0, flag; int temp[505]; int known[505]; memset(temp, 0, sizeof(temp)); memset(known, 0, sizeof(known));

for(i=1; i

if(arr[1][i] == 1)

temp[i] = arr[1][i];

else if(arr[1][i] == 0)

temp[i] = 1E30; }

n表示公交车站点的数目 m表示有 known[1] = 1;

for(i=2; i

flag = 1E30;

for(j=1; j

if(!known[j] && temp[j]

flag = temp[j];

index = j;

}

known[index] = 1;

for(j=1; j

if(!known[j] && temp[j]>temp[index]+1 && arr[index][j])

temp[j] = temp[index]+1;

} } int x = 1E30; if(temp[n]!=x)

printf(\"%d\\n\",temp[n]-1); else

printf(\"NO\\n\");

}

int main(){ int t; cin>>t; while(t--){

int i, j, k, l;

char [2000];

int m, n;

cin>>m>>n;

getchar();

memset(arr,0,sizeof(arr));

for(i=1; i

gets();

int len = strlen();

l=0;

for(j=0; j

int sum=0;

for(k=j; [k]!=\' \'&& [k]!=\'\\0\';){

sum = sum*10 + [k]-\'0\';

}

k++;

j++;

}

j+=1;

temp[++l]=sum;

}

for(j=1; j

for(k=j+1; k

arr[temp[j]][temp[k]] = 1;

}

} } /* cout

Sample Input 5 1 5 3 3 1 2 5 0

Sample Output 3

Recommend 8600

#include using namespace std; #define INF 999999 int map[500][500]; int dist[500],used[500]; int n; void Dijkstra(int v) {

int i,j,pos,min;

memset(used,0,sizeof(used));

for(i=1;i

dist[i]=map[v][i];

used[v]=1;

dist[v]=0;//floor A==floor B(起点就是终点)的情况

for(j=1;j

{

pos=0;

min=100000000;

for(i=1;i

if(dist[i]

{

pos=i;

min=dist[i];

}

used[pos]=1;

for(i=1;i

if(dist[i]>dist[pos]+map[pos][i])

dist[i]=dist[pos]+map[pos][i];

} }

int main() {

int s,t,i,j;

int a[500];

while(cin>>n,n)

{

cin>>s>>t;

memset(map,INF,sizeof(map));

for(i=1;i

{

cin>>a[i];

if(i+a[i]

map[i][i+a[i]]=1;//构图必须是单向边

if(i-a[i]>=1)

map[i][i-a[i]]=1;

}

Dijkstra(s);

if(dist[t]>INF)//If you can\'t reach floor B,printf \"-1\"

cout

else

cout

}

return 0; }

昂贵的聘礼

年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求。酋长说：\"嗯，如果你能够替我弄到大祭司的皮袄，我可以只要8000金币。如果你能够弄来他的水晶球，那么只要5000金币就行了。\"探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他的东西，他可以降低价格。探险家于是又跑到其他地方，其他人也提出了类似的要求，或者直接用金币换，或者找到其他东西就可以降低价格。不过探险家没必要用多样东西去换一样东西，因为不会得到更低的价格。探险家现在很需要你的帮忙，让他用最少的金币娶到自己的心上人。另外他要告诉你的是，在这个部落里，等级观念十分森严。地位差距超过一定限制的两个人之间不会进行任何形式的直接接触，包括交易。他是一个外来人，所以可以不受这些限制。但是如果他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。因此你需要在考虑所有的情况以后给他提供一个最好的方案。为了方便起见，我们把所有的物品从1开始进行编号，酋长的允诺也看作一个物品，并且编号总是1。每个物品都有对应的价格P，主人的地位等级L，以及一系列的替代品Ti和该替代品所对应的\"优惠\"Vi。如果两人地位等级差距超过了M，就不能\"间接交易\"。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。

Input 输入第一行是两个整数M，N（1 using namespace std; const int INF=100000; int a[105][105],b[105],c[105],s[105],dist[105]; int n,m; int dj(int p,int q) { int i,j,r,t,k=0; for(i=0;i=p&&b[i]

t=INF;

for(j=0;j

if(!s[j]&&dist[j]

s[k]=1;

for(j=0;j

if(!s[j]&&a[k][j]=p&&b[j]

{

r=dist[k]+a[k][j];

if(dist[j]>r) dist[j]=r;

} } t=c[0]; for(i=0;i

if(dist[i]+c[i]

return t; } int main(int argc, char *argv[]) { int i,j,k,p,q,l,r; while(cin>>m>>n&&(m||n)) {

for(i=0;i

for(j=0;j

a[i][j]=INF; for(i=0;i

cin>>c[i]>>b[i]>>k;

for(j=0;j

{

cin>>p>>q;

a[i][p-1]=q;

} } r=c[0];

for(i=b[0]-m;i

{

k=dj(i,i+m);

if(k

}

cout

prim算法模板 + 思路

Prim:利用dis[]来记录已选点集中到各点的最短距离，一开始用起始点到各点的距离初始化dis[]

while->知道全部点都走到

for->找dis[]中最小边（保证不出现环，即不出现最小边所关联的两个定点都在已选点集中），添加长度，添加点进已选点集

for->利用刚添加进来的点到各点的距离，更新dis[]

#include #include #define MaxInt 0x3f3f3f3f #define N 110 //创建map二维数组储存图表，low数组记录每2个点间最小权值，visited数组标记某点是否已访问

int map[N][N],low[N],visited[N];

//low的含义就是 visited【i】为0的情况下

int n;

//选中点集的各个点到未选中点集的各个点的最短距离

int prim() {

int i,j,pos,min,result=0;

memset(visited,0,sizeof(visited)); //从某点开始，分别标记和记录该点

visited[1]=1;pos=1; //第一次给low数组赋值,

for(i=1;i

if(i!=pos) low[i]=map[pos][i]; }

//再运行n-1次 for(i=1;i

min=MaxInt; for(j=1;j

if(visited[j]==0&&min>low[j])

{

min=low[j];pos=j;

} }

//最小权值累加 result+=min; //标记该点 visited[pos]=1;

//更新权值

for(j=1;j

{

if(visited[j]==0&&low[j]>map[pos][j])

{

low[j]=map[pos][j];

}

} } return result; }

int main() {

int i,v,j,ans;

while(scanf(\"%d\",&n)!=EOF)

{

//所有权值初始化为最大

memset(map,MaxInt,sizeof(map));

for(i=1;i

for(j=1;j

{

scanf(\"%d\",&v);

map[i][j]=map[i][j]=v;

}

ans=prim();

printf(\"%d\\n\",ans);

}

return 0; }

畅通工程

#include #include #include #define INF 999999999 using namespace std;

int map[105][105],visit[105],dis[105],M;

int prim() { int i,j; for(i = 1;i

dis[i] = map[i][1]; } dis[1] = 0;

int sum = 0; for(i = 1; i

int temp = INF,pos;

for(j= 1; j

{

if(!visit[j] && temp > dis[j])

{

temp = dis[j];

pos = j;

}

if(temp == INF)

return 0;

visit[pos] = 1;

sum += dis[pos];

for(j = 1; j

{

if(!visit[j] && map[pos][j]

{

dis[j] = map[pos][j];

}

} } return sum; } int main() { int N; while(scanf(\"%d%d\",&N,&M),N) {

int u,v,w;

memset(map,0x3f,sizeof(map));

memset(dis,0x3f,sizeof(dis));

memset(visit,0,sizeof(visit));

for(int i = 1; i

{

scanf(\"%d%d%d\",&u,&v,&w);

map[u][v] = map[v][u] = w;

}

int ans = prim();

if(ans)

printf(\"%d\\n\",ans);

else

printf(\"?\\n\"); } return 0; }

Freckles 雀斑

In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad\'s back to form a picture of the Liberty Bell.Alas, one of the freckles turns out to be a scar, so his Ripley\'s engagement falls through.

Consider Dick\'s back to be a plane with freckles at various (x,y) locations.Your job is to tell Richie how to connect the dots so as to minimize the amount of ink used.Richie connects the dots by drawing straight lines between pairs, poibly lifting the pen between lines.When Richie is done there must be a sequence of connected lines from any freckle to any other freckle.

输入：

The first line contains 0

输出：

Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles.

样例输入： 3 1.0 1.0 2.0 2.0 2.0 4.0 样例输出： 3.41

#include #include #include #define max 1

p[i]=map[0][i]; vis[0]=1; for(i=1;i

min=max;

for(j=1;j

{

if(!vis[j]&&p[j]

{

min=p[j];

k=j;

}

sum+=min;

vis[k]=1;

for(j=1;j

{

if(!vis[j]&&map[k][j]

p[j]=map[k][j];

} } } int main() { int i,j; while(~scanf(\"%d\",&n)) {

memset(vis,0,sizeof(vis));

for(i=0;i

scanf(\"%lf%lf\",&e[i].x,&e[i].y);

for(i=0;i

{

for(j=0;j

map[i][j]=map[j][i]=sqrt((e[i].x-e[j].x)*(e[i].x-e[j].x)+(e[i].y-e[j].y)*(e[i].y-e[j].y));

}

prim();

printf(\"%.2lf\\n\",sum); } return 0; }

并查集

普通并查集：

带路径压缩的的findset函数： 1.while版本

2.递归版本

个人经验表明在递归版本不栈溢出的情况下，递归版本和循环版本的效率并没有太大差别，并且对于带路径压缩的并查集，基本上不会发生“递归栈溢出”。另外，union_nodes函数还可以可以采用启发式合并，思路就是把深度较小的那棵子树并到深度较大的那棵子树上，不过一般情况下路径压缩就够用了。听人说并查集还可以“离散化”，个人从字面上理解应该是指用map、hash来保存每个节点，从而当节点分布比较稀疏的时候，可以比普通并查集更快的完成初始化等工作（待商榷）。

代码：

小希的迷宫

上次Gardon的迷宫城堡小希玩了很久（见Problem B），现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。

Input 输入包含多组数据，每组数据是一个以0 0结尾的整数对列表，表示了一条通道连接的两个房间的编号。房间的编号至少为1，且不超过100000。每两组数据之间有一个空行。整个文件以两个-1结尾。

Output 对于输入的每一组数据，输出仅包括一行。如果该迷宫符合小希的思路，那么输出\"Yes\"，否则输出\"No\"。

Sample Input 6 8 5 3 5 2 6 4 5 6 0 0

8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0

3 8 6 8 6 4 5 3 5 6 5 2 0 0

-1 -1

Sample Output Yes Yes No

#include #include

int arr[100005];

int mark[100005];

int max(int a, int b){ if(a>b)

return a; else

return b; } int min(int a, int b){ if(a

return a; } else{

return b; } }

int find(int a){ while(arr[a]){

a = arr[a]; } return a; }

int union1(int a, int b){ a = find(a); b = find(b); int max1 = max(a, b); int min1 = min(a, b); if(a == b)

return 0; // 0代表有回路

arr[max1] = min1;

return 1; }

int check(){ int cur = 0; int i; for(i=1; i

if(mark[i] == 1 && arr[i] == 0){

cur++;

if(cur>1){

return 0;

}

} return 1; } int main(){ int x, y;

while(scanf(\"%d%d\",&x, &y) &&( x!=-1 && y!=-1)){

memset(arr,0,sizeof(arr));

memset(mark,0,sizeof(mark));

if(x==0 && y==0){

printf(\"Yes\\n\");

continue;

}

int max=-1;

int min=999999;

int flag = 1;

while(x || y){

mark[x]=1;

mark[y]=1;

if(x>max) max=x;

if(x

if(y>max) max=y;

if(y

if(!union1(x, y))

flag = 0;

scanf(\"%d%d\",&x,&y);

}

int cnt=0;

if(flag == 0){

printf(\"No\\n\");

}

else{

for(int i=min; i

if(mark[i]==1 && arr[i]==0)

cnt++;

}

if( cnt==1)

printf(\"Yes\\n\");

else

printf(\"No\\n\"); }

} return 0; 搜索算法模板

BFS：

1.#include 2.#include 3.#include 4.#include 5.using namespace std; 6.const int maxn=100; 7.bool vst[maxn][maxn]; // 访问标记

8.int dir[4][2]={0,1,0,-1,1,0,-1,0}; // 方向向量 9.

10.struct State // BFS 队列中的状态数据结构 11.{ 12.

int x,y; // 坐标位置

13.

int Step_Counter; // 搜索步数统计器 14.}; 15.

16.State a[maxn]; 17.

18.boolCheckState(State s) // 约束条件检验 19.{ 20. if(!vst[s.x][s.y] && ...) // 满足条件 1: 21. return 1; 22. else // 约束条件冲突 23. return 0; 24.} 25.

26.void bfs(State st) 27.{ 28. queue q; // BFS 队列

29. State now,next; // 定义2 个状态，当前和下一个 30. st.Step_Counter=0; // 计数器清零 31. q.push(st); // 入队

32. vst[st.x][st.y]=1; // 访问标记 33. while(!q.empty()) 34. { 35. now=q.front(); // 取队首元素进行扩展

36. if(now==G) // 出现目标态，此时为Step_Counter 的最小值，可以退出即可 37. { 38. ......// 做相关处理 39. return; 40. } 41. for(int i=0;i

57.int main() 58.{ 59.......60. return 0; 61.}

代码：

胜利大逃亡

Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会.

魔王住在一个城堡里,城堡是一个A*B*C的立方体,可以被表示成A个B*C的矩阵,刚开始Ignatius被关在(0,0,0)的位置,离开城堡的门在(A-1,B-1,C-1)的位置,现在知道魔王将在T分钟后回到城堡,Ignatius每分钟能从一个坐标走到相邻的六个坐标中的其中一个.现在给你城堡的地图,请你计算出Ignatius能否在魔王回来前离开城堡(只要走到出口就算离开城堡,如果走到出口的时候魔王刚好回来也算逃亡成功),如果可以请输出需要多少分钟才能离开,如果不能则输出-1.

Input 输入数据的第一行是一个正整数K,表明测试数据的数量.每组测试数据的第一行是四个正整数A,B,C和T(1

特别注意:本题的测试数据非常大,请使用scanf输入,我不能保证使用cin能不超时.在本OJ上请使用Visual C++提交.

Output 对于每组测试数据,如果Ignatius能够在魔王回来前离开城堡,那么请输出他最少需要多少分钟,否则输出-1.

Sample Input 1 3 3 4 20 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1 1 0

Sample Output 11

代码：

#include #include #include #include #include

using namespace std;

int tx[] = {0,1,-1,0,0,0,0};

int ty[] = {0,0,0,1,-1,0,0};

int tz[] = {0,0,0,0,0,1,-1};

int arr[55][55][55]; int known[55][55][55]; // 访问标记 int a,b,c,d; struct state{

int x,y,z;

// 所在的坐标

int step_count; //统计搜索步数。 };

int check(int x, int y, int z){

if(x>=1 && x=1 && y=1 && z

return 1;

return 0; } int bfs(int a, int b, int c){

queue q;

state temp, now;

temp.x=1;

temp.y=1;

temp.z=1;

// 对压入队列的state元素进行初始化

q.push(temp);

known[1][1][1] = 1; // 第一个元素已经访问;

while(!q.empty()){

now = q.front();

if(now.x == a && now.y == b && now.z == c && (known[a][b][c]-1)

return known[a][b][c]-1;

}

int fangxiang=1;

for(; fangxiang

temp = now;

temp.x += tx[fangxiang];

temp.y += ty[fangxiang];

temp.z += tz[fangxiang];

if(check(temp.x, temp.y, temp.z) && !known[temp.x][temp.y][temp.z]){

known[temp.x][temp.y][temp.z] = known[now.x][now.y][now.z]+1;

q.push(temp);

}

q.pop();

}

return -1; } int main(){

int t;

int i, j, k;

scanf(\"%d\",&t);

while(t--){

scanf(\"%d%d%d%d\",&a, &b, &c, &d);

memset(known,-1,sizeof(known));

memset(arr,-1,sizeof(arr));

for(i=1; i

for(j=1; j

for(k=1; k

arr[i][j][k]=0;

known[i][j][k]=0;

// 对访问标记进行初始化置为0， 1 代表已经访问过。

scanf(\"%d\",&arr[i][j][k]);

}

int cur = bfs(a, b, c);

printf(\"%d\\n\",cur);

}

return 0; }

超级密码

Problem Description Ignatius花了一个星期的时间终于找到了传说中的宝藏,宝藏被放在一个房间里,房间的门用密码锁起来了,在门旁边的墙上有一些关于密码的提示信息: 密码是一个C进制的数,并且只能由给定的M个数字构成,同时密码是一个给定十进制整数N(0

注意:由于宝藏的历史久远,当时的系统最多只能保存500位密码.因此如果得到的密码长度大于500也不能用来开启房门,这种情况也被认为密码不存在.

Input 输入数据的第一行是一个整数T(1

注意:在给出的M个数字中,如果存在超过10的数,我们约定用A来表示10,B来表示11,C来表示12,D来表示13,E来表示14,F来表示15.我保证输入数据都是合法的.

Output 对于每组测试数据,如果存在要求的密码,则输出该密码,如果密码不存在,则输出\"give me the bomb please\".

注意:构成密码的数字不一定全部都要用上;密码有可能非常长,不要试图用一个整型变量来保存密码;我保证密码最高位不为0(除非密码本身就是0).

Sample Input 3 22 10 3 7 0 1

2 10 1 1

25 16 3 A B C

Sample Output 110 give me the bomb please CCB

代码：

#include #include #include #include using namespace std;

int num[20],vis[5005]; int n,c,m;

struct node {

int s[505];//将每一位的字符压入此数组

int len; };

int print(node a)//输出函数 {

int i;

for(i = 0; i

{

if(a.s[i]

printf(\"%d\",a.s[i]);

else

printf(\"%c\",a.s[i]+\'A\'-10);

}

printf(\"\\n\"); }

int mod(node a)//由于数字大，采用这种大数取模方式 {

int i,tem = 0;

for(i = 0; i

{

tem = (tem*c+a.s[i])%n;//由于是n进制，tem在前面的基础上乘以进制数c在加上下一位，如果能整除n，那必定是n的倍数，则成立

}

return tem; }

int BFS() {

memset(vis,0,sizeof(vis));

node a;

queue Q;

a.len = 0;

int i,r;

for(i = 1; i

{

if(num[i])//这个数是给出的样例

{

a.s[0] = i;//压入数组

a.len = 1;//长度变化

r = mod(a);

if(!r)//模为0，则肯定是n的倍数，输出

{

print(a);

return 1;

}

else

{

if(!vis[r])//余数不能与之前出现过的余数相同，因为前面出现过的序列，肯定包含同样余数却在后面出现的序列

{

vis[r] = 1;//标记该余数已被访问

Q.push(a);

}

while(!Q.empty())

{

a = Q.front();

Q.pop();

for(i = 0; i

{

if(num[i])

{

a.s[a.len] = i;

a.len++;

r = mod(a);

if(!r)//一直找到能整除n的方案

{

print(a);

return 1;

}

else

{

if(!vis[r] && a.len

{

vis[r] = 1;

Q.push(a);

}

a.len--;//是不是觉得这里与a.len++这句话会无限重复，导致a.len一直为1？错了！要注意，在r与之前出现过的余数相同是，这次的a是没有压入队列的，也就是这次的a.len减少了，但是在队列中的a.len却没有减少！

}

return 0; }

int main() {

int t,i;

char str[2];

scanf(\"%d\",&t);

while(t--)

{

scanf(\"%d%d%d\",&n,&c,&m);

memset(num,0,sizeof(num));

for(i = 0; i

{

scanf(\"%s\",str);

if(str[0]>=\'0\' && str[0]

num[str[0]-\'0\'] = 1;

else

num[str[0]-\'A\'+10] = 1;

}

if(n)

{

int flag;

flag = BFS();

if(!flag)

printf(\"give me the bomb please\\n\");

}

else

{

if(num[0])

printf(\"0\\n\");

else

printf(\"give me the bomb please\\n\");

}

return 0; }

DFS:

1./* 2.该DFS 框架以2D 坐标范围为例，来体现DFS 算法的实现思想。 3.*/ 4.#include 5.#include 6.#include 7.using namespace std; 8.const int maxn=100; 9.bool vst[maxn][maxn]; // 访问标记 10.int map[maxn][maxn]; // 坐标范围

11.int dir[4][2]={0,1,0,-1,1,0,-1,0}; // 方向向量，(x,y)周围的四个方向 12.

13.bool CheckEdge(int x,int y) // 边界条件和约束条件的判断 14.{ 15. if(!vst[x][y] && ...) // 满足条件 16. return 1; 17. else // 与约束条件冲突 18. return 0; 19.} 20.

21.void dfs(int x,int y) 22.{ 23. vst[x][y]=1; // 标记该节点被访问过

24. if(map[x][y]==G) // 出现目标态G，最终的目标。 25. { 26. ......// 做相应处理 27. return; 28. } 29. for(int i=0;i

Prime Ring Problem Problem Description A ring is compose of n circles as shown in diagram.Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

Input n (0

You are to write a program that completes above proce.

Print a blank line after each case.

Sample Input 6 8

Sample Output Case 1: 1 4 3 2 5 6 1 6 5 2 3 4 Case 2: 1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2

#include #include #include #include using namespace std;

int str[25]; int known[25]; int num; int cases=1;

bool isPrime(int x){ for(int i = 2; i

if(x % i == 0) return 0;

return 1; }

void DFS(int n, int len){ int i; if(len==n && isPrime(str[n-1]+1)){