2018/11/16 集训队周五第五次测试赛补题题解

这次基本提高组的题了。。。

A 无线网路发射器选址

这个题的数据有点水，直接两次三个for即可。第一次三个for是找到最大值，第二次三个for是寻找个数

完整代码

#include <bits/stdc++.h>
using namespace std;
struct node
{
  int x,y,sum;
}G[100];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int d,maxn=-1,js=0;
  cin>>d;
  int n;
  cin>>n;
  for(int i=0;i<n;i++)
  cin>>G[i].y>>G[i].x>>G[i].sum;
  for(int i=0;i<=128;i++)
  for(int j=0;j<=128;j++)
  {
    int ans=0;
    for(int k=0;k<n;k++)
    {
      if(G[k].x>=i-d&&G[k].x<=i+d&&G[k].y>=j-d&&G[k].y<=j+d)
      ans+=G[k].sum;
    }
    maxn=max(maxn,ans);
  }
  for(int i=0;i<=128;i++)
  for(int j=0;j<=128;j++)
  {
    int ans=0;
    for(int k=0;k<n;k++)
    {
      if(G[k].x>=i-d&&G[k].x<=i+d&&G[k].y>=j-d&&G[k].y<=j+d)
      ans+=G[k].sum;
    }
    if(ans==maxn)
    js++;
  }
  cout<<js<<" "<<maxn;
}

C 寻找道路

一眼看上去不是spfa的裸题吗，实际上并不是。。。具体解释在另一个题解中

完整代码

#include <bits/stdc++.h>
using namespace std;
struct node
{
  int to,cost;
};
map<long long,long long> vis,bk,bk1,dis,bk2;
queue<int> q,qq;
vector <node> G1[10005];
vector <node> G2[10005];
const int inf=INT_MAX;
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,m;
  cin>>n>>m;
  while(m--)
  {
    int t1,t2;
    cin>>t1>>t2;
    G1[t2].push_back((node){t1,1});
    G2[t1].push_back((node){t2,1});
  }
  int s,e;
  cin>>s>>e;
  for(int i=1;i<=n;i++)
  dis[i]=i==s?0:inf;
  qq.push(e);
  bk2[e]=1;
  while(qq.size())
  {
    int f=qq.front();
    qq.pop();
    bk[f]=1;
    vis[f]=1;
    for(int i=0;i<G1[f].size();i++)
    {
        vis[G1[f][i].to]=1;
        bk[G1[f][i].to]=1;
        if(!bk2[G1[f][i].to])
        {
          bk2[G1[f][i].to]=1;
          qq.push(G1[f][i].to);
        }
    }
  }
  for(int i=1;i<=n;i++)
  {
    if(!vis[i])
    for(int j=0;j<G1[i].size();j++)
    if(vis[G1[i][j].to])
    bk[G1[i][j].to]=0;
  }
  q.push(s);
  while(q.size())
  {
    int p=q.front();
    q.pop();
    bk1[p]=0;
    if(bk[p])
    {
      for(int i=0;i<G2[p].size();i++)
      {
        if(dis[G2[p][i].to]>dis[p]+G2[p][i].cost)
        {
          dis[G2[p][i].to]=dis[p]+G2[p][i].cost;
          if(!bk1[G2[p][i].to])
          {
            bk1[G2[p][i].to]=1;
            q.push(G2[p][i].to);
          }
        }
      }
    }
   }
  if(dis[e]<INT_MAX)
  cout<<dis[e];
  else
  cout<<-1;
}