题目限制一览
| 题目 |
时间限制 |
空间限制 |
| 1. buckets |
$1000$ MS |
$256$ MB |
| 2. factory |
$1000$ MS |
$256$ MB |
| 3. dining |
$1000$ MS |
$512$ MB |
1. 救火（buckets.cpp）
Description
农场上起火了，奶牛们正在紧急赶去灭火！
农场可以用一个像这样的10×10的字符方阵来描述：
1
2
3
4
5
6
7
8
9
10
| ..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........
|
字符’B’表示正着火的牛棚。字符’L’表示一个湖，而字符’R’表示农场上的一块巨大岩石。
奶牛们想要沿着一条湖到牛棚之间的路径组成一条“水桶传递队列”，这样她们就可以沿着这条路径传递水桶来帮助灭火。当两头奶牛在东南西北四个方向上相邻时水桶可以在她们之间传递。这对于湖边的奶牛也是对的——奶牛只能在紧挨着湖的时候才能用水桶从湖里取水。类似地，奶牛只能在紧挨着牛棚的时候才能用水去灭牛棚的火。
请帮助求出奶牛们为了组成这样的“水桶传递队列”需要占据的’.’格子的最小数量。
奶牛不能站在岩石所在的方格之内，此外保证牛棚和湖不是相邻的。
输入包含10行，每行10个字符，描述这个农场的布局。输入保证图案中恰有一个字符’B’、一个字符’L’以及一个字符’R’。
Output
输出一个整数，为组成一条可行的水桶传递队列所需要的奶牛的最小数量。
1
2
3
4
5
6
7
8
9
10
| ..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........
|
Sample Output
Hint
在这个例子中，以下是一个可行的方案，使用了最小数量的奶牛（7）：
1
2
3
4
5
6
7
8
9
10
| ..........
..........
..........
..B.......
..C.......
..CC.R....
...CCC....
.....C....
.....L....
..........
|
分析
做法一：BFS（100分）
用 洪水填充法 填表，设 $f[i][j]=min(f[i][j],f[i’][j’]+1)$ ，$i’$ 和 $j’$ 来自于上下左右的格子
边界为 $f[sx][sy]=0$ 表示为 $L$ 的格子坐标
做法二：计算（100分）
发现数据中只有一块岩石 $R$，那么显然从 $L$ 格子走一个 L 形路线到 B 格子就行了，因为 L 形路线有两条，不可能全被 $R$ 阻挡所以一定可以走通
Codes
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
| #include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn 13
using namespace std;
typedef pair<pair<int,int>,int> pp;
char M[maxn][maxn];bool vis[maxn][maxn];
int offX[]={0,0,1,-1},offY[]={1,-1,0,0};
int f[maxn][maxn];int sx,sy,ex,ey;
void solve(){
for(int i=1;i<=10;i++)
for(int j=1;j<=10;j++){
if(M[i][j]=='L'){sx=i;sy=j;continue;}
if(M[i][j]=='B'){ex=i;ey=j;continue;}
}
memset(f,127,sizeof(f));
queue<pp> q; pp head; int newx,newy;
q.push(make_pair(make_pair(sx,sy),0));
f[sx][sy]=0;
while(!q.empty()){
#define x head.first.first
#define y head.first.second
#define z head.second
head=q.front();q.pop();
if(vis[x][y]) continue;
vis[x][y]=true;
for(int i=0;i<4;i++){
newx=x+offX[i];newy=y+offY[i];
if(newx<1 || newx>10 || newy<1 || newy>10) continue;
if(M[newx][newy]=='R') continue;
f[newx][newy]=min(f[newx][newy],f[x][y]+1);
q.push(make_pair(make_pair(newx,newy),z+1));
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("buckets.in","r",stdin);
freopen("buckets.out","w",stdout);
#endif
for(int i=1;i<=10;i++) scanf("%s",&M[i][1]);
solve();
printf("%d",f[ex][ey]-1);
return 0;
}
|
2.奶牛工厂（factory.cpp）
Description
牛奶生意正红红火火！Farmer John的牛奶加工厂内有N个加工站，编号为1…N（1≤N≤100），以及N−1条通道，每条连接某两个加工站。（通道建设很昂贵，所以Farmer John选择使用了最小数量的通道，使得从每个加工站出发都可以到达所有其他加工站）。
为了创新和提升效率，Farmer John在每条通道上安装了传送带。不幸的是，当他意识到传送带是单向的已经太晚了，现在每条通道只能沿着一个方向通行了！所以现在的情况不再是从每个加工站出发都能够到达其他加工站了。
然而，Farmer John认为事情可能还不算完全失败，只要至少还存在一个加工站i满足从其他每个加工站出发都可以到达加工站i。注意从其他任意一个加工站j前往加工站i可能会经过i和j之间的一些中间站点。请帮助Farmer John求出是否存在这样的加工站i。
输入的第一行包含一个整数N，为加工站的数量。以下N−1行每行包含两个空格分隔的整数ai和bi，满足1≤ai,bi≤N以及ai≠bi。这表示有一条从加工站ai向加工站bi移动的传送带，仅允许沿从ai到bi的方向移动。
Output
如果存在加工站i满足可以从任意其他加工站出发都可以到达加工站i，输出最小的满足条件的i。否则，输出−1。
Sample Output
Hint
无
分析
做法一：暴力 + DFS（100分）
看到 $N\leq100$ 我们就知道这个题有多水了，存了反图之后直接对每个点暴力地 DFS 一遍看能不能遍历到所有点，把最先满足条件的输出就行
做法二：暴力 + 并查集（100分）
稍微优雅一点的暴力，维护每个点的并查集 $f(i)$ ，每次连边 $u\to v$ 就把 $f(u)$ 搬进 $f(v)$ 里面即可，最后判断有没有点的 $siz(f(i))=n$ ，由于数据太水，甚至不需要启发式合并
Codes
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
| #include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn 101
#define maxm maxn*2
using namespace std;
template<typename t>inline void fcin(t &x){
int sign=1; x=0; char op=getchar();
while(op<'0'||op>'9'){if(op=='-') sign=-1;op=getchar();}
while(op>='0'&&op<='9'){x=x*10+(op-48);op=getchar();}
x*=sign;
}
int to[maxm],nxt[maxm],head[maxn];
int tot,n;bool vis[maxn];int cnt;
inline void Eadd(int u,int v){
to[++tot]=v;nxt[tot]=head[u];
head[u]=tot;
}
void dfs(int u){
if(vis[u]) return;
cnt++;vis[u]=true;
for(int i=head[u];i;i=nxt[i])
dfs(to[i]);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("factory.in","r",stdin);
freopen("factory.out","w",stdout);
#endif
fcin(n); int x,y;
for(int i=1;i<n;i++){fcin(x);fcin(y);Eadd(y,x);}
for(int i=1;i<=n;i++){
memset(vis,false,sizeof(vis));cnt=0;
dfs(i);if(cnt==n){printf("%d",i);return 0;}
}
printf("-1");
return 0;
}
|
3.奶牛觅食（dining.cpp）
Description
漫长的一天结束了，饥困交加的奶牛们准备返回牛棚。农场由N片牧场组成（2≤N≤50,000），方便起见编号为1…N。所有奶牛都要前往位于牧场N的牛棚。其他N−1片牧场中每片有一头奶牛。奶牛们可以通过M条无向的小路在牧场之间移动（1≤M≤100,000）。第i条小路连接牧场ai和bi，通过需要时间ti。每头奶牛都可以经过一些小路回到牛棚。
由于饥饿，奶牛们很乐于在他们回家的路上停留一段时间觅食。农场里有K(1≤K≤n)个有美味的干草捆，第ii个干草捆的美味值为yi。每头奶牛都想要在她回牛棚的路上在某一个干草捆处停留，但是她这样做仅当经过这个干草捆使她回牛棚的时间增加不超过这个干草捆的美味值。注意一头奶牛仅仅“正式地”在一个干草捆处因进食而停留，即使她的路径上经过其他放有干草捆的牧场；她会简单地无视其他的干草捆。
输入的第一行包含三个空格分隔的整数N，M和K。以下M行每行包含三个整数ai，bi和ti，表示牧场ai和bi之间有一条需要ti时间通过的小路（ai不等于bi，ti为不超过10^4的正整数）。
以下K行，每行以两个整数描述了一个干草捆：该干草捆所在牧场的编号，以及它的美味值（一个不超过10^9的正整数）。同一片牧场中可能会有多个干草捆。
Output
输出包含N−1行。如果牧场i里的奶牛可以在回牛棚的路上前往某一个干草捆并且在此进食，则第i行为一个整数1，否则为一个整数0。
1
2
3
4
5
6
7
| 4 5 1
1 4 10
2 1 20
4 2 3
2 3 5
4 3 2
2 7
|
Sample Output
Hint
在这个例子中，牧场3里的奶牛可以停留进食，因为她回去的时间仅会增加6（从2增加到8），而这个增加量并没有超过干草捆的美味值7。牧场2里的奶牛显然可以吃掉牧场2里的干草，因为这并不会导致她的最佳路径发生变化。对于牧场1里的奶牛是一个有趣的情况，因为看起来她的最佳路径（10）可能会因为前去进食而有过大的增加量。然而，确实存在一条路径使得她可以前去干草捆处停留：先到牧场4，然后去牧场2（吃草），然后回到牧场4。
分析
做法一：SPFA + 少量递推（100分）
首先用 SPFA 求出所有点到点 n 的单源最短路径，考虑经过有干草的牧场对于奶牛心理的影响
设 $dist[i][0]$ 表示原本的单源最短路径，$dist[i][1]$ 表示在某一个牧场吃过草后心理上的最短路径，显然，若对于奶牛 $i$ 有 $dist[i][1]\leq dist[i][0]$，则奶牛 $i$ 是可以吃了草再走回牛棚的
其实在第一遍用 SPFA 求 $dist[i][0]$ 的时候可以把 $dist[i][1]$ 顺带求了，具体是：
$dist[i’][1]=min(dist[i][1]+w,\;dist[i][0]+w-f[i’])$
其中 $i’$ 表示 SPFA 当前考虑的下一个点，$f[i’]$ 表示其美味程度，注意要严格控制 $dist[i][1]$ 为吃了草才能形成的最短路径，可以将没有干草的点弄成 $f[x]=-inf$
做法二：两次 SPFA（100分）
第一遍 SPFA 求各个点到 n 的单源最短路径，第二遍 SPFA 开始时不要将 $dist$ 数组全部赋值 INF，将带有干草的那几个点的 $dist$ 值设定成美味程度，n 点的 $dist$ 为零，其他点的 $dist$ 设置为 INF 即可求出通过吃草走出的到 n 点的最短路径，剩下的部分处理思路同做法一
Codes
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
| #include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn 100001
#define maxm maxn*2
using namespace std;
template<typename t>inline void fcin(t &x){
int sign=1; x=0; char op=getchar();
while(op<'0'||op>'9'){if(op=='-') sign=-1;op=getchar();}
while(op>='0'&&op<='9'){x=x*10+(op-48);op=getchar();}
x*=sign;
}
int deli[maxn];
int dist[maxn][2];
int to[maxm],w[maxm],nxt[maxm];
int head[maxn],tot;bool vis[maxn];
inline void Eadd(int u,int v,int ww){
to[++tot]=v;w[tot]=ww;
nxt[tot]=head[u];head[u]=tot;
}
int n,m,k;
void SPFA(int s){
memset(dist,0x3f,sizeof(dist));
queue<int> q;
dist[s][0]=0;
vis[s]=true;
int qhead; q.push(s);
while(!q.empty()){
qhead=q.front();q.pop();
vis[qhead]=false;
for(int i=head[qhead];i;i=nxt[i]){
if(dist[to[i]][0]>dist[qhead][0]+w[i]){
dist[to[i]][0]=dist[qhead][0]+w[i];
if(!vis[to[i]]){
q.push(to[i]);
vis[to[i]]=true;
}
}
if(dist[to[i]][1]>dist[qhead][1]+w[i]){
dist[to[i]][1]=dist[qhead][1]+w[i];
if(!vis[to[i]]){
q.push(to[i]);
vis[to[i]]=true;
}
}
if(dist[to[i]][1]>dist[qhead][0]+w[i]-deli[to[i]]){
dist[to[i]][1]=dist[qhead][0]+w[i]-deli[to[i]];
if(!vis[to[i]]){
q.push(to[i]);
vis[to[i]]=true;
}
}
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("dining.in","r",stdin);
freopen("dining.out","w",stdout);
#endif
fcin(n);fcin(m);fcin(k);
int x,y,z,fx,fy;
for(int i=1;i<=m;i++){
fcin(x);fcin(y);fcin(z);
Eadd(x,y,z);Eadd(y,x,z);
}
memset(deli,-0x3f,sizeof(deli));
for(int i=1;i<=k;i++){
fcin(x);fcin(y);
deli[x]=max(deli[x],y);
}
if(deli[n]>0){
for(int i=1;i<=n-1;i++) printf("1\n");
return 0;
}
SPFA(n);
for(int i=1;i<=n-1;i++){
if(dist[i][0]>=dist[i][1]) printf("1\n");
else printf("0\n");
}
return 0;
}
|
