化妆品网站建设可行性报告,商城网站建设信息,优化营商环境个人心得,辽源网站建设S 城现有两座监狱#xff0c;一共关押着 $N$ 名罪犯#xff0c;编号分别为 $1-N$ 。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久#xff0c;如果客观条件具备则随时可能爆发冲突。我们用“怨气值”#xff08;一个正整数值#xff09;来表示某两名罪犯之间的…S 城现有两座监狱一共关押着 $N$ 名罪犯编号分别为 $1-N$ 。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久如果客观条件具备则随时可能爆发冲突。我们用“怨气值”一个正整数值来表示某两名罪犯之间的仇恨程度怨气值越大则这两名罪犯之间的积怨越多。如果两名怨气值为 $c$ 的罪犯被关押在同一监狱他们俩之间会发生摩擦并造成影响力为 $c$ 的冲突事件。
每年年末警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力如果影响很坏他就会考虑撤换警察局长。
在详细考察了 $N$ 名罪犯间的矛盾关系后警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配以求产生的冲突事件影响力都较小从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨那么他们一定会在每年的某个时候发生摩擦。
那么应如何分配罪犯才能使 Z 市长看到的那个冲突事件的影响力最小这个最小值是多少
输入格式
每行中两个数之间用一个空格隔开。第一行为两个正整数 $N$,$M$,分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的 $M$ 行每行为三个正整数 $a_j$,$b_j$,$c_j$,表示 $a_j$ 号和 $b_j$ 号罪犯之间存在仇恨其怨气值为 $c_j$。数据保证 $1 a_j \leq b_j \leq N$, $0 c_j \leq 10^9$且每对罪犯组合只出现一次。
输出格式
共 1 行为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件请输出 0。
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N4e410;
const int M2e510;
int fa[N];
struct p{int x,y,c;
}a[M];
bool cmp(p a,p b)
{return a.cb.c;
}
int find(int x)
{return fa[x]x?x:(fa[x]find(fa[x]));
}
void merge(int a,int b)
{int xfind(a);int yfind(b);if(x!y)fa[x]y;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m;cinnm;for(int i1;i2*n;i) fa[i]i;for(int i0;im;i) cina[i].xa[i].ya[i].c;sort(a,am,cmp);bool flag0;for(int i0;im;i){if(find(a[i].x)find(a[i].y)){couta[i].cendl;flag1;break;}merge(a[i].x,a[i].yn);merge(a[i].y,a[i].xn);}if(!flag)cout0endl;return 0;
}
