hdu oj 1102（Kruskal）

分析： 已经有n个村修好了路，问打通所有村庄的最小生成树，拿merge中的mark判断一下是否在树中

#include
#include
#include
#include 
#define maxn 110
using namespace std;struct road{int x, y, dist;road(int ix, int iy, int idist){x = ix;y = iy;dist = idist;}
};int n,roads,length;
vector vec;int pre[maxn];
bool yes[maxn][maxn];void init(int n){for (int i = 1; i <= n; ++i)pre[i] = i;	
}int find(int v)
{int t1,t2=v;while(v!=pre[v]) v=pre[v];while(pre[t2]!=v){t1=pre[t2];pre[t2]=v;t2=t1;}return v;
}bool merge(int x, int y){int fy = find(y);int fx = find(x);bool mark = false;if (fx != fy){pre[fx] = fy;mark = true;}return mark;
}bool cmp(road a, road b)
{return a.dist < b.dist;}int main(){int dist, t, x, y;while (cin>>n){vec.clear();memset(yes, 0, sizeof(yes));for (int i = 1; i <= n; ++i){for (int j = 1; j <= n; ++j){scanf("%d", &dist);if (i == j || i > j)continue;//重复的路径不进行添加vec.push_back(road(i, j, dist));}}sort(vec.begin(), vec.end(), cmp);init(n);scanf("%d", &t);while (t--){scanf("%d %d", &x, &y);merge(x, y);yes[x][y] = true;}length = 0;vector::iterator it;for (it=vec.begin();it!=vec.end();++it){x = (*it).x;y = (*it).y;dist = (*it).dist;if (yes[x][y])continue;if (merge(x, y))length += dist;}printf("%d\n", length);}return 0;
}

看的iaccepted大佬的

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