HDU 6026

题意：就是给你一个连通图，让你删掉一些边后变成一棵树，同时这棵树的根是0号节点，且要满足在树上从0到任意节点的最短距离和原图相等。问总共有多少种删法？

解：这道题需要认识到一点，就是在构建这棵树时，距离远的点只能从距离近的点得到，也就是按照到0的距离依次由近到远的把点插入这棵树当中，最后看有多少种建树的方案就是最后的答案。

先跑一遍dij，把距离从小到大排好，在做一遍dp，注意当一个点插入到树并且成功后，此时这棵树不管有多少种形状，对于后面要插入的点来说，这个树只有一种“形状”，理解好这个就能写了。

  
#include #include #include #include using namespace std;
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
int n;
int e[55][55];
int d[55];
int vis[55];
struct node
{int num;int len;
}p[55];
long long dp[55];
bool cmp(node a, node b)
{return a.len < b.len;
}
void dij(int n)
{memset(d, INF,sizeof(d));memset(vis, 0, sizeof(vis));d[0] = 0;while(1){int v = -1;for(int i = 0; i < n; i ++){if(!vis[i] && ((v == -1) || (d[i] < d[v])))v = i;}if(v == -1)break;vis[v] = 1;for(int i = 0;  i < n; i ++){if(!vis[i]){if(d[i] > d[v] + e[v][i]){d[i] = d[v] + e[v][i];}}}}for(int i = 0; i < n; i ++){p[i].num = i;p[i].len = d[i];}sort(p, p + n, cmp);}
int main()
{//freopen("1.txt", "r", stdin);while (scanf("%d",&n)!=EOF){for (int i=0;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！