【HDU6026】Deleting Edges

题意

有一个n个节点的无向图，结点编号从0-n-1，每条边的长度时1to9的一个正整数。现在要删除一些边(或者不删)，使得到的新图满足下面两个要求。

1.
新图是一颗树有n-1条边
2.
对于每个结点v（0ton-1）从0到v的距离要等于原图上从0到v的最短路

现在计算有多少种不同的图满足上面两个条件

分析

统计每个点可以到达最短路的入度值，然后相乘。这个题因为spfa写错了调了老久···

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <iostream>

 #include <queue>

 using namespace std;

 const int INF=;

 const int maxn=;

 const int MOD=;

 int n;

 char g[maxn][maxn];

 int G[maxn][maxn];

 int d[maxn],vis[maxn];

 long long in[maxn];

 long long ans;

 void spfa(){

     memset(vis,,sizeof(vis));

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

     queue<int>q;

     q.push();vis[]=;

     d[]=;

     while(!q.empty()){

         int u=q.front();q.pop();

         vis[u]=;

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

             if(G[u][i]){

                 if(d[i]>=d[u]+G[u][i]){

                     d[i]=d[u]+G[u][i];

                     if(!vis[i]){

                       vis[i]=;

                       q.push(i);

                     }

                 }

             }

         }

     }

     return;

 }

 int main(){

     while(scanf("%d",&n)!=EOF){

         memset(G,,sizeof(G));

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

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

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

             }

         }

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

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

                 G[i][j]=g[i][j]-'';

             }

         }

         spfa();

         memset(in,,sizeof(in));

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

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

                 if(i!=j){

                     if(G[i][j]&&d[j]==d[i]+G[i][j]){

                         in[j]++;

                     }

                 }

             }

         }

         ans=;

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

             if(in[i])

             ans=(ans%MOD*in[i]%MOD)%MOD;

         }

         printf("%lld\n",ans);

     }

 return ;

 }

巴特西

【HDU6026】Deleting Edges

最新文章

热门文章