解题报告 P1119 灾后重建

题目内容

P1119

大意:给定编号从 1n-1 的村庄,每个村庄都被一定程度上损毁,而公路正常,在 t_i 时间前 i 号村庄不能通过,询问在 t 时间时 x 号和 y 号村庄能不能通车,如果能,最短路径是多少。

解题思路

这题思路真的很妙,让我们对 Floyd 的本质有了更深的理解,至少本蒟蒻是这样觉得的。

回归 Floyd 算法的本质:

for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f[i][j]=min(f[i][j],f[i][k]+f[k][j])

实际上,Floyd 是通过枚举中转点 k 来求得每个点之间的最短路,本质上是一种 dp。

然后,注意到本题中,每个村庄的恢复时间是递增的,且给出的询问的时间也是递增的。而题目让我们求任意两点的最短路,那么也可以抽象成 Floyd。具体的方法就是,由于时间是递增的,所以每到一个村庄恢复的时间点我们就可以让这个村庄成为那个可以用来中转的 k 来更新这一时间的所有最短路。

在这题中,就是使用时间戳,保证回答被询问的时间前信息被更新过即可。注意村庄编号从 0 开始

#include <cstdio>
#include <cctype>
#include <cstring>

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline int min(int a,int b)
{
    return a<b?a:b;
}

const int maxn=205;
int n,m,t[maxn],f[maxn][maxn],q;

inline void floyd(int k)//更新信息的,通过给定可以中转的中转点来进行更新
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    return;
}

int main()
{
    n=read(),m=read();
    memset(f,0x3f,sizeof(f));//初始赋极大值 0x3f 不至于加起来爆int
    for(int i=0;i<n;i++)
        t[i]=read(),f[i][i]=0;
    while(m--)
    {
        int x=read(),y=read(),w=read();
        f[x][y]=f[y][x]=w;//双向边
    }
    q=read();
    int now=0;
    while(q--)
    {
        int x=read(),y=read(),s=read();
        while(t[now]<=s && now<n)//将这一时间前的所有时间信息更新
            floyd(now++);
        if(t[x]>s || t[y]>s || f[x][y]>=0x3f3f3f3f)//如果这一时间时村庄未修复,或者无路线
            printf("-1\n");//输出 -1
        else
            printf("%d\n",f[x][y]);//否则输出最短路即可
    }
    return 0;
}

2019 CSP-J 题解

前言

咕咕咕了好久,终于今天把 T3 的坑给补回来了,于是打算写一波题解。

勿吐槽码风,丑是必然的,毕竟好久前写的代码了。

T1 数字游戏

P5660 数字游戏

大意:给定长度为 8 的 01 串,求 1 的个数

sb 题,考察字符串基本使用,当时好像 2:30 还没到就已经切完了

考场代码:

#include <iostream>
#include <cstdio>
#include <string>
//#define LOCAL

using namespace std;

int main()
{
#ifndef LOCAL
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
#endif
    string s;
    cin>>s;
    int ans=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='1') ans++;
    }
    printf("%d\n",ans);
    return 0;
}

T2 公交换乘

P5661 公交换乘

大意:坐一次地铁可以获取一张有效期 45 分钟的优惠券,可以凭券免费坐票价不超过地铁票价的公交车,优惠票可累积,使用时优先使用最先获得的

模拟即可,这里使用 vector 模拟优惠票的队列,代码并不优美但是能过。

坑点就在于

  • 使用票要使用最先获得的
  • 优惠票用过要删掉

记得当时在考场上发现队列不能用之后还自己研究 vector::erase 的用法

#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
//#define LOCAL
struct ticket{
    int price;
    ll time;
};
vector<ticket> q;

int main()
{
#ifndef LOCAL
    freopen("transfer.in","r",stdin);
    freopen("transfer.out","w",stdout);
#endif
    int n;
    scanf("%d",&n);
    ll ans=0;
    while(n--)
    {
        int type,price;
        ll t;
        scanf("%d %d %lld",&type,&price,&t);
        if(type==0)//如果坐地铁
        {
            ans+=price;//更新答案
            ticket tt={price,t};
            q.push_back(tt);//插入候选队
        }
        else if(type==1)//如果是公交
        {
            while(!(q.empty())&&t-q.front().time>45) q.erase(q.begin());//先删掉超时的优惠票
            bool flag=0;
            for(int i=0;i<q.size();i++)//查询符合标准的第一张优惠票
            {

                if(q[i].price>=price)
                {
                    q.erase(q.begin()+i);//直接删掉
                    flag=1;
                    break;
                }
            }
            if(!flag) ans+=price;//如果不存在就需要付原价
        }
    }
    printf("%lld\n",ans);
    return 0;
}

T3 纪念品

P5662 纪念品

谁叫我太菜,当时考场上骗了 10 分走人,现在看题解才写出正解。

大意:T 天,N 种纪念品,每天不同的纪念品都有不同的价格,小伟一开始有 M 金币,每天可以卖掉手中的纪念品换取金币,买进纪念品花费金币或者什么都不做。在第 T 天一定会卖出手中所有纪念品,求最高收益

分析题意,可以发现需要使用 dp,发现状态貌似很复杂,又可以买进又可以卖出,然而,注意到买进和卖出都可以进行无数次,因此我们可以把所谓一直持有的纪念品看成先将其卖出,又将其买进,效果是一样的,实质上就是每一天都做一次完全背包。

f_{i,j,k} 表示第 i 天,考虑前 j 种物品,手里有 k 金币时,在下一天全部卖出能达到的最大收益,则有方程

f_{i,j,k}=\max(f_{i,j,k},f_{i,j-1,k+p_i,j}+p_{i,j}-p_{i+1,j})

表示如果要了第 j 个物品,那么净收益即为 p_{i,j}-p_{i+1,j},从 f_{i,j-1,k+p_i,j} 转移而来,利用完全背包思想压一下维度然后改循环顺序即可以达到正确结果。

(第一维的天数是可以不要的,第二维的物品也是可以用滚动数组优化掉的,保留第三维即可)

#include <cstdio>
#include <cctype>
#include <cstring>

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline int max(int a,int b)
{
    return a>b?a:b;
}

int n,t,p[105][105],f[10005];

int main()
{
    t=read(),n=read();
    int m=read();
    for(int i=1;i<=t;i++)
        for(int j=1;j<=n;j++)
            p[i][j]=read();
    int ans=m;
    for(int i=1;i<t;i++)
    {
        memset(f,~0x3f,sizeof(f));//先赋负无穷
        f[ans]=ans;//初始值,什么都不干的情况
        for(int j=1;j<=n;j++)//枚举物品,从小到大即为完全背包
            for(int k=ans;k>=p[i][j];k--)//枚举金钱
                f[k-p[i][j]]=max(f[k-p[i][j]],f[k]+p[i+1][j]-p[i][j]);
        int maxn=0;//统计最优答案用
        for(int j=0;j<=ans;j++)
            maxn=max(maxn,f[j]);
        ans=maxn;
    }
    printf("%d\n",ans);
    return 0;
}

T4 加工零件

P5663 加工零件

大意:一个工厂正在生产零件,工人从 1 到 n 标号,某些工人之间有双向传送带。

如果 x 号工人想生产一个被加工到第 L (L \gt 1) 阶段的零件,则所有与 x 号工人有传送带直接相连的工人,都需要生产一个被加工到第 L – 1 阶段的零件(但 x 号工人自己无需生产第 L – 1 阶段的零件)。

如果 x 号工人想生产一个被加工到第 1 阶段的零件,则所有与 x 号工人有传送带直接相连的工人,都需要为 x 号工人提供一个原材料。

给定一些工单,即需要某工人生产某阶段的零件,求 1 号是否需要提供原材料。


先将其抽象成图论问题,以工人为节点,传送带为边来建图。

考虑暴力,虽然一定超时,但还是能给我们一些启示,不难发现暴力就是在看 a 与 1 之间是否存在长度为 L 的路径,同时我们又注意到:如果 L 为奇数,且从 1 到 a 存在一条奇数路径,且最小奇数路径长小于等于 L,那么 1 就必须提供原材料(为什么可以:你可以两个传送带之间来回跳,比如 1->2->1->2->1…,但如果最小的奇数路径大于 L,说明从 aL 个阶段也轮不到 1,就不行)同样的,如果 L 为偶数,且从 1 到 a 存在一条偶数路径,且最小偶数路径长小于等于 L,那么 1 就必须提供原材料。

这就给我们了正解的方法:找到每个点距离 1 点的最小奇数路径与偶数路径即可,这一过程实现可以使用 bfs(因为我当时还没学过最短路),然后判定每一个工单的时候按照奇偶数去找最短奇偶路径是否小于等于工单给定阶段就可以判定 YesNo

当然,我写的考场代码有一个小 bug,就是没有判断 1 点不连通的情况,然而 ccf 的数据没有这种特殊情况,所以也就 A 了这道题

考场代码:

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
//#define LOCAL
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
vector<int> g[100020];//存图
bool vis0[100020],vis1[100020];//bfs用
int minans0[100020],minans1[100020];//存储奇偶最短路
struct node{
    int n,time;
};
queue<node> q;
void bfs()
{
    memset(minans0,inf,sizeof(minans0));
    memset(minans1,inf,sizeof(minans1));
    q.push((node){1,0});
    while(!q.empty())
    {
        int curn=q.front().n;//当前的点
        int nxtc=q.front().time+1;//下一个点会经过的路径长
        q.pop();
        for(int i=0;i<g[curn].size();i++)
        {
            int nxt=g[curn][i];
            if(nxtc%2==0)//如果下一个点是偶数到达
            {
                if(vis0[nxt]==0)//如果未访问
                {
                    vis0[nxt]=1;
                    q.push((node){nxt,nxtc});
                    minans0[nxt]=min(nxtc,minans0[nxt]);//就更新这里的结果
                    //cout<<"no."<<nxt<<" "<<nxtc<<endl;
                }
            }
            if(nxtc%2==1)//反之如果是奇数,也一样
            {
                if(vis1[nxt]==0)
                {
                    vis1[nxt]=1;
                    q.push((node){nxt,nxtc});
                    minans1[nxt]=min(nxtc,minans1[nxt]);
                    //cout<<"no."<<nxt<<" "<<nxtc<<endl;
                }
            }
        }
    }
    return;
}

void add_edge(int u,int v)
{
    g[u].push_back(v);//注意是无向图
    g[v].push_back(u);
    return;
}


int main()
{
#ifndef LOCAL
    freopen("work.in","r",stdin);
    freopen("work.out","w",stdout);
#endif
    int n,m,q;
    scanf("%d %d %d",&n,&m,&q);
    while(m--)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        add_edge(u,v);
    }
    bfs();//预处理
    while(q--)
    {
        int a,l;
        scanf("%d %d",&a,&l);
        bool flag=0;
        if(l%2==0&&vis0[a]==1&&minans0[a]<=l) flag=1;//如果是偶数阶段并且能到达
        if(l%2==1&&vis1[a]==1&&minans1[a]<=l) flag=1;
        if(flag) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

解题报告 P1396 营救

题目内容

一张带权图,求从 st 经过的边中的最大边权的最小值

解题思路

要使最大边权最小,说明是瓶颈生成树,而最小生成树即为瓶颈生成树。故跑一遍 Kruskal,由于 Kruskal 是从小到大枚举边,因此如果当加了某条边后 st 联通了,那么这条边的边权就是最终要的结果了。

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>

using namespace std;

//快读省略

//并查集省略

//边的结构体省略

bool cmp(edge a,edge b)
{
    return a.dist<b.dist;
}

vector<edge> q;
int n,m,s,t;

int kruskal()
{
    sort(q.begin(),q.end(),cmp);
    for(auto &e:q)
    {
        int from=e.from,to=e.to,dist=e.dist;
        if(!u.query(from,to))
            u.uni(from,to);
        if(u.query(s,t))//如果刚好加了这条边之后s和t联通了
            return dist;//说明当前边一定就是最大的了
    }
}

int main()
{
    n=read(),m=read(),s=read(),t=read();
    int u,v,w;
    for(int i=1;i<=m;i++)
    {
        u=read(),v=read(),w=read();
        q.push_back(edge(u,v,w));
    }
    printf("%d\n",kruskal());
    return 0;
}

解题报告 P1347 排序

题目内容

P1347

大意:给定若干个元素的偏序关系,求是否能判定排好序后序列的顺序。

如果根据前 i 个关系可以直接得到,输出序列并直接结束程序。

如果第 i 个关系造成了矛盾,输出 i 并结束程序。

如果根据所有的关系都不能还原序列,输出无法完成。

解题思路

看到偏序关系就想到利用图论建模然后跑拓扑排序,结果30分

说回正题:这题还是需要注意很多地方的,还是先来分析思路。

题目要求的是通过前 i 个来判断,因此我们要根据所有的关系挨个加边然后每加一次边跑一遍拓扑排序,由于 n\le26 所以不需要担心时间问题。

拓扑排序的实现有一些细节:首先显而易见的,如果给出来的偏序关系形成了环,那显然是不可以的,直接返回,判断是否有环的标准是拓扑排序能否遍历完所有给出的点,如果遍历不完,说明图存在环,直接输出矛盾即可。

但是遍历所有点并不代表就能形成完整的排序,有可能给出的是诸如下面的关系:

C

这样拓扑排序仍能遍历整张图,但是遍历的顺序不唯一,表明条件不足,所以我们要记录拓扑排序的深度 step,如果最终的深度刚好等于节点的个数才能判定排序的序列唯一。

还有要注意的就是存储入度的数组要每次重新开,不然会玄学 WA,而且这张图可能有自环与重边,所以存图的时候我使用的是 std::set,方便排除自环和重边的影响。

下面的拓扑排序函数返回值有三种:1 代表条件暂时不足,2 代表可以输出序列,0 代表出现矛盾条件。

注意 IO 的要求,防止被卡空格之类的事情出现,注意细节

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <queue>
#include <set>
using namespace std;

set<int> g[27];//存边
set<int> all;//all是存储当前给出的所有点的集合

struct node
{
    int now,step;//now为当前节点,step为拓扑排序的深度
};

int n,m,depth;
string s;

int topo()
{
    s.clear();
    int ind[27];//重新处理入度数组
    memset(ind,0,sizeof(ind));//不memset的话会玄学
    for(auto i:all)
        for(auto j:g[i])
            ind[j]++;//处理
    queue<node> q;
    int visited=0;
    for(int i=1;i<=n;i++)
        if((!ind[i] && all.count(i)))//既要满足入度为0,也要满足点给出过
            q.push((node){i,1}),s.push_back(i+'A'-1);
    while(!q.empty())
    {
        visited++;
        int now=q.front().now,step=q.front().step;
        q.pop();
        for(auto i:g[now])
        {
            ind[i]--;
            if(!ind[i])
            {
                q.push((node){i,step+1});
                s.push_back(i+'A'-1);
                depth=max(depth,step+1);
            }
        }
    }
    if(depth==n)
        return 2;
    if(visited<all.size())
        return 0;
    return 1;
}

int main()
{
    scanf("%d %d",&n,&m);
    if(m<n-1)//这里是一个小优化:如果给出的关系不足n-1个是铁定完不成的
    {
        printf("Sorted sequence cannot be determined.\n");
        return 0;
    }
    char c[4];
    for(int i=1;i<=m;i++)
    {
        scanf("%s",c);
        int from=c[0]-'A'+1,to=c[2]-'A'+1;
        g[from].insert(to);
        all.insert(from),all.insert(to);
        int x=topo();
        if(x==0)
        {
            printf("Inconsistency found after %d relations.\n",i);
            return 0;
        }
        if(x==2)
        {
            printf("Sorted sequence determined after %d relations: ",i);
            cout<<s<<'.'<<endl;
            return 0;
        }
    }
    printf("Sorted sequence cannot be determined.\n");//如果前两种情况都没发生,那就是第三种了
    return 0;
}

解题报告 P4017 最大食物链计数

题目内容

P4017

大意:给出 mn 种生物的捕食关系,求最大食物链(最左端是不会捕食其他生物的生产者,最右端是不会被其他生物捕食的消费者)的条数。

保证给定的关系没有环

解题思路

一看,无环,想到 DAG,然后又看到最大食物链的定义:

最左端是不会捕食其他生物的生产者,最右端是不会被其他生物捕食的消费者

就想到了最大食物链的左端必然是入度为 0 的点,右端必然是出度为 0 的点,因此使用拓扑排序。

我们设 f_i 为从入度为 0 的所有点到达点 i 的方案数总和,由于拓扑排序是在一个点的信息更新完之后再入队的,所以正确性得到了保证。

具体的做法就是普通的拓扑排序,记录每个点的入度,然后从入度为 0 的点开始,使用顺推,对于处理到的每一个点入度都减一,然后方案数加上去,特别的,如果从队列中取出的这个点的出度为 0,则统计答案。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
using namespace std;

const int maxn=5e3+5,p=80112002;
vector<int> g[maxn];
int n,m,ind[maxn],f[maxn],ans;

inline int read()
{
    int s=0;
    char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
        s=10*s+c-'0',c=getchar();
    return s;
}

void topo()
{
    queue<int> q;
    for(int i=1;i<=n;i++)//先扫一遍点,将入度为 0 的点加进去
        if(!ind[i])
            q.push(i),f[i]=1;//这里的初始状态很重要
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        if(g[now].size()==0)//如果出度为 0
        {
            ans=(ans+f[now])%p;//统计答案
            continue;
        }
        for(auto to:g[now])//遍历这个点的出边
        {
            f[to]=(f[to]+f[now])%p;//更新状态
            ind[to]--;//删边
            if(!ind[to])//如果这个点相连的信息都处理完了
                q.push(to);//入队
        }
    }
    return;
}

int main()
{
    n=read(),m=read();
    int a,b;
    for(int i=1;i<=m;i++)
    {
        a=read(),b=read();
        ind[a]++;//记录入度
        g[b].push_back(a);//加边
    }
    topo();//拓扑排序
    printf("%d\n",ans);
    return 0;
}

解题报告 P4568 [JLOI2011]飞行路线

题目内容

P4568

大意:n 个城市 m 条航线,可以免费掉最多 k 条航线,求从 st 的最少花费。

解题思路

分层图最短路模板,将图分成 k+1 层处理,每层之间照常连航线的边,跨层连免费航线,跑一遍最短路然后统计答案就可以了。每往下一层就相当于免费搭了一次飞机。

spfa 会被卡

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int maxn=1e4+5;

struct edge
{
    int to,dist;
    edge(){}
    edge(int b,int c)
    {
        to=b,dist=c;
    }
};

vector<edge> g[maxn*11];
int n,m,k,s,t;
queue<int> q;
bool vis[maxn*11];//记得空间开够
int d[maxn*11];

void ins(int u,int v,int w)
{
    g[u].push_back(edge(v,w));
    return;
}

void dij()//跑dij
{
    priority_queue<pair<int,int>, vector<pair<int,int> >,greater<pair<int,int> > > q;
    memset(d,0x3f3f3f3f,sizeof(d));
    d[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        int now=q.top().second;
        q.pop();
        if(!vis[now])
        {
            vis[now]=1;
            for(auto &e:g[now])
            {
                if(d[e.to]>d[now]+e.dist)
                {
                    d[e.to]=d[now]+e.dist;
                    q.push(make_pair(d[e.to],e.to));
                }
            }
        }
    }
    return;
}

int main()
{
    scanf("%d %d %d",&n,&m,&k);
    scanf("%d %d",&s,&t);
    register int a,b,c;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        for(int j=0;j<=k;j++)//每层中间连
        {
            ins(a+n*j,b+n*j,c);
            ins(b+n*j,a+n*j,c);
            if(j<k)//跨层连
            {
                ins(a+n*j,b+(j+1)*n,0);
                ins(b+n*j,a+(j+1)*n,0);
            }
        }
    }
    dij();
    int ans=0x3f3f3f3f;
    for(int i=0;i<=k;i++)
        ans=min(ans,d[i*n+t]);
    printf("%d\n",ans);
    return 0;
}

解题报告 P1991 无线通讯网

题目内容

P1991

大意:国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络;

每个边防哨所都要配备无线电收发器;有一些哨所还可以增配卫星电话。

任意两个配备了一条卫星电话线路的哨所(两边都ᤕ有卫星电话)均可以通话,无论他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过 D,这是受收发器的功率限制。收发器的功率越高,通话距离 D 会更远,但同时价格也会更贵。

收发器需要统一购买和安装,所以全部哨所只能选择安装一种型号的收发器。换句话说,每一对哨所之间的通话距离都是同一个 D。你的任务是确定收发器必须的最小通话距离 D,使得每一对哨所之间至少有一条通话路径(直接的或者间接的)。

解题思路

明确题意:p 个哨所,s 个卫星电话,有卫星电话连起来的话就可以无限距离传信息,否则只能用无线收发器,求无线收发器的最小的最大功率。

抽象:一个完全图,顶点就是各个哨所,如果不看卫星电话的话,就是求一个最小生成树,找出他的最大边。但是由于卫星电话可以直接干掉任何距离,所以就一定要考虑这个问题。

具体的解法是求出最小生成树,然后同时干掉生成树的最大的 s-1 条边,因为只有这样才可以使得剩余生成树上的边的最大权值最小。

可以使用 Kruskal 算法,由于一共有 p-1 条边,卫星电话可以解决掉的是前 s-1 条边,由于 Kruskal 枚举的边是从小到大的顺序,因此可以记录枚举的边的数量,当枚举到第 (p-1)-(s-1) 条边即第 p-s 条边的时候就直接停止,直接输出当前边的权值即可。

别脑残写错 dist 函数就行

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const int maxn=50050;

struct unionset
{
    int bin[maxn];
    unionset()
    {
        for(int i=1;i<=maxn;i++)
            bin[i]=i;
    }
    int anc(int x)
    {
        if(bin[x]!=x)
            return bin[x]=anc(bin[x]);
        return bin[x];
    }
    void uni(int x,int y)
    {
        bin[anc(x)]=anc(y);
    }
    bool query(int x,int y)
    {
        return anc(x)==anc(y);
    }
}u;

struct edge
{
    int from,to;
    double dist;
    edge(){}
    edge(int _from,int _to,double _dist)
    {
        this->from=_from;
        this->to=_to;
        this->dist=_dist;
    }
};

double dist(int x1,int y1,int x2,int y2)//欧几里得距离
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

int s,p,x[maxn],y[maxn];
vector<edge> v;

bool cmp(edge a,edge b)
{
    return a.dist<b.dist;
}

void kruskal()
{
    sort(v.begin(),v.end(),cmp);
    int cnt=0;//统计当前枚举的边的数量
    for(auto e:v)
    {
        if(!u.query(e.from,e.to))
        {
            u.uni(e.from,e.to);
            cnt++;
            if(cnt==p-s)//如果当前到了第 p-s 条边
            {
                printf("%.2f\n",e.dist);//就直接输出跑路
                return;
            }
        }
    }
}

int main()
{
    scanf("%d %d",&s,&p);
    for(int i=1;i<=p;i++)
        scanf("%d %d",x+i,y+i);
    for(int i=1;i<=p;i++)//完全图的边枚举
        for(int j=i+1;j<=p;j++)//卡常,减少循环的次数
        {
            v.push_back(edge(i,j,dist(x[i],y[i],x[j],y[j])));
            v.push_back(edge(j,i,dist(x[i],y[i],x[j],y[j])));
        }
    kruskal();
    return 0;
}

解题报告 P2330 [SCOI2005]繁忙的都市

题目内容

P2330

大意:城市 C 是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。城市 C 的道路是这样分布的:城市中有n个交叉路口,有些交叉路口之间有道路相连,两个交叉路口之间最多有一条道路相连接。这些道路是双向的,且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值,分值越小表示这个道路越繁忙,越需要进行改造。但是市政府的资金有限,市长希望进行改造的道路越少越好,于是他提出下面的要求:

  1. 改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
  2. 在满足要求1的情况下,改造的道路尽量少。
  3. 在满足要求1、2的情况下,改造的那些道路中分值最大的道路分值尽量小。

输出两个整数 s, max,表示你选出了几条道路,分值最大的那条道路的分值是多少。

解题思路

把所有的交叉路口直接或间接的连通起来

生成树

改造的那些道路中分值最大的道路分值尽量小

瓶颈生成树

由于 MST 一定是瓶颈生成树,所以直接跑一遍最小生成树即可。只是输出的时候要输出选出的边的条数和最大的边权,跑生成树的时候记得记录最大值,最后输出点数减一即可。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn=305;

struct unionset
{
    int bin[maxn];
    unionset()
    {
        for(int i=1;i<=maxn;i++)
            bin[i]=i;
    }
    int anc(int x)
    {
        if(bin[x]!=x)
            return bin[x]=anc(bin[x]);
        return bin[x];
    }
    void uni(int x,int y)
    {
        bin[anc(x)]=anc(y);
    }
    bool query(int x,int y)
    {
        return anc(x)==anc(y);
    }
}u;

struct edge
{
    int from,to,dist;
    edge(){}
    edge(int _from,int _to,int _dist)
    {
        this->from=_from;
        this->to=_to;
        this->dist=_dist;
    }
};

int n,m;
vector<edge> v;

bool cmp(edge a,edge b)
{
    return a.dist<b.dist;
}

void kruskal()
{
    int _max=-0x3f3f3f3f;
    sort(v.begin(),v.end(),cmp);
    for(auto e:v)
    {
        if(!u.query(e.from,e.to))
        {
            u.uni(e.from,e.to);
            _max=max(_max,e.dist);//记录的是最长边的大小
        }
    }
    printf("%d %d\n",n-1,_max);
    return;
}

int main()
{
    scanf("%d %d",&n,&m);
    int x,y,c;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        v.push_back(edge(x,y,c));
        v.push_back(edge(y,x,c));
    }
    kruskal();
    return 0;
}

解题报告 P1546 最短网络 Agri-Net

题目内容

FJ 已经给他的农场安排了一条高速的网络线路,他想把这条线路共享给其他农场。为了用最小的消费,他想铺设最短的光纤去连接所有的农场。

你将得到一份各农场之间连接费用的列表,你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过 10^5

解题思路

农场之间要联通,使得光缆最小,所以要用最小生成树,跑一遍 Kruskal 就可以了。

代码:

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn=105;

struct unionset
{
    int bin[maxn];
    unionset()
    {
        for(int i=1;i<=maxn;i++)
            bin[i]=i;
    }
    int anc(int x)
    {
        if(bin[x]!=x)
            return bin[x]=anc(bin[x]);
        return bin[x];
    }
    void uni(int x,int y)
    {
        bin[anc(x)]=anc(y);
    }
    bool query(int x,int y)
    {
        return anc(x)==anc(y);
    }
}u;

struct edge
{
    int from,to,dist;
    edge(){}
    edge(int _from,int _to,int _dist)
    {
        this->from=_from;
        this->to=_to;
        this->dist=_dist;
    }
};

int n;
vector<edge> v;

bool cmp(edge a,edge b)
{
    return a.dist<b.dist;
}

int kruskal()
{
    int ans=0;
    sort(v.begin(),v.end(),cmp);
    for(auto e:v)
    {
        if(!u.query(e.from,e.to))
        {
            u.uni(e.from,e.to);
            ans+=e.dist;
        }
    }
    return ans;
}

int main()
{
    scanf("%d",&n);
    int tmp;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&tmp);
            if(tmp)
                v.push_back(edge(i,j,tmp));
        }
    printf("%d\n",kruskal());
    return 0;
}

解题报告 P1073 最优贸易 【NOIP2009TGT3】

题目内容

P1073

大意:一个商人在一个国家(n个城市m条路)游玩,每到一个城市可以选择买入或者卖出物品,贸易只进行一次,从1出发,到n结束,求最大获利

解题思路

嗯,遇到这种贸易问题,可以抽象成图来看。

商人完整的贸易过程分为三个部分:出发到买入,买入到卖出,卖出到结束

可以使用分层图的思想,将整张图复制为三份,然后在第一层到第二层每个点之间连边,边权为该点的物价,在第二层到第三层之间每个点连边,边权为物价的相反数。然后每一层中间城市的道路边权都为0,因为在城市间移动不需要费用。

对于商人的移动,层内的对应的是正常移动,跨层的是买卖操作,求出从第一层的1号节点到第三层的n节点的最短路再取相反数即可。

代码细节

首先,由于负权边的存在,最短路的算法要使用SPFA,实现的细节不再赘述。

其次,分层图的表示,使用的是1\~n号代表第一层,n+1\~2n号代表第二层,2n+1~3n号代表第三层。对于每一个节点编号为i,权值为c_i的节点,需要添加边(i,n+i)=c_i(n+i,2n+i)=-c_i

至于城市间道路的添加,需要在三层图上都分别添加,注意双向边的存在。

多层图的节点切记不是2*n或3*n,我第一次打的时候就因为这个spfa陷入了死循环

注意如果商人不能获得优惠的话就不进行贸易输出0

代码

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int maxn=1e5+5;

struct edge
{
    int from,to,dist;
    edge(){}
    edge(int u,int v,int w)
    {
        from=u,to=v,dist=w;
    }
};

vector<edge> g[maxn*3];//开空间的时候maxn要乘上3
queue<int> q;
bool inq[maxn*3];
int d[maxn*3];
int n,m;

void ins(int u,int v,int w)
{
    g[u].push_back(edge(u,v,w));
    return;
}

int spfa()
{
    memset(d,0x3f3f3f3f,sizeof(d));
    q.push(1);
    inq[1]=true;
    d[1]=0;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        inq[now]=false;
        for(auto &e:g[now])
        {
            int to=e.to, dist=e.dist;
            if(d[now]+dist<d[to])
            {
                d[to]=d[now]+e.dist;
                if(!inq[to])
                {
                    inq[to]=true;
                    q.push(to);
                }
            }
        }
    }
    return d[n+(n<<1)];//返回值是到终点的最小值
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int k;
        scanf("%d",&k);
        ins(i,i+n,k);//记得加边
        ins(i+n,i+(n<<1),-k);//第二,三层之间边权是负的
    }
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        ins(u,v,0);//三层边都要加上
        ins(u+n,v+n,0);
        ins(u+(n<<1),v+(n<<1),0);
        if(w==2)//如果是双向边的话也要加上
        {
            ins(v,u,0);
            ins(v+n,u+n,0);
            ins(v+(n<<1),u+(n<<1),0);
        }
    }
    int ans=spfa();
    //这里如果ans小于0,说明能获利,否则不能获利就不进行贸易,输出0
    printf("%d\n",ans<0?-ans:0);
    return 0;
}