求 关押罪犯 标程
发布网友
发布时间：2024-07-13 04:54
共2个回答
热心网友
时间：2024-08-06 06:42
【题目描述】
☆关押罪犯
描述 Description
S 城现有两座监狱，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为c 的冲突事件。
每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。
在详细考察了N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？
输入格式 Input Format
输入文件的每行中两个数之间用一个空格隔开。
第一行为两个正整数N 和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。
接下来的M 行每行为三个正整数aj，bj，cj，表示aj 号和bj 号罪犯之间存在仇恨，其怨气值为cj。数据保证1<=aj<bj<N,0<cj<=1,000,000,000 且每对罪犯组合只出现一次。
输出格式 Output Format
输出共1 行，为Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出0。
数据范围
对于30%的数据有N≤15。
对于70%的数据有N≤2000，M≤50000。
对于100%的数据有N≤20000，M≤100000。
【问题的分析】
一.首先，我们要从题目的要求出发，弄清题目所要求的值。
由于市长只会去看列表中的由大至小第一个事件的影响力，那么，我们所要求的就是这样的一个最大值。现在，题目要求这样的一个最大值要尽可能的“小”。什么意思？其实就是说，我们通过一定的分配罪犯监狱的方法分配完罪犯之后，那么对于分进两个不同的监狱中的罪犯将不存在怨气值，因而，不同的分法可能存在着不同的最大值。因而，现在我们要做的就是，找出这样的分配方法，使得其中最大的怨气值是所有可行分配方法中最小的一个值。
二.问题分析的逐步深入。
首先，我们会发现题目中有一个重要的大前提：就是S城只有两座监狱！这样的一句话，可以很明显的让我们看出本题所具有的二分图的性质，因为通过可行分配方法分配过后，所有的罪犯将会被分进两个不同的监狱，抽象起来就是二分图的模型。那么，本题是否用到了二分图的算法呢？答案是没有，因为我们真正需要的仅仅是对于二分图是否成立的一个定性的判断。
到以上，我们就有了一个粗略的想法：就是通过枚举的思想，枚举最大的边，将比它大的边删去，那么，对于剩下的图来说，如果我们能够将之划分成二分图，则当前所枚举的最大边就将是一个可行的解。并且，我们可以想到的一个判断二分图的可行方法就是宽度搜索：将图中的一个没选过的点标上1，与之相连的点标上2，然后再依次标上1,2......，当然，如果其中出现了矛盾，则说明这个图不可二分。
至此，我们得到了一个可行的算法：枚举最大的边，宽搜判断二分图。 时间的复杂度约为O（M*N）。朴素的30分。
进一步思考，发现在枚举最大边时，我们可以想到的一个很好的优化，那就是：二分枚举！因为，我们可以通过排序，使得边由小到大递增，那么边的顺序就具有了单调性，因而，我们可以采用二分的思想来枚举。效率就会立马提升一个档次。
完善后：时间复杂度约为O（N*logM）。从理论上将已经可以通过全部的点了。
然而细细的想后，会发现在我们判断二分图的时候，每次都是在一个新的图上判断二分图能否成立，因而，判断一遍二分图约是O（N）级别的效率，这样可以看出，效率被花在的二分图的判断上。那么，我们是否可以改善一下判断的方法呢？
再次回顾一下题目中的大前提，我们发现：罪犯被分在了两个监狱，也即是分成了两类！同类在一个监狱！我们可以将每一类之抽象成一个集合。
那么在动态维护每一类的对象，以及便于查找确定每个对象所在类别的数据结构是什么呢？很明显：并查集！
想到并查集之后，问题就简化了许多。现在我们可以采取的解决办法就是：将所有的边排序，然后由大到小将每条边一次删去，对于每一条删去的边来说，边上所连接的两个点需要被分在两个不同的集合之中（即将这两个罪犯分在不同的监狱）。当我们在删去边的时候，发现该边上所连接的两个点已经在同一类集合之中了，那么此时，这条边就是不可被删去的。也就是最终的解。时间复杂度约为O（5*M）（该常数是并查集的效率）
【算法的实现】
对于并查集，我们可以采用的办法由两种：一种是同类合并。另一种是关系合并。
以下以关系合并为例，讲解以下并查集实现的过程：
0-代表同一个监狱（朋友） 1-代表不同的监狱（敌对）
对于当前这条待删去的边来说，我们需要判断边上所连接的两个点是否曾经有过关系，如果不曾有过关系，则说明这两个点可以成为敌对的关系；反之，需要我们判断当前这两点的关系是否敌对，如果不敌对则说明当前这条边是不可删去的，否则是可以删去的。
路径压缩的时候，我们需要修改点的父亲，以及点与父亲的关系。合并的时候，我们也需要建立一个点与其父亲的关系。（在个人标程中有详细的说明。）
【个人标程】
以下是个人标程，供大家参考：
program prison;
const
maxn=20000; maxm=100000;
var
n,m:longint;
f,s:array[0..maxn+1] of longint;
a,b,c:array[0..maxm+1] of longint;
function findsets(k:longint):longint;
var
y:longint;
begin
if f[k]<>k then
begin
y:=f[k]; f[k]:=findsets(y); {路径的压缩}
s[k]:=(s[k]+s[y]) mod 2; {在路径压缩中正确的建立与新的父亲的新的关系}
end;
exit(f[k]);
end;
procedure combinesets(a,b:longint);
begin
s[f[a]]:=(s[a]+1) mod 2; {建立a的父亲与b的关系，1为敌人，0为朋友}
f[f[a]]:=b; {改变a的父亲的对象，为b}
end;
procedure work;
var
i,sa,sb:longint;
begin
for i:=m downto 1 do {枚举每条边，进行二分图的判断}
begin
sa:=findsets(a[i]); sb:=findsets(b[i]);
if sa=sb then
begin
if s[a[i]]=s[b[i]] then {当二者之前发生过关系，并且现在的关系和之前的关系相矛盾，则说明当前的为输出解}
begin
writeln(c[i]);
exit;
end;
end
else combinesets(a[i],b[i]); {否则将二者合并，建立关系}
end;
writeln(0);{删去所有的边后仍然符合条件，则说明此时应当输出0}
end;
procedure qsort(l,r:longint); {将读入的边按照大小排序}
var
i,j,x,y:longint;
begin
i:=l; j:=r; x:=c[(l+r) div 2];
repeat
while c[i]<x do inc(i);
while c[j]>x do dec(j);
if not (i>j) then
begin
y:=a[i]; a[i]:=a[j]; a[j]:=y;
y:=b[i]; b[i]:=b[j]; b[j]:=y;
y:=c[i]; c[i]:=c[j]; c[j]:=y;
inc(i); dec(j);
end;
until i>j;
if j>l then qsort(l,j);
if i<r then qsort(i,r);
end;
procedure makesets; {建立一个新的并查集}
var
i:longint;
begin
for i:=1 to n do f[i]:=i;
end;
procedure reads; {读入数据}
var
i:longint;
begin
readln(n,m);
makesets;
for i:=1 to m do readln(a[i],b[i],c[i]);
end;
begin
assign(input,'prison.in');
reset(input);
assign(output,'prison.out');
rewrite(output);
reads;
qsort(1,m);
work;
close(input);
close(output);
end.
热心网友
时间：2024-08-06 06:39
