水题水过
var x,y,l,i,n,m,k,ans,temp:longint;
father,u,v,w:array[0..100000] of longint;

function getfather(k:longint):longint;
var tip:longint;
begin
if father[k]=k then exit(k);
tip:=father[k];
father[k]:=getfather(tip);
getfather:=father[k];
end;

procedure qsort(a,b:longint);
var i,j,x,temp:longint;
begin
i:=a;
j:=b;
x:=w[(i+j) div 2];
repeat
while w[i]<x do inc(i);
while w[j]>x do dec(j);
if i<=j then
begin
temp:=w[i];
w[i]:=w[j];
w[j]:=temp;
temp:=u[i];
u[i]:=u[j];
u[j]:=temp;
temp:=v[i];
v[i]:=v[j];
v[j]:=temp;
inc(i);
dec(j);
end;
until i>j;
if i<b then qsort(i,b);
if a<j then qsort(a,j);
end;

procedure kruskal;
var i,t1,t2,tip:longint;
begin
tip:=0;
for i:=1 to m do
begin
t1:=getfather(u[i]);
t2:=getfather(v[i]);
if t1<>t2 then
begin
father[t1]:=t2;
ans:=ans+w[i];
inc(tip);
end;
if tip=temp then break;
end;
if tip<temp then ans:=-1;
end;

begin
//assign(input,'vj2.in');
//assign(output,'vj2.out');
//reset(input);
//rewrite(output);
readln(n,m,k);

for i:=1 to m do
begin
readln(x,y,l);
u[i]:=x;
v[i]:=y;
w[i]:=l;
end;
qsort(1,m);
for i:=1 to n do father[i]:=i;
temp:=n-k;
kruskal;
if ans<0 then writeln('No Answer')
else
writeln(ans);

//close(input);
//close(output);
end.

题号真帅

Krusal 连了n-k条边就结束，连不到这么多边就输出无解
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 552 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 552 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 556 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 560 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 560 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 564 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 556 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 556 KiB, score = 10
Accepted, time = 75 ms, mem = 564 KiB, score = 100
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAXN 1001
#define MAXM 10010

struct edge {
int s,t,c;
} E[MAXM];

bool cmp(edge x,edge y) {
return x.c<y.c;
}

int n,m,k;
int father[MAXN];

int Find(int x) {
int i,j=x;
for (i=x;father[i];i=father[i]) ;
while (father[j]) {
int K=father[j];
father[j]=i;
j=K;
}
return i;
}

int main() {
while (scanf("%d%d%d",&n,&m,&k)!=EOF) {
for (int i=0;i<m;i++) scanf("%d%d%d",&E[i].s,&E[i].t,&E[i].c);
sort(E,E+m,cmp);
memset(father,0,sizeof(father));
int N=0,Cost=0;
for (int i=0;i<m;i++) {
if (N==n-k) break;
if (Find(E[i].s)!=Find(E[i].t)) {
father[Find(E[i].s)]=E[i].t;
Cost+=E[i].c;
N++;
}
}
if (N!=n-k) printf("No Answer\n"); else printf("%d\n",Cost);
}
return 0;
}

裸地Kruskal，注意最后结束循环的条件

Kruskal。。。不解释。。。

话说我写个题解就是为了这题号来的。。。

├ 测试数据 01：答案正确... (0ms, 704KB)

├ 测试数据 02：答案正确... (0ms, 704KB)

├ 测试数据 03：答案正确... (0ms, 704KB)

├ 测试数据 04：答案正确... (0ms, 704KB)

├ 测试数据 05：答案正确... (0ms, 704KB)

├ 测试数据 06：答案正确... (0ms, 704KB)

├ 测试数据 07：答案正确... (0ms, 704KB)

├ 测试数据 08：答案正确... (0ms, 704KB)

├ 测试数据 09：答案正确... (0ms, 704KB)

├ 测试数据 10：答案正确... (0ms, 704KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 0ms / 704KB

水最小生成树

此题甚好

坑爹啊~~顶楼下，同感！！！

program p1234;

var d,q,h,i,j,n,m,k,tot:longint;

x,y,l:array[1..10000] of integer;

f:array[1..1000] of integer;

procedure qsort(i,j:integer);

var z,q,h,mid:longint;

begin

q:=i;

h:=j;

mid:=l[(i+j) div 2];

repeat

while l[q]mid do dec(h);

if qh ;

if qi then qsort(i,h);

end;

function find(x:integer):integer;

begin

if x=f[x] then exit(f[x])

else f[x]:=find(f[x]);

exit(f[x]);

end;

begin

readln(n,m,k);

for i:=1 to m do readln(x[i],y[i],l[i]);

qsort(1,m);

for i:=1 to n do f[i]:=i;

tot:=0;

d:=0;

for i:=1 to m do

begin

q:=find(x[i]);

h:=find(y[i]);

if qh then

begin

f[q]:=h;

inc(d);

tot:=tot+l[i];

end;

if n-d=k then break;

end;

if n-d=k then writeln(tot) else writeln('No Answer');

end.

悲剧了。。。我自己用VIJOS的数据测试都对，为什么提交后答案都错误= =

KRUSKAL 秒杀 一次AC

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

终于搞懂了并查集

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

就是利用最小生成树的思想，就最小的n-k条边使他们不构成环。

program p1234;

var a,b,c,f:array[1..10000] of longint;

i,j,k,l,m,n,min,r,max:longint;

procedure qsort(x,y:longint);

var g,t,s,l,r:longint;

begin

t:=c[(x+y) div 2];l:=x;r:=y;

repeat

while c[l]t do dec(r);

if lr;

if l

100题留念

很可悲的没有一次AC

原因是把数据范围看错了 看成那个30%的数据范围了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确...ms

├ 测试数据 02：答案正确...ms

├ 测试数据 03：答案正确...ms

├ 测试数据 04：答案正确...ms

├ 测试数据 05：答案正确...ms

├ 测试数据 06：答案正确...ms

├ 测试数据 07：答案正确...ms

├ 测试数据 08：答案正确...ms

├ 测试数据 09：答案正确...ms

├ 测试数据 10：答案正确...ms

Accepted 有效得分：100 有效耗时：0ms

101题纪念……

我沙茶了，一道水题交了六遍

program v1234;

type rec=record

x,y,w:longint;

end;

var a:array[1..10000] of rec;

f:array[1..1000] of longint;

i,j,k,n,m,s,w,f1,f2:longint;

procedure qsort(s,e:longint);

var i,j,x:longint;

t:rec;

begin

i:=s; j:=e;

x:=a[random(e-s)+s].w;

repeat

while a[i].wx do dec(j);

if ij;

if is then qsort(s,j);

end;

function find(x:longint):longint;

begin

if x=f[x] then exit(x)

else f[x]:=find(f[x]);

exit(f[x]);

end;

begin

readln(n,m,k);

for i:=1 to m do readln(a[i].x,a[i].y,a[i].w);

randomize;

qsort(1,m);

for i:=1 to n do f[i]:=i;

for i:=1 to m do

begin

f1:=find(a[i].x);

f2:=find(a[i].y);

if f1f2

then begin

f[f2]:=f1;

inc(w,a[i].w);

inc(s);

end;

if n-s=k then break;

end;

if n-s=k then writeln(w) else writeln('No Answer');

end.

水……………………

不错的题...不完全最小生成树

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

直接kruskal了……没想那么多……晒一下主要过程：

procedure kruskal;

var

i,j:longint;

begin

if (k>n) or (m

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

嗯，不错的一道题……