用什么网站做动感相册,360建筑网是什么,仿站仿淘宝客网站视频教程,百度新闻发布正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP1525 题目大意
有n个罪犯#xff0c;罪犯有些关系#xff0c;就是(i,j,c)(i,j,c)表示罪犯i和罪犯j在同一个监狱会造成c的破坏#xff0c;有两座监狱#xff0c;要求分配的使得最大的破坏最小。 解…正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP1525 题目大意
有n个罪犯罪犯有些关系就是(i,j,c)(i,j,c)(i,j,c)表示罪犯i和罪犯j在同一个监狱会造成c的破坏有两座监狱要求分配的使得最大的破坏最小。 解题思路
先按照c排序然后就从大到小处理直到无法处理。 我们可以用并查集表示在一个监狱中然后用敌人的敌人是朋友来合并。记录每个罪犯的敌人的根然后每次合并就将他的敌人和他的敌人合并在一起直到发现一个人即是某人的敌人有是某人敌人的敌人就输出。 code
#includecstdio
#includealgorithm
#define N 20010
using namespace std;
struct node{int x,y,c;
}a[N*5];
int n,m,father[N],empty[N];
bool cmp(node x,node y)
{return x.cy.c;}
int find(int x)//寻找
{if(father[x]x) return x;return father[x]find(father[x]);
}
void unionn(int x,int y)//合并
{int fafind(x),fbfind(y);father[fa]fb;
}
int main()
{scanf(%d%d,n,m);for(int i1;im;i)scanf(%d%d%d,a[i].x,a[i].y,a[i].c);for(int i1;in;i)father[i]i;sort(a1,a1m,cmp);for(int i1;im;i){if(find(a[i].x)find(a[i].y))//出现问题{printf(%d,a[i].c);return 0;}else {if(!empty[a[i].x])empty[a[i].x]a[i].y;else unionn(empty[a[i].x],a[i].y);if(!empty[a[i].y])empty[a[i].y]a[i].x;else unionn(empty[a[i].y],a[i].x);//连接——敌人的敌人}}printf(0);
}
