湖北网站建设,手机网站菜单网页怎么做的,国家企业信用公示信息系统官网,深圳建站推广本题链接#xff1a;登录—专业IT笔试面试备考平台_牛客网
题目#xff1a;
样例#xff1a; 输入 3 4
1 2 3 1
1 2 2 0
1 3 1 0
2 3 3 0 输出 2 1 3 思路#xff1a; 由题意#xff0c;这里建造的城市需要修路#xff0c;且每个城市之间可以联通#xff0c;且 是 1 …本题链接登录—专业IT笔试面试备考平台_牛客网
题目
样例
输入 3 4
1 2 3 1
1 2 2 0
1 3 1 0
2 3 3 0
输出 2 1 3 思路 由题意这里建造的城市需要修路且每个城市之间可以联通且 是 1 的标记一定有该方案0 可自主选择该修路方案问最少花费修路费用。
根据题干 ‘每个城市之间可以联通’ 相当于 每个结点都需要遍历一遍这个修路就是边权。
这里只是多了一个 标记需要优先选择根据数据范围我们还是用 Kruskal 算法即可。
代码详解如下
#include iostream
#include vector
#include queue
#include cstring
#include algorithm
#include unordered_map
#define endl \n
#define YES puts(YES)
#define NO puts(NO)
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,Ofast,inline)
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N 2e6 10;int n,m;struct Edge
{int a,b,w,p,id;// 定义排序规则标记 1 的为优先选择方案// 之后排序 最小花费的边权为 优先可选择的方案inline bool operator(const Edget)const{if(p ! t.p) return p t.p;return w t.w;}
}edge[N];umapint,intr; // 存储集合所对应的连接点// 查找对应的城市 根节点函数
inline int Find(int x)
{int t x;while(x ! r[x]) x r[x];r[t] x;return x;
}vectorintplan;
inline bool Kruskal()
{// 排序好优先选择的方案sort(edge 1,edge m 1);// 初始化城市点的根节点为自身for(int i 0;i n;i) r[i] i;int cnt 0; // cnt 用于记录修路的数量// 遍历所有方案for(int i 1;i m;i){// 获取需要修路的对应两个城市int a edge[i].a;int b edge[i].b;// 查找对应两个城市的根节点a Find(a),b Find(b);if(edge[i].p || a ! b){// 如果这两个城市之间没有连接过// 或者它们是必选方案那么将它们连接起来r[a] b;// 累加方案数plan.emplace_back(edge[i].id);cnt; // 累加可以修的路数量}}// 如果所修的路无法将所有城市联通返回 falseif(cnt n - 1) return false;return true; // 否则返回 true
}// 打印方案数函数
inline void PrintPlan()
{cout plan.size() endl;for(int i : plan){cout i ;}
}inline void solve()
{// 输入各个信息cin n m;for(int i 1;i m;i){int a,b,w,p;cin a b w p;// 存储好方案edge[i] {a,b,w,p,i};}// 开始克鲁斯卡尔算法判断是否有解并输出对应答案if(Kruskal()) PrintPlan();else puts(-1);
}int main()
{
// freopen(a.txt, r, stdin);IOS;int _t 1;
// cin _t;while (_t--){solve();}return 0;
}
最后提交
