好久没有写博客了，今天水几篇博客
挖地雷这个题之前在 信息学奥赛一本通 上做过几乎一样的题，但是由于数据太水导致我当时过了，进而导致我昨天（4.28）考试丢了20分，今天写一篇题解
这个挖地雷我们首先要想一个问题（基本人人能想到）：
看这个图，如果我们从4出发，假设能挖到10颗雷，那么我们从1或3出发肯定能挖到更多的雷，毕竟你不可能挖到的雷是负数个或者会丢失雷
那么我们就应该从没有入度的点开始，这貌似跟最短路差不多
思路：
a:
1.从入度为0的点开始,若能更新它的出边的点则更新,然后删边并让它的入度减一,若减到0则入队.
2.标记刚刚更新的点
3.检查是否全部标记
if(全部标记)
goto b;
4.不断重复 goto a;
注意:并不是只有更新过的点才删边及减入度,不管有无更新,与入度为0的点相连的边都要删,入度都要减(如果不明白可以拿上面那个图手动模拟一下就知道为什么了)
b:
交代
.-' _..`.
/ .'_.'.'
| .' (.)`.
;' ,_ `.
.--.__________.' ; `.;-'
| ./ /
| | /
`..'`-._ _____, ..'
/ | | | |\ \
/ /| | | | \ \
/ / | | | | \ \
/_/ |_| |_| \_\
|__\ |__\ |__\ |__\
(这是一种神奇的生物自己可以手动增加空格把他复原)
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<stack>
#include<queue>
#include<iostream>
using namespace std;
bool b[][];//临界矩阵存边
stack <int> ss;//栈输出路径
int a[],du[],s[],pre[];//a[]->每个地窖的地雷数,du[]指入度,s[]指当前挖到这个地窖最优,pre[]用来记录路径
int n,yyy;//n指有几个地窖,yyy用来去掉最后的空格
queue <int> q;//队列储存入度为0
void print(int x) {//打印路径
if(x==)//没有前驱就返回
return ;
yyy++;
ss.push(x);
print(pre[x]);//递归找
}
void dd(int x) {
for(int i=; i<=n; i++) {//枚举每一个点
if(b[x][i] == ) {//有路的话
b[x][i] = ;//删边
du[i]--;//减度
if(du[i] == ) {//如果减到0就入队
q.push(i);
}(这几句不能放到下面)
if(s[i] < s[x]+a[i]) {//如果能更新就更新
s[i] = s[x]+a[i];
pre[i] = x;//记录路径
}
} } }
void dg() {
for(int i=; i<=n; i++) {//找一开始入度为0的边
if(du[i] == ) {
q.push(i);
}
}
while(q.empty() == ) {//这个可以写到dd()里面
int a=q.front();
q.pop();
dd(a);
}
} int main() {
// freopen("lei.in","r",stdin);
// freopen("lei.out","w",stdout);
scanf("%d",&n);
for(int i=; i<=n; i++) {
scanf("%d",&a[i]);
s[i]= a[i];//一开始最优就是只走一个
}
for(int i=; i<=n; i++) {
for(int j=i+; j<=n; j++) {
scanf("%d",&b[i][j]);
if(b[i][j] == )//记录度数
du[j]++;
}
} dg();
int zd=,xx;
for(int i=; i<=n; i++) {//找到最大值,并找到最大值的序号
if(s[i]>zd) {
zd=s[i];
xx=i;
}
}
print(xx);//打印
for(int i=; i<yyy; i++) {//yyy的用途
cout<<ss.top()<<' ';
ss.pop();
}
cout<<ss.top()<<endl;//最后换行格式错了貌似会WA
cout<<zd;
return ;
}
一篇博客水完啦