HDOJ3468

发表于 | 分类于

题目在这里:HDOJ3468

解释一下题意
题目给了一张地图，地图上有墙/空地/宝藏/集合点’A’~’Z’~’a’~’z’
要求按顺序以最短路径访问集合点，每次最短路径可以最多拿一个宝藏，每个宝藏只能被拿一次，问到最后一个集合点的时候最多拿多少宝藏

先确认算法 显然这里要用到最短路径(bfs解决)
观察到每个宝藏只能被拿一次 最后求最多拿多少宝藏
考虑网络流（最大流）

考虑网络流建模：
超级源点s连接每个集合点，权值为1（因为每次从集合点出发拿宝藏，每次最短路只能拿一个）
超级汇点t连接每一个宝藏 权值为1（用于计数拿了多少宝藏）
在最短路径point[i]->point[i+1]中的所有宝藏与point[i]连边,权值为1（表示在从point[i]->point[i+1]的过程中可以取这个宝藏）
然后从s->t跑一边最大流就是答案

有一些小细节和实现
1) 当寻找最短路的时候发现走不到下一个集合点直接退出
2) 怎么判断一个宝藏是否在最短路径？先A->B跑一边最短路记录diss 然后B->A 用bfs或者dfs按diss[i][j]==diss[pre_i][pre_j]+1的规则往回走回去 如果当前的点是宝藏就连边

上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include<bits/stdc++.h>

using namespace std;

const int MAXN=10050;
const int INF=0x3f3f3f3f;
int n,m;

struct Edge{
    int from,to,cap,flow;
    Edge(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(flow){}
    Edge(){}
};

vector<Edge> edges;
vector<int> g[MAXN];
bool vis[MAXN];
int dis[MAXN];
int s,t;
int cur[MAXN];
char pp[105][105];

void clearall(){
    for(int i=0;i<MAXN;i++) g[i].clear();
    edges.clear();
}

queue<int> q;
bool bfs(){
    memset(vis,0,sizeof(vis));
    while(!q.empty()) q.pop();
    q.push(s);
    vis[s]=1;
    dis[s]=0;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=0;i<g[x].size();i++){
            Edge &e=edges[g[x][i]];
            if(!vis[e.to]&&e.cap>e.flow){
                vis[e.to]=1;
                dis[e.to]=dis[x]+1;
                q.push(e.to);
            }
        }
    }
    return vis[t];
}

void Addedge(int from,int to,int cap){
    edges.push_back(Edge(from,to,cap,0));
    edges.push_back(Edge(to,from,0,0));
    int tmp=edges.size();
    g[from].push_back(tmp-2);
    g[to].push_back(tmp-1);
}

int dfs(int x,int a){
    if(a==0||x==t) return a;
    int flow=0,f;
    for(int &i=cur[x];i<g[x].size();i++){
        Edge &e=edges[g[x][i]];
        if(dis[x]+1!=dis[e.to]) continue;
        f=dfs(e.to,min(a,e.cap-e.flow));
        if(f>0){
            e.flow+=f;
            edges[g[x][i]^1].flow-=f;
            flow+=f;
            a-=f;
            if(a==0) break;
        }
    }
    return flow;
}

int maxflow(){
    int flow=0;
    while(bfs()){
        memset(cur,0,sizeof(cur));
        flow+=dfs(s,INF);
    }
    return flow;
}

const int dx[]={0,0,-1,1};
const int dy[]={1,-1,0,0};
int diss[105][105];

int tmpx,tmpy;
bool sp_bfs(int x,int y,char tar){
    memset(diss,0x3f3f3f3f,sizeof(diss));
    queue<pair<int,int>> q;
    q.push(make_pair(x,y));
    diss[x][y]=0;
    while(!q.empty()){
        pair<int,int> ft=q.front();
        q.pop();
        if(pp[ft.first][ft.second]==tar) {
            tmpx=ft.first;
            tmpy=ft.second;
            return true;
        }
        for(int i=0;i<4;i++){
            int nx=ft.first+dx[i];
            int ny=ft.second+dy[i];
            if(nx<1||ny<1||nx>n||ny>m) continue;
            if(pp[nx][ny]=='#') continue;
            if(diss[nx][ny]==0x3f3f3f3f){
                diss[nx][ny]=diss[ft.first][ft.second]+1;
                q.push(make_pair(nx,ny));
            }
        }
    }
    return false;
}

int index(int x,int y){
    return (x-1)*m+y;
}
int index(pair<int,int> a){
    return (a.first-1)*m+a.second;
}

bool viss[105][105];
void re_dfs(int x,int y,int tx,int ty){
	if(viss[x][y]==1) return;
	viss[x][y]=1;
    if(x<1||y<1||x>n||y>m) return;
    if(x==tx&&y==ty) return;
    if(pp[x][y]=='*') Addedge(index(tx,ty),index(x,y),1);
    for(int i=0;i<4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx<1||ny<1||nx>n||ny>m) continue;
        if(diss[nx][ny]+1==diss[x][y]) re_dfs(nx,ny,tx,ty);
    }
    return;
}

struct Node{
    char ch;
    int x,y;
    Node(char ch,int x,int y):ch(ch),x(x),y(y){};
};

int main(){
    s=10010,t=10020;
    while(cin>>n>>m){
        clearall();
        char chmin='z'+1;
        char chmax='A'-1;
        int sx,sy;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>pp[i][j];
                if(pp[i][j]=='*') Addedge(index(i,j),t,1);
                else if(pp[i][j]>='A'&&pp[i][j]<='Z'||pp[i][j]>='a'&&pp[i][j]<='z'){
                    chmin=min(chmin,pp[i][j]);
                    chmax=max(chmax,pp[i][j]);
                    if(chmin==pp[i][j]) sx=i,sy=j;
                    Addedge(s,index(i,j),1);
                }
            }
        }
        bool exist=true;
        while(chmin!=chmax){
            char nch;
            if(chmin=='Z') nch='a';
            else nch=chmin+1;
            if(!sp_bfs(sx,sy,nch)){
                exist=false;
                break;
            }
			memset(viss,0,sizeof(viss));
            re_dfs(tmpx,tmpy,sx,sy);
            sx=tmpx,sy=tmpy;
            chmin=nch;
        }
        if(exist) cout<<maxflow()<<endl;
        else cout<<-1<<endl;
    }
    return 0;
}