注意，Prim不保证加入的边递增！

我WA了2次，可见我之沙茶

话说……这题想不过都不行了。。。因为N^3都能AC……

干脆一个Kruskal……

编译通过...

├ 测试数据 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

Kruskal显然能秒吧...读入复杂度就O(M)了

快排打错一次 囧了

├ 测试数据 01：运行时错误...|错误号: 128

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

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

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

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

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

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

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

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

├ 测试数据 10：运行时错误...|错误号: 128

#include

using namespace std;

int main()

{

const int max=99999;

int n,m;

int g[301][301],u,v,i,j,k,min,mo,s,w;

struct line

{

int f,e,w;

};

line es[300],t;

cin>>n>>m;

for(i=1;i>v>>g[v];

g[v]=g[v];

}

for(i=1;i

编译通过... ├ 测试数据 01：答案正确... 0ms ├ 测试数据 02：答案正确... 0ms ├ 测试数据 03：答案正确... 0ms ├ 测试数据 04：答案正确... 0ms ├ 测试数据 05：答案正确... 0ms ├ 测试数据 06：答案正确... 0ms ├ 测试数据 07：答案正确... 0ms ├ 测试数据 08：答案正确... 0ms ├ 测试数据 09：答案正确... 0ms ├ 测试数据 10：答案正确... 0ms ------------------------- Accepted 有效得分：100 有效耗时：0ms

kruskal照样秒

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

1A0MS Prim才是王道 好写还实用

直接write(n-1,' ')然后再Prim.....无语.....

好题 据说O(N^3)Prim好像都超不了时吧

编译通过...

├ 测试数据 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

省选题?太水了吧!直接最小生成树啊我晕!还难度3....闷

简单朴素的prim

最小生成树。。。

程序：

http://lifeich1.spaces.live.com/blog/cns!9AB465A9D807BE22!182.entry

PRIM

裸的prim 39行

一次过

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

Kruscal+冰茶几=AC

prim就行么

显然，这道题用的是最小生成树。

显然，我这个显然用得有问题，其实……

请教列位神牛大牛，这个最小生成树算法正确性如何证明？

Prim

数据范围难道给小了么.

好久没写MST了..0.5h内写弯着油西写出来一遍AC.

一次过样例

一次AC

耗时10min

Prim

Kruskal

皆宜

这个竟然成了俺们省的省选题了....无语...