[fzu 2271]不改变任意两点最短路至多删的边数

题目链接：http://acm.fzu.edu.cn/problem.php?pid=2271

题目中说每条边的边权都是[1,10]之间的整数，这个条件非常关键！以后一定要好好读题啊……

做10次循环，第i次循环加边权为i的边，如果这条边小于当前两点间最短路，就加边，更新两点距离；否则就不要这个边。

每次循环过后，做一次Floyd。至多做10次Floyd。

有一个猜想，比赛的时候就想到了：从小到大加边，如果这个边比这两点之间的最短距离小，就要，否则就不要。这个猜想不会证……

但是只想到了每次更改距离以后都做一次Floyd，没有想到一块加权值相同的边，然后再做Floyd。这里就假设上面的猜想是正确的，然后证明一下统一做Floyd的方法也是正确的吧。

假设dis[][]维护着两点间的最短距离。

首先，对于未经优化的方法，如果有一条边加入了，说明这条边的权比两点的最短路短，如果没有随时维护，只维护到了上次权值不同的最后一条边，由于dis随着维护是越来越小的，所以现在的dis也显然大于这个边权，因此对于没有优化的方法，这条边会加进去。

然后，对于未经优化的方法，如果有一条边没有加入，说明这条边的权w不比两点的最短路短，如果没有随时维护，只维护到了上次权值不同的最后一条边，由于用[1,w-1]的边构成的最短路已经得到，假设这条权值是w的边在优化后会加入，也就是说当前的dis>w，而优化以前没有加入，说明dis'<=w，所以意思就是，加入了一些权值为w的边以后，dis变得<=w了，那这个dis'只能是=w了。既然是权值为w的最短路，要么是用权值为w的边得到的，那此时dis应该也=w了，因为每遇到一个w的边都会更新距离。要么是用[1,w-1]的边构成的，那这个在[1,w-1]之后就应该已经维护出来了。这两种情况都与dis>w矛盾。所以假设失败，这条边在优化以后还是不会加入。

所以加不加入在优化前后是一样的。

#include<cstdio>

#include<cstring>

const int maxn=;

const int maxm=;

const int INF=0x3f3f3f3f;

struct Edge

{

    int u,v,w;

}edge[maxm];

int dis[maxn][maxn];

int main()

{

    int t;

    scanf("%d",&t);

    for (int cas=;cas<=t;cas++)

    {

        int n,m;

        scanf("%d%d",&n,&m);

        for (int i=;i<m;i++)

        {

            scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);

        }

        memset(dis,INF,sizeof(dis));

        for (int i=;i<=n;i++) dis[i][i]=;

        int ans=;

        for (int z=;z<=;z++)

        {

            for (int e=;e<m;e++)

            {

                if (edge[e].w==z)

                {

                    int u=edge[e].u;

                    int v=edge[e].v;

                    if (z<dis[u][v])

                    {

                        dis[u][v]=z;

                        dis[v][u]=z;

                        ans++;

                    }

                }

            }

            for (int k=;k<=n;k++)

                for (int i=;i<=n;i++)

                    for (int j=;j<=n;j++)

                        if (dis[i][k]+dis[k][j]<dis[i][j])

                            dis[i][j]=dis[i][k]+dis[k][j];

        }

        printf("Case %d: %d\n",cas,m-ans);

    }

    return ;

}

另外还有一种更神的做法，只需要做一次Floyd。

首先，删掉重边和自环。然后剩下的边做一次Floyd，在做的过程中被松弛过的边都可以删去。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

const int INF=0x3f3f3f3f;

int G[maxn][maxn];

int dis[maxn][maxn];

bool vis[maxn][maxn];

int main()

{

    int t;

    scanf("%d",&t);

    for (int cas=;cas<=t;cas++)

    {

        memset(G,INF,sizeof(G));

        memset(dis,INF,sizeof(dis));

        memset(vis,false,sizeof(vis));

        int n,m;

        scanf("%d%d",&n,&m);

        int ans=;

        for (int i=;i<m;i++)

        {

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            if (G[u][v]<INF||u==v) ans++;

            if (w<G[u][v]&&u!=v) G[u][v]=G[v][u]=w;

        }

        for (int i=;i<=n;i++)

            for (int j=;j<=n;j++)

                dis[i][j]=G[i][j];

        for (int k=;k<=n;k++)

            for (int i=;i<=n;i++)

                for (int j=;j<=n;j++)

                {

                    if (dis[i][k]+dis[k][j]<=dis[i][j])

                    {

                        dis[i][j]=dis[i][k]+dis[k][j];

                        vis[i][j]=true;

                    }

                }

        for (int i=;i<=n;i++)

            for (int j=i+;j<=n;j++)

            {

                if (vis[i][j]&&G[i][j]!=INF) ans++;

            }

        printf("Case %d: %d\n",cas,ans);

    }

    return ;

}

巴特西

[fzu 2271]不改变任意两点最短路至多删的边数

最新文章

热门文章