POJ 3411 Paid Roads(DFS)

题意 你要从第1个城市到第N个城市去 有m条路 每条路用a, b, c, p, r 表示
你从第a个城市到第b个城市时 若之前经过或现在位于第c个城市 过路费就是p元
否则就是r元 求你到达第N个城市最少用多少过路费

由于最多只有10个城市 10条路 这个题就变得很简单了 直接暴力dfs就行
可以用状态压缩来存储已经走过了哪些城市 由于最多只有10条路
从某个城市出发要一条 回这个城市也要一条 所以一个城市最多经过5次
这个可以作为dfs的结束条件

 

#include 
#include 
#include 
using namespace std;

const int N = 11, INF = 2333333;
int n, m, ans, vis[N];
struct road{
    int a, b, c, p, r;
} rd[N];

//当前所在城市, 到过哪些城市, 当前已经用了多少过路费
void dfs(int p, int s, int v)
{
    if(vis[p] > 5) return;
    s = s | 1 << (p - 1);
    if(p == n)
    {
        ans = min(ans, v);
        return;
    }

    for(int i = 0; i < m; ++i)
    {
        if(rd[i].a != p) continue;
        ++vis[rd[i].b];
        if(s & 1 << (rd[i].c - 1)) //到过城市c
            dfs(rd[i].b, s, v + rd[i].p);
        else dfs(rd[i].b, s, v + rd[i].r);
        --vis[rd[i].b]; //回溯
    }
}

int main()
{
    while(~scanf(%d%d, &n, &m))
    {
        for(int i = 0; i < m; ++i)
            scanf(%d%d%d%d%d, &rd[i].a, &rd[i].b, &rd[i].c, &rd[i].p, &rd[i].r);

        ans = INF;
        memset(vis, 0, sizeof(vis));
        dfs(1, 0, 0);
        if(ans == INF) puts(impossible);
        else printf(%d
, ans);
    }

    return 0;
}
Paid Roads

Description

A network of m roads connects N cities (numbered from 1 to N). There may be more than one road connecting one city with another. Some of the roads are paid. There are two ways to pay for travel on a paid road i from city ai to city bi:

in advance, in a city ci (which may or may not be the same as ai);after the travel, in the city bi.

The payment is Pi in the first case and Ri in the second case.

Write a program to find a minimal-cost route from the city 1 to the city N.

Input

The first line of the input contains the values of N and m. Each of the following m lines describes one road by specifying the values of ai, bi, ci, Pi, Ri (1 ≤ im). Adjacent values on the same line are separated by one or more spaces. All values are integers, 1 ≤ m, N ≤ 10, 0 ≤ Pi , Ri ≤ 100, PiRi (1 ≤ im).

Output

The first and only line of the file must contain the minimal possible cost of a trip from the city 1 to the city N. If the trip is not possible for any reason, the line must contain the word ‘impossible’.

Sample Input

4 5
1 2 1 10 10
2 3 1 30 50
3 4 3 80 80
2 1 2 10 10
1 3 2 10 50

Sample Output

110

Source

Northeastern Europe 2002, Western Subregion

 

 

3411 Paid Roads(DFS) 题意
你要从第1个城市到第N个城市去 有m条路 每条路用a, b, c, p, r 表示
你从第a个城市到第b个城市时 若之前经过或现在位…

Paid Roads

深度优先搜索

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 6549   Accepted: 2427

DFS基本思想

Description

基本步骤:

A network of m roads connects N cities (numbered from 1
to N). There may be more than one road connecting one city with
another. Some of the roads are paid. There are two ways to pay for
travel on a paid road i from city ai to
city bi:

1.从图中某个顶点v0出发,首先访问v0;

  • in advance, in a city ci (which may or may not be the
    same as ai);
  • after the travel, in the city bi.

2.访问结点v0的第一个邻接点,以这个邻接点vt作为一个新节点,访问vt所有邻接点。直到以vt出发的所有节点都被访问到,回溯到v0的下一个未被访问过的邻接点,以这个邻结点为新节点,重复上述步骤。直到图中所有与v0相通的所有节点都被访问到。

The payment is Pi in the first case
and Ri in the second case.

3.若此时图中仍有未被访问的结点,则另选图中的一个未被访问的顶点作为起始点。重复深度优先搜索过程,直到图中的所有节点均被访问过。

Write a program to find a minimal-cost route from the city 1 to the
city N.

威尼斯人平台 1图片发自简书App威尼斯人平台 2图片发自简书App

Input

基本代码结构

The first line of the input contains the values of N and m. Each
of the following m lines describes one road by specifying the values
of aibiciPiRi (1
≤ ≤ m). Adjacent values on the same line are separated by one
or more spaces. All values are integers, 1 ≤ m, N ≤ 10, 0
≤ Pi , Ri ≤
100, Pi ≤ Ri (1 ≤ ≤ m).

void DFS( Point P ){

Output

for{

The first and only line of the file must contain the minimal possible
cost of a trip from the city 1 to the city N. If the trip is not
possible for any reason, the line must contain the word
impossible’.

if{

Sample Input

if

4 5
1 2 1 10 10
2 3 1 30 50
3 4 3 80 80
2 1 2 10 10
1 3 2 10 50

return true;

Sample Output

标记K;

110

dfs;

Source

}

Northeastern Europe
2002,
Western Subregion

}

大致题意:

}

有n座城市和m(1<=n,m<=10)条路。现在要从城市1到城市n。有些路是要收费的,从a城市到b城市,如果之前到过c城市,那么只要付P的钱,如果没有去过就付R的钱。求的是最少要花多少钱。

广度优先搜索

注意:路径是有向的。

BFS基本思想

 

基本步骤:

#include<iostream>
#include<cstring>
using namespace std;
struct node{
    int a,b,c,p,r;
}e[11];//每条道路的付费规则
int n,m,mincost,vis[11];//城市数//道路数//最小总花费//记录城市的访问次数,每个城市最多经过3次
void dfs(int now,int fee){//now:当前所在城市,fee:当前方案的费用
    if(now==n&&mincost>fee){
        mincost=fee;return ;
    }
    for(int i=1;i<=m;i++){//枚举道路
        if(now==e[i].a&&vis[e[i].b]<=3){
            vis[e[i].b]++;
            if(vis[e[i].c])
                dfs(e[i].b,fee+e[i].p);    
            else
                dfs(e[i].b,fee+e[i].r);
            vis[e[i].b]--;//回溯
        }
    }
}
int main(){
    while(cin>>n>>m){
        memset(vis,0,sizeof vis);
        vis[1]=1;//从城市1出发,因此预记录到达1次
        mincost=2000;
        for(int i=1;i<=m;i++)
            cin>>e[i].a>>e[i].b>>e[i].c>>e[i].p>>e[i].r;
        dfs(1,0);
        if(mincost==2000)
            cout<<"impossiblen";
        else
            cout<<mincost<<endl;
    }
    return 0;
}

1.从图中某个顶点v0出发,首先访问v0;

 

2.依次访问v0的各个未被访问的邻接点;

3.依次从上述邻接点出发,访问它们的各个未被访问的邻接点。

4.若此时图中仍有未被访问的结点,则另选图中的一个未被访问的顶点作为起始点。重复广度优先搜索过程,直到图中的所有节点均被访问过。

威尼斯人平台 3图片发自简书App威尼斯人平台 4图片发自简书App

基本代码结构

通常用队列(先进先出,FIFO)实现

初始化队列Q.

Q={起点s};

标记s为己访问;

while {

取Q队首元素u; u出队;

if (u == 目标状态) {…}

所有与u相邻且未被访问的点进入队列;

标记与u相邻的点为已访问;

}

DFS/BFS是竞赛中最常见的基础算法。虽然题目多种多样,但无外乎就是套用上文的程序片段,最主要的还是结合习题多练习达到熟能生巧。

这里呢,我想多讲一点。上面的BFS是使用C++库里封装的队列的,这里额外写一个不使用封装队列的方法,就是自己使用一个数组来模拟操作,见下方代码:

#include<bits/stdc++.h>

using namespace std;

int a[105][105],vis[105],n,m;

//a是邻接矩阵 vis是标记 点是否被访问过

void bfs{ //k是当前点的名字

int q[105];

int f,r,i,j;//r表示当前BFS路过的点是第r个点

q[1]=k;

vis[k]=1;

f=1;r=1;

while{

i=q[f];

for(j=1;j<=n;j++){

if(a[i][j]>0&&!vis[j]){ //邻接矩阵中a[i][j]>0 表示
i和j连通

r++;

q[r]=j;

vis[j]=1;

}

}

f++;

}

for(i=1;i<=r;i++) cout<<q[i]<<”
“;//输出当前BFS层的点的序号

}

int main(){

int h,v1,v2;

威尼斯人平台,cin>>m;//点的数量

cin>>n;//边的数量

memset(a,0,sizeof;

memset(vis,0,sizeof;

for(int i=1;i<=n;i++){

cin>>v1>>v2>>h;//每条边的 起点 终点 边长

a[v1][v2]=a[v2][v1]=h;//无向图正反对接

}

for(int i=1;i<=n;i++)ifbfs;

return 0;

}

下面给出一些例题和代码 及时练习效果更佳

出栈次序

X星球特别讲究秩序,所有道路都是单行线。一个甲壳虫车队,共16辆车,按照编号先后发车,夹在其它车流中,缓缓前行。

路边有个死胡同,只能容一辆车通过,是临时的检查站,如图所示。

X星球太死板,要求每辆路过的车必须进入检查站,也可能不检查就放行,也可能仔细检查。

如果车辆进入检查站和离开的次序可以任意交错。那么,该车队再次上路后,可能的次序有多少种?

为了方便起见,假设检查站可容纳任意数量的汽车。

显然,如果车队只有1辆车,可能次序1种;2辆车可能次序2种;3辆车可能次序5种。

现在足足有16辆车啊,亲!需要你计算出可能次序的数目

这是一个整数,请通过浏览器提交答案,不要填写任何多余的内容。

威尼斯人平台 5图片发自简书App

#include<iostream>

using namespace std;

long long count=0;

void dfs(int a,int b,int k){

if(a==16&&b==16&&k==32){

count++;

return;

}

if(a<=16&&b<=16&&a>=b&&k<32){

dfs(a+1,b,k+1);

dfs(a,b+1,k+1);

}

return ;

}

int main(){

dfs;

cout<<count;

return 0;

}

油田

输入一个m行n列的字符矩阵,统计字符“@”组成多少个八连块。如果两个字符“@”所在的格子相邻,就说明他们属于同一个八连块。如图,有两个八连块

* * * * @

* @ @ * @

* @ * * @

@ @ @ * @

@ @ * * @

方法一:用DFS解决

#include<cstdio>

#include<cstring>

const int maxn=105;

char pic[maxn][maxn];

int m,n,idx[maxn][maxn];

void dfs(int r,int c,int id){

if(r<0||r>=m||c<0||c>=n) return;

if(idx[r][c]>0||pic[r][c]!=’@’) return;

idx[r][c]=id;

for(int dr=-1;dr<=1;dr++)

for(int dc=-1;dc<=1;dc++)

if(dr!=0||dc!=0)dfs(r+dr,c+dc,id);

}

int main(){

while(scanf(“%d%d”,&m,&n)==2&&m&&n){

for(int i=0;i<m;i++) scanf(“%s”,pic[i]);

memset(idx,0,sizeof;

int cnt=0;

for(int i=0;i<m;i++)

for(int j=0;j<n;j++)

if(idx[i][j]==0&&pic[i][j]==’@’) dfs(i,j,++cnt);

printf(“%dn”,cnt);

}

return 0;

}

方法二:用BFS解决

#include<bits/stdc++.h>

using namespace std;

const int maxn=105;

int m,n;

int vis[maxn][maxn];

char s[maxn][maxn];

int cnt=0;

int
dir[8][2]={{0,1},{1,-1},{-1,-1},{-1,0},{0,-1},{-1,1},{1,0},{1,1}};

typedef struct Node{

int x,y;

}node;

void bfs(int x,int y){

node p,t;

queue<node> q;

p.x=x;

p.y=y;

q.push;

while(!q.empty{

p=q.front();

q.pop();

for(int i=0;i<8;i++){

t.x=p.x+dir[i][0];

t.y=p.y+dir[i][1];

if(t.x<0||t.x>=n||t.x<0||t.y>=m){

continue;

}

if(!vis[t.x][t.y]&&s[t.x][t.y]==’@’){

vis[t.x][t.y]=1;

q.push;

}

}

}

}

int main()

{

while(scanf(“%d %d”,&n,&m)&&{

memset(vis,0,sizeof vis);

cnt=0;

for(int i=0;i<n;i++){

scanf(“%s”,s[i]);

}

for(int i=0;i<n;i++){

for(int j=0;j<m;j++){

if(!vis[i][j]&&s[i][j]==’@’){

vis[i][j]=1;

cnt++;

bfs;

}

}

}

printf(“%dn”,cnt);

}

return 0;

}

相关文章