模板2

最小生成树（Prim,Kruskal）

求城市的最小生成树，城市标号是从0到n-1,注意重边和不能构成的情况

const int zui = 1000000000;int n,m;int map1[1010][1010];int lowdist[1010];int visit[1010];int sum;bool flag;void Prim(){ int i,j,k; sum = 0; memset(visit,0,sizeof(visit)); for(i=0; i<=n-1; i++) { lowdist[i] = map1[0][i]; } visit[0] = 1; for(i=1; i

求城市的最小生成树，修成的路用1标记，没有修成的用0标记

const int inf = 0x7f7f7f7f;//2139062143typedef long long ll;using namespace std;struct node{ int a,b; int value;}road[5000];int pre[110];bool cmp(node a,node b){ return a.value < b.value;}int find(int x){ return x == pre[x] ? x : pre[x] = find(pre[x]);}int Kruskal(int sum1){ int sum = 0; for(int i=0; i

最短路径

void Dijkstra(){ int i,j,k; int max2; memset(visit,0,sizeof(visit)); for(i=1; i<=n; i++) { low[i] = map1[0][i]; } for(i=1; i<=n; i++)//每次并一个点,需要并n次 { max2 = zui; for(j=1; j<=n; j++) { if(!visit[j] && low[j] < max2) { k = j; max2 = low[j]; } } visit[k] = 1; for(j=1; j<=n; j++) { if(!visit[j] && low[k] + map1[k][j] < low[j]) { low[j] = low[k] + map1[k][j]; } } }}

void Floyed(){ int i,j,k; for(k=1; k<=n; k++) { for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { if(map1[i][j] > map1[i][k] + map1[k][j]) { map1[i][j] = map1[i][k] + map1[k][j]; } } } }}

二分图的最大匹配（最大匹配数=最大点覆盖）

#include#includeint lol[101][301],visit[301],cf[301],n;bool find(int l){ int i; for(i=1; i<=n; i++) { if(lol[l][i] && !visit[i])//有好感并且没尝试把妹子许配给别人，要是visit[i]等于1表明，前面有一个人要i这个妹子要定了 { visit[i] = 1;//表明i这个妹子l要定了，别人不能再娶了，不然下面一条语句腾妹子的过程，本来想让i这个妹子的丈夫重娶一个妹子，结果这个妹子的丈夫还是娶了她，然后又把这个妹子配给l,这就太扯淡了，所以这一句不能放在if语句里面 if(!cf[i] || find(cf[i]))//i这个妹子没丈夫或者能让她的丈夫重娶一个妹子，和这个妹子离婚 { cf[i] = l;//妹子i的丈夫就是l了 return true;//光棍l摆脱单身 } } } return false;}int main(){ int t,p,i,j,sum,a,sum1; scanf("%d",&t); while(t--) { memset(lol,0,sizeof(lol)); memset(cf,0,sizeof(cf)); sum1 = 0; scanf("%d%d",&p,&n); for(i=1; i<=p; i++) { scanf("%d",&sum);//有好感的人的个数 for(j=0; j

记忆化搜索

AC代码1：

dp[x][y]记录的是点(x,y)到点(n-1,n-1)的数量,dp[x][y]的数量可以由它所到达的点的dp[x][y]的和求出来

[cpp] ​​view plain​​​ ​​copy​​ 1. #include 2. #include3. #include4. 5. using namespace std;6. 7. int map[40][40];8. long long dp[40][40];//用long long 类型9. int dir[2][2] = {{1,0},{0,1}};10. int n;11. 12. long long dfs(int x,int y)//返回值是long long 类型13. {14. int newx,newy,i;15. if(dp[x][y] || !map[x][y])//map[x][y]为0时，肯定没有到点（n-1，n-1）的路径，直接返回dp[x][y]，此时dp[x][y]为016. return dp[x][y];17. for(i=0; i<2; i++)18. {19. newx = x + dir[i][0] * map[x][y];20. newy = y + dir[i][1] * map[x][y];21. if(newx >= 0 && newy >= 0 && newx < n && newy < n)//判断条件写清楚22. dp[x][y] += dfs(newx,newy);23. }24. return dp[x][y];25. }26. int main()27. {28. int i,j;29. char lol[35];30. while(cin>>n && n != -1)31. {32. sizeof(dp));33. for(i=0; i>lol;36. for(j=0; j

AC代码2：

[cpp] ​​view plain​​​ ​​copy​​ 1. #include 2. #include3. 4. using namespace std;5. 6. int map[40][40];7. long long dp[40][40];//用long long 类型8. int dir[2][2] = {{1,0},{0,1}};9. 10. int main()11. {12. int i,j,n;13. char lol[35];14. while(cin>>n && n != -1)15. {16. sizeof(dp));17. for(i=0; i>lol;20. for(j=0; j

BFS

从起始位置到终止位置，转弯次数不超过k

#include#include#includeusing namespace std;int visit[110][110];char map[110][110];int dir[4][2] = {{-1,0,},{1,0},{0,-1},{0,1}};int m,n,k,endi,endj;struct node{ int x; int y; int dir;}a[10010];bool check(int x,int y){ if(x>0 && y>0 && x<=m && y<=n && map[x][y] != '*')//为*的位置不能走 return true; return false;}void bfs(int x,int y){ if(x == endi && y == endj) { cout<<"yes"< q; node in,out; in.x = x; in.y = y; in.dir = -1; q.push(in); while(!q.empty()) { out = q.front(); q.pop(); for(i=0; i<4; i++) { newx = out.x + dir[i][0]; newy = out.y + dir[i][1]; while(check(newx,newy)) { if(!visit[newx][newy]) { in.x = newx; in.y = newy; in.dir = out.dir + 1; q.push(in); visit[newx][newy] = 1; if(newx == endi && newy == endj && in.dir <= k) { cout<<"yes"<>t; while(t--) { memset(visit,0,sizeof(visit)); cin>>m>>n; for(i=1; i<=m; i++) { for(j=1; j<=n; j++) { cin>>map[i][j]; } } cin>>k>>y1>>x1>>endj>>endi;//最多转弯的次数，起始和终止位置 bfs(x1,y1); } return 0;}

连连看

线的转弯次数不超过2次

#include#includeint dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; int x1,y1,x2,y2,m,n,mark,l = 0;int a[1010][1010],visit[1010][1010];void dfs(int x3,int y3,int sum,int direction){ int i; if(x3 < 1 || x3 > n || y3 < 1 || y3 > m || visit[x3][y3] == 1) return; if(mark) return; if(sum > 2) return; if(x3 == x2 && y3 == y2) { mark = 1; return; } if(a[x3][y3] != 0) return; visit[x3][y3] = 1; //printf("%d %d %d %d %d\n",l,x3,y3,m,n); for(i=0; i<4; i++) { if(direction != i) dfs(x3+dir[i][0],y3+dir[i][1],sum+1,i); else dfs(x3+dir[i][0],y3+dir[i][1],sum,i); } visit[x3][y3] = 0;}int main(){ int i,j,q; //freopen("input6.txt","r",stdin); while(scanf("%d%d",&n,&m)) { if( n == 0 && m == 0) break; for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { scanf("%d",&a[i][j]); } } scanf("%d",&q); while(q--) { mark = 0; memset(visit,0,sizeof(visit)); scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if(a[x1][y1] == a[x2][y2] && a[x1][y1] != 0 && (x1 !=x2 || y1 != y2))//0表示空格，即使都是零，也不能消去 { visit[x1][y1] = 1; for(i=0; i<4; i++) { dfs(x1+dir[i][0],y1+dir[i][1],0,i); } } if(mark == 1) printf("YES\n"); else printf("NO\n"); } } return 0;}

路劲输出

定义一个二维数组：

int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, };

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

0 1 0 0 00 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0

Sample Output

(0, 0)(1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)

int map1[5][5];int visit[30][30];int pre[30];struct node{ int x; int y;}a[30];int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};bool judge(int x,int y){ if(x >=0 && x < 5 && y >= 0 && y < 5 && !visit[x][y] && !map1[x][y]) return true; return false;}void print(int x){ int t = pre[x]; if(t == -1) { printf("(0, 0)\n"); return; } print(t); printf("(%d, %d)\n",a[x].x,a[x].y);}void bfs(){ int head = 0,tail = 1; a[0].x = 0; a[0].y = 0; pre[0] = -1; while(head < tail) { for(int i=0; i<4; i++) { int newx = a[head].x + dir[i][0]; int newy = a[head].y + dir[i][1]; if(a[head].x == 4 && a[head].y == 4) { print(head); return; } if(judge(newx,newy)) { visit[newx][newy] = 1; pre[tail] = head; a[tail].x = newx; a[tail].y = newy; tail++; } } head++; }}int main(){ for(int i=0; i<5; i++) { for(int j=0; j<5; j++) { scanf("%d",&map1[i][j]); } } memset(visit,0,sizeof(visit)); bfs(); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。