找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 4432|回复: 1
收起左侧

[米群网刷题小分队] [PAT-TOP] 1001 Battle Over Cities - Hard Version

[复制链接]
发表于 1-21-2016 12:17 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
1001  Battle Over Cities - Hard Version
N个城市,之前有道路相连,有些道路是坏的,修路需要代价。如果一个城市被占领,则所有和它关联的道路都关闭。目标是:选择最重要的(若干)城市——如果它被占领,我们需要很大的修路代价把其他城市连起来。

分析: 问题虽然说了原来图保证连通,但有可能原来就是一个树了,这样占领一些城市,可能会导致,我们根本无法连接剩余城市,这种代价要按照无穷大计算…… 坑就在这里。这个题说白了就是一个kruskal算法的最小生成树问题。 Top level也不太难。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <string>
  4. #include <vector>
  5. #include <algorithm>

  6. using namespace std;

  7. struct node {
  8. int x;
  9. int y;
  10. int c;
  11. };

  12. int f[505], num[505];
  13. vector<node> e;

  14. bool cmp(const node &x, const node &y) {
  15.         return x.c < y.c;
  16. }

  17. int getf(int x) {
  18.         return (f[x] == x)?x:(f[x] = getf(f[x]));
  19. }

  20. bool make(int x,int y) {
  21.         if ((x = getf(x)) == (y = getf(y))) {
  22.                 return false;
  23.         }
  24.         if (num[x] < num[y]) {
  25.                 f[x] = y;
  26.                 num[y] += num[x];
  27.         }
  28.         else {
  29.                 f[y] = x;
  30.                 num[x] += num[y];
  31.         }
  32.         return true;
  33. }

  34. int main() {
  35. int n, m;
  36.         scanf("%d%d",&n,&m);
  37.         for (int i = 0; i < m; ++i) {
  38.                 int x, y, c, p;
  39.                 scanf("%d%d%d%d",&x, &y, &c, &p);
  40.                 node temp;
  41.                 temp.x = x - 1;
  42.                 temp.y = y - 1;
  43.                 temp.c = p?0:c;
  44.                 e.push_back(temp);
  45.         }
  46.         sort(e.begin(), e.end(), cmp);
  47.         vector<int> answer;
  48.         int now = 1;
  49.         bool mark = false;
  50.         for (int i = 0; i < n; ++i) {
  51.                 int need = n - 2;
  52.                 int cost = 0;
  53.                 for (int j = 0; j < n; ++j) {
  54.                         f[j] = j;
  55.                         num[j] = 1;
  56.                 }
  57.                 for (int j = 0; (need > 0) && (j < m); ++j) {
  58.                         if ((e[j].x != i) && (e[j].y != i) && make(e[j].x, e[j].y)) {
  59.                                 --need;
  60.                                 cost += e[j].c;
  61.                         }
  62.                 }
  63.                 if (need > 0) {
  64.                         if (!mark) {
  65.                                 mark = true;
  66.                                 answer.clear();
  67.                         }
  68.                         answer.push_back(i);
  69.                 }
  70.                 else if (mark) {
  71.                 }
  72.                 else if (cost > now) {
  73.                         now = cost;
  74.                         answer.resize(1);
  75.                         answer[0] = i;
  76.                 }
  77.                 else if (cost == now) {
  78.                         answer.push_back(i);
  79.                 }
  80.         }
  81.         if (answer.empty()) {
  82.                 puts("0");
  83.         }
  84.         else {
  85.                 for (int i = 0; i < answer.size(); ++i) {
  86.                         if (i) {
  87.                                 putchar(' ');
  88.                         }
  89.                         printf("%d",answer【i】 + 1);
  90.                 }
  91.                 puts("");
  92.         }
  93.         return 0;
  94. }
复制代码



本帖被以下淘专辑推荐:

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

0

主题

0

精华

1

积分

新米人

Rank: 1

积分
1
发表于 1-22-2016 06:45 PM | 显示全部楼层
感谢cpcs分享~~~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表