TTTTTTTTTTT 400D Dima and Bacteria 细菌最短路

题意：题目大意：给出n，m和k，表示有n个细菌，m种仪器和k种细菌，给出k种细菌的数量ci，然后每个细菌按照种类排成一排（所以有第i种细菌的序号从∑（1≤j≤i-1）cj + 1 到∑（1≤j≤i）cj）；接下来给出m种仪器，有u，v，x三个值，表示说从可以在第u，v号细菌之间移动能量，代价为x。请帮助博士判断说这些细菌是否正确，正确的前提条件是说同种细菌之间移动能量为0，如果正确的话，给出两两细菌（种类）间移动能量的最小值。

AC代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <queue>

#include <stack>

#include <map>

#include <algorithm>

#include <set>

using namespace std;

typedef long long ll;

typedef unsigned long long Ull;

#define MM(a,b) memset(a,b,sizeof(a));

const double eps = 1e-10;

const int inf = 0x3f3f3f3f;

const double pi=acos(-1);

const int mod=100000000;

struct edge{

   int to,c;

};

vector<edge> G[100600];

int c[100600],f[100600],be[100600],dist[600][600],n,m,k;

void add_edge(int u,int v,int c)

{

    G[u].push_back((edge){v,c});

    G[v].push_back((edge){u,c});

}

int findr(int u)

{

    if(f[u]!=u)

        f[u]=findr(f[u]);

    return f[u];

}

bool legal()

{

    for(int i=1;i<=k;i++)

    {

        int r=findr(c[i-1]+1);

        for(int j=c[i-1]+2;j<=c[i];j++)

            if(r!=findr(j)) return false;

    }

    return true;

}

int main()

{

    while(~scanf("%d %d %d",&n,&m,&k))

    {

        for(int i=1;i<=n;i++) {G[i].clear();f[i]=i;}

        for(int i=1;i<=k;i++)

            {

                scanf("%d",&c[i]);

                c[i]+=c[i-1];

                for(int j=c[i-1]+1;j<=c[i];j++)

                    be[j]=i;

            }

        MM(dist,inf);

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

            {

                int u,v,c;

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

                add_edge(u,v,c);

                if(!c)

                {

                   int ru=findr(u);

                   int rv=findr(v);

                   if(ru!=rv) f[rv]=ru;

                }

            }

        if(!legal()) {printf("No\n");continue;};

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

          for(int j=0;j<G[i].size();j++)

           {

            int u=i,v=G[i][j].to;

            if(dist[be[u]][be[v]]>G[i][j].c)

               dist[be[v]][be[u]]=dist[be[u]][be[v]]=G[i][j].c;

           }

        for(int w=1;w<=k;w++)

        for(int i=1;i<=k;i++)

        for(int j=1;j<=k;j++)

            dist[i][j]=min(dist[i][j],dist[i][w]+dist[w][j]);

        printf("Yes\n");

        for(int i=1;i<=k;i++)

        for(int j=1;j<=k;j++)

            {

                if(i==j)

                  printf("0 ");

                else if(dist[i][j]==inf)

                  printf("-1 ");

                else

                  printf("%d ",dist[i][j]);

               if(j==k)

                  printf("\n");

            }

    }

    return 0;

}

　　并查集+floyd

wa代码，好好查错：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <queue>

#include <stack>

#include <map>

#include <algorithm>

#include <set>

using namespace std;

typedef long long ll;

typedef unsigned long long Ull;

#define MM(a,b) memset(a,b,sizeof(a));

const double eps = 1e-10;

const int inf = 0x3f3f3f3f;

const double pi=acos(-1);

const int mod=100000000;

struct edge{

   int to,c;

};

vector<edge> G[100005];

int c[100005],f[100005],n,m,k;

void add_edge(int u,int v,int c)

{

    G[u].push_back((edge){v,c});

    G[v].push_back((edge){u,c});

}

int findr(int u)

{

    if(f[u]!=u) return findr(f[u]);

}

bool legal()

{

    for(int i=1;i<=k;i++)

    {

        int r=findr(c[i-1]+1);

        for(int j=c[i-1]+2;j<=c[i];j++)

            if(r!=findr(j)) return false;

    }

    return true;

}

int main()

{

    while(~scanf("%d %d %d",&n,&m,&k))

    {

        for(int i=1;i<=n;i++) {G[i].clear();f[i]=i;}

        for(int i=1;i<=k;i++) {scanf("%d",&c[i]);c[i]+=c[i-1];}

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

            {

                int u,v,c;

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

                add_edge(u,v,c);

                if(!c)

                {

                   int ru=findr(u);

                   int rv=findr(v);

                   if(ru!=rv) f[rv]=ru;

                }

            }

        if(!legal()) {printf("No\n");continue;};

    }

    return 0;

}

巴特西

TTTTTTTTTTT 400D Dima and Bacteria 细菌最短路

最新文章

热门文章

巴特西

TTTTTTTTTTT 400D Dima and Bacteria 细菌 最短路

最新文章

热门文章

TTTTTTTTTTT 400D Dima and Bacteria 细菌最短路