求第一个点到每一个点的最短路的数量;
第一个点到第一个点的数量固定为1,由于边权为1,求最短路数量也就相当于求bfs搜索树的深度,因为每一个点的最短路都要经过连接它的上一个点,一次bfs就可以了。
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n,m;
int i;
int dep[1000001],vis[1000001],ans[1000001];
vector<int >v[1000001];
queue<int >q;
int main(){
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++){
int a,b;
scanf("%d %d",&a,&b);
if(a==b) continue;
v[a].push_back(b);
v[b].push_back(a);
}
dep[1]=0;vis[1]=1;ans[1]=1;q.push(1);
while(!q.empty()){
int x=q.front();q.pop();
for(i=0;i<v[x].size();i++){
int y=v[x][i];
if(!vis[y]){
vis[y]=1;
dep[y]=dep[x]+1;
q.push(y);
}
if(dep[y]==dep[x]+1){
ans[y]=(ans[x]+ans[y])%100003;
}
}
}
for(i=1;i<=n;i++){
printf("%d\n",ans[i]);
}
return 0;
}
用最少数量的河蟹封锁一张无向图,每只河蟹可以对一个点进行封锁,当某个点被封锁后,与这个点相连的道路就被封锁了,且河蟹不能相邻,做不到就输出Impossible;
对无向图中的每一个节点进行染色,由于河蟹不能相邻,所以相邻的节点不能使用同一种颜色,在对已经染色的点进行染色时,判断它当前的颜色与相邻的点是否相同,全部染色完成后,取两种颜色的较小值即可。
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
int head[10010],vis[10010],sum[3];
int i,ans=0,ant=0;
struct node{
int t;int next;
}t[200010];
void add(int x,int y){
ant++;
t[ant].t=y;
t[ant].next=head[x];
head[x]=ant;
}
queue<int>q;
int BFS(int s){
vis[s]=1;
sum[1]=1;sum[2]=0;
q.push(s);
while(!q.empty()){
int a=q.front();q.pop();
for(i=head[a];i;i=t[i].next){
int b=t[i].t;
if(vis[b]==vis[a]) return 1;
if(vis[b]==0){
vis[b]=vis[a]%2+1;
sum[vis[b]]++;
q.push(b);
}
}
}
return 0;
}
int main(){
int n,m;
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++){
int a,b;
scanf("%d %d",&a,&b);
add(a,b);
add(b,a);
}
for(i=1;i<=n;i++){
if(vis[i]) continue;
if(BFS(i)){
printf("Impossible");
return 0;
}
else ans+=min(sum[1],sum[2]);
}
printf("%d",ans);
return 0;
}
重生之我是卧底,计算每个领主被瘟疫感染的时间,汇报给巫妖王;
节点分为两种,一种是感染源,一种是领主,其他的杂兵不用管,从感染源开始进行bfs,将整个矩阵遍历,给每一个单位赋值,最后输出即可。
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int map[510][510],vis[510][510],q[100010][2];
int i,j;
int ans=0;
int n,m,a,b;
void BFS(){
int kp[4][2]={0,1,-1,0,1,0,0,-1};
for(j=1;j<ans;j++){
int x=q[j][0],y=q[j][1];
vis[x][y]=1;
for(i=0;i<4;i++){
int xx=x+kp[i][0];int yy=y+kp[i][1];
if(vis[xx][yy]) continue;
if(xx<1||xx>n||yy<1||yy>m) continue;
map[xx][yy]=map[x][y]+1;
vis[xx][yy]=1;
q[++ans][0]=xx;q[ans][1]=yy;
}
}
}
int main(){
scanf("%d %d %d %d",&n,&m,&a,&b);
for(i=1;i<=a;i++){
int x,y;
scanf("%d %d",&x,&y);
q[++ans][0]=x;q[ans][1]=y;
vis[x][y]=1;
}
BFS();
for(i=1;i<=b;i++){
int x,y;
scanf("%d %d",&x,&y);
printf("%d\n",map[x][y]);
}
return 0;
}
重生之我是马,和卧底基本上一样,但是要注意遍历的时候要用象棋马的走法,就是马走日。
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n,m;
int i,j,ans=0;
int map[410][410],vis[410][410],q[200000][2];
int kp[8][2]={2,1,2,-1,-2,1,-2,-1,1,2,1,-2,-1,2,-1,-2};
void bfs(){
int head=0;
while(head<ans){
head++;
int x=q[head][0],y=q[head][1];
vis[x][y]=1;
for(i=0;i<8;i++){
int xx=x+kp[i][0],yy=y+kp[i][1];
if(xx<1||xx>n||yy>m||yy<1) continue;
if(vis[xx][yy]) continue;
vis[xx][yy]=1;
map[xx][yy]=map[x][y]+1;
q[++ans][0]=xx;q[ans][1]=yy;
}
}
}
int main(){
int x,y;
scanf("%d %d %d %d",&n,&m,&x,&y);
q[++ans][0]=x;q[ans][1]=y;
bfs();
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(map[i][j]==0&&(x!=i||y!=j)) printf("-1\t");
else printf("%d\t",map[i][j]);
}
printf("\n");
}
return 0;
}
5.[USACO06FEB]Backward Digit Sums G/S - 洛谷
写出一个1至N的排列ai,然后每次将相邻两个数相加,构成新的序列,再对新序列进行这样的操作,显然每次构成的序列都比上一次的序列长度少1,直到只剩下一个数字位置。下面是一个例子:
3,1,2,4
4,3,6
7,9
16
最后得到16这样一个数字。
现在想要倒着玩这样一个游戏,如果知道N,知道最后得到的数字的大小sum,请你求出最初序列ai,为1至N的一个排列。若答案有多种可能,则输出字典序最小的那一个。
痛苦深搜,首先要想明白ai的相加与n的关系,简单排列一下(假设ai都为1)
n为4 1+3+3+1 n为5 1+4+6+4+1 n为6 1+5+10+10+5+1
其实就是杨辉三角每层的数字
有了每个数相加的个数,接下来就是枚举了,由于最后要求字典序,所以采用深搜,还可以进行一个枝的剪,当累计的和超过sum时,直接返回就可以了。
#include <bits/stdc++.h>
using namespace std;
int n,p;
int a[13];
int c[13][13];
bool b[13];
void dfs(int dep,int s)
{
if(s>p)
return;
if(dep>n)
{
if(s==p)
{
cout<<a[1];
for(int i=2;i<=n;i++)
cout<<" "<<a[i];
exit(0);
}
return;
}
for(int i=1;i<=n;i++)
{
if(b[i]==false)
{
b[i]=true;
a[dep]=i;
dfs(dep+1,s+i*c[n][dep]);
b[i]=false;
}
}
}
int main()
{
cin>>n>>p;
c[1][1]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<=i;j++)
c[i][j]=c[i-1][j]+c[i-1][j-1];
dfs(1,0);
return 0;
}
一矩形阵列由数字 0 到 9 组成,数字 1 到 9 代表细胞,细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。
发现不为0就进入dfs,同时把与它相邻的不为0的数字全部换成0,每发现一次就计数。由于输出的是一串数字,所以用char来绘制地图。
#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[101][101];
int ans=0;
void dfs(int x,int y) {
if(x<1||y<1||x>n||y>m) {
return ;
}
if(a[x][y+1]!='0') {
a[x][y+1]='0';
dfs(x,y+1);
}
if(a[x][y-1]!='0') {
a[x][y-1]='0';
dfs(x,y-1);
}
if(a[x+1][y]!='0') {
a[x+1][y]='0';
dfs(x+1,y);
}
if(a[x-1][y]!='0') {
a[x-1][y]='0';
dfs(x-1,y);
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin>>a[i][j];
}
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(a[i][j]!='0') {
a[i][j]=0;
ans++;
dfs(i,j);
}
}
}
printf("%d",ans);
return 0;
}
一个N×M的由非负整数构成的数字矩阵,你需要在其中取出若干个数字,使得取出的任意两个数字不相邻(若一个数字在另外一个数字相邻8个格子中的一个即认为这两个数字相邻),求取出数字和最大是多少。
也就是说取了一个数后,它周围的八个数不可以取,再从其他的数中取数,直到遍历完整个数字矩阵,可以使用dfs,在每一次取数后将周围的八个格子标记为不可取,回溯的时候在取消标记即可。
#include<bits/stdc++.h>
using namespace std;
int mp[10][10],vis[10][10];
int kp[8][2]={1,0,-1,0,0,1,0,-1,1,1,-1,1,1,-1,-1,-1};
int i,j,k,n,m,ans=0,ant=0;
void dfs(int x,int y){
if(y==m+1){
dfs(x+1,1);
return;
}
if(x==n+1){
ant=max(ant,ans);
return;
}
dfs(x,y+1);
if(vis[x][y]==0){
ans+=mp[x][y];
for(k=0;k<8;k++){
++vis[x+kp[k][0]][y+kp[k][1]];
}
dfs(x,y+1);
for(k=0;k<8;k++){
--vis[x+kp[k][0]][y+kp[k][1]];
}
ans-=mp[x][y];
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
memset(mp,0,sizeof(mp));
memset(vis,0,sizeof(vis));
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
scanf("%d",&mp[i][j]);
}
}
ant=0;
dfs(1,1);
printf("%d\n",ant);
}
return 0;
}
有奇怪的一点
++vis[x+kp[k][0]][y+kp[k][1]];
--vis[x+kp[k][0]][y+kp[k][1]];
改成
vis[x+kp[k][0]][y+kp[k][1]]=1;
vis[x+kp[k][0]][y+kp[k][1]]=0;后不知道为什么就行不通了。
就是一个树形结构,每条边对答案的贡献为边两边联通块大小差的绝对值乘上边权,输出边贡献之和。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,cnt,ans;
int i;
int head[1000010],size[1000010];
struct node{
int to,nt,t;
}nn[2000010];
void add(int a,int b,int c){
cnt++;
nn[cnt].to=b;
nn[cnt].nt=head[a];
nn[cnt].t=c;
head[a]=cnt;
}
void dfs(int x,int y){
size[x]=1;
for(i=head[x];i;i=nn[i].nt){
int to=nn[i].to;
if(y==to) continue;
dfs(to,x);
size[x]+=size[to];
ans+=nn[i].t*abs(size[to]*2-n);
}
}
int main(){
scanf("%d",&n);
for(i=1;i<n;i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
dfs(1,0);
printf("%d",ans);
return 0;
}