Home PAT Top Level 1001 Battle Over Cities - Hard Version
Post
Cancel

PAT Top Level 1001 Battle Over Cities - Hard Version

Link

这道题巧妙的地方在于, 结构体要存储边而不是点.

将可以使用的边和需要修理的边分开存储. 因为我们是要对这 n 个城市逐个进行分析, 从而找到权值和最大的那个 (些) 城市. 对于不同的城市而言, 去掉这个城市和与其连接的所有边之后, 剩下的图的连通性很有可能会变. 因此, 我们需要对每个城市都进行一次并查集的操作, 得到当前图的连通性, 这就只需要用 in use 的路来判断. 接下来, 就是修理被摧毁的路来使得当前图连通. 这也是用到贪心思想的地方: 对需要修理的边权值从小到大排序.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
int n,m,father[510],cost[510];
struct node{
    int c1,c2,cost;
    bool operator<(const node& x)const{
        return cost<x.cost;
    }
};
vector<node>use,rep;
vector<int>ans;
int findFather(int x){
    while(x!=father[x]) x=father[x]=father[father[x]];
    return x;
}
int getNum(){
    int cnt=0;
    for(int i=1;i<=n;++i)
        if(father[i]==i)
            cnt++;
    return cnt;
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int c1,c2,cost,stat;
        scanf("%d%d%d%d",&c1,&c2,&cost,&stat);
        if(stat) use.push_back({c1,c2,cost});
        else rep.push_back({c1,c2,cost});
    }
    sort(rep.begin(),rep.end());
    for(int i=1;i<=n;++i){
        for(int i=1;i<=n;++i) father[i]=i;
        for(node &v:use){
            int f1=findFather(v.c1),f2=findFather(v.c2);
            if(v.c1!=i&&v.c2!=i&&f1!=f2){
                father[f1]=f2;
            }
        }
        for(node &v:rep){
            int f1=findFather(v.c1),f2=findFather(v.c2);
            if(v.c1!=i&&v.c2!=i&&f1!=f2){
                father[f1]=f2;
                cost[i]+=v.cost;
            }
        }
        if(getNum()>2) cost[i]=INT_MAX;
    }
    int maxv=0;
    for(int i=1;i<=n;++i)
        if(cost[i]>maxv){
            maxv=cost[i];
            ans.clear();
            ans.push_back(i);
        }else if(cost[i]==maxv) ans.push_back(i);
    if(maxv==0) printf("0");
    else{
        for(int i=0;i<ans.size();++i)
            printf("%s%d",(i==0?"":" "),ans[i]);
    }
    return 0;
}
This post is licensed under CC BY 4.0 by the author.