这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
最小生成树(MST)讲解请看: [http://www.wutianqi.com/?p=1284](http://www.wutianqi.com/?p=1284) |
HDOJ 1233 还是畅通工程: 题目传送门: http://acm.hdu.edu.cn/showproblem.php?pid=1233
解答报告:
#include
#include
using namespace std;
typedef struct Road
{
int c1, c2, cost;
}Road;
bool myCompare(const Road &a;, const Road &b;)
{
if(a.cost < b.cost)
return 1;
return 0;
}
Road road[5051];
int city[101];
int Find(int n)
{
if(city[n] == -1)
return n;
return city[n] = Find(city[n]);
}
bool Merge(int s1, int s2)
{
int r1 = Find(s1);
int r2 = Find(s2);
if(r1 == r2)
return 0;
if(r1 < r2)
city[r2] = r1;
else
city[r1] = r2;
return 1;
}
int main()
{
//freopen("input.txt", "r", stdin);
int n;
while(scanf("%d", &n;) && n)
{
int m = n*(n-1)/2;
memset(city, -1, sizeof(city));
for(int i=0; i
**HDOJ 1863 畅通工程**
题目传送门:
[http://acm.hdu.edu.cn/showproblem.php?pid=1863](http://acm.hdu.edu.cn/showproblem.php?pid=1863)
好吧,这题是送你的,因为这题和1233基本上没区别。。。。
解答报告:
```cpp
#include
#include
using namespace std;
typedef struct Road
{
int c1, c2, cost;
}Road;
bool myCompare(const Road &a;, const Road &b;)
{
if(a.cost < b.cost)
return 1;
return 0;
}
Road road[5051];
int city[101];
int Find(int n)
{
if(city[n] == -1)
return n;
return city[n] = Find(city[n]);
}
bool Merge(int s1, int s2)
{
int r1 = Find(s1);
int r2 = Find(s2);
if(r1 == r2)
return 0;
if(r1 < r2)
city[r2] = r1;
else
city[r1] = r2;
return 1;
}
int main()
{
//freopen("input.txt", "r", stdin);
int n, m;// m-道路条数, n-村庄数
while(scanf("%d %d", &m;, &n;) && m)
{
memset(city, -1, sizeof(city));
for(int i=0; i
**HDOJ 1879 继续畅通工程**
题目传送门:
[http://acm.hdu.edu.cn/showproblem.php?pid=1879](http://acm.hdu.edu.cn/showproblem.php?pid=1879)
这题币上面两题要活一些。
可以考察大家对MST的掌握。
好好分析代码,相信你能看懂的。
```cpp
#include
#include
using namespace std;
typedef struct Road
{
int c1, c2, cost, state;
}Road;
bool myCompare(const Road &a;, const Road &b;)
{
if(a.cost < b.cost)
return 1;
return 0;
}
Road road[5051];
int city[101];
int Find(int n)
{
if(city[n] == -1)
return n;
return city[n] = Find(city[n]);
}
bool Merge(int s1, int s2)
{
int r1 = Find(s1);
int r2 = Find(s2);
if(r1 == r2)
return 0;
if(r1 < r2)
city[r2] = r1;
else
city[r1] = r2;
return 1;
}
int main()
{
//freopen("input.txt", "r", stdin);
int n;
while(scanf("%d", &n;) && n)
{
int m = n*(n-1)/2;
memset(city, -1, sizeof(city));
int count = 0;
for(int i=0; i<m; ++i)
{
scanf("%d %d %d %d", &road[i].c1, &road[i].c2, &road[i].cost, &road[i].state);
if(road[i].state == 1)
{
count ++;
Merge(road[i].c1, road[i].c2);
}
}
sort(road, road+m, myCompare);
int sum = 0;
for(int i=0; i<m; ++i)
{
if(Merge(road[i].c1, road[i].c2) && road[i].state == 0)
{
count ++;
sum += road[i].cost;
}
if(count == n-1)
break;
}
printf("%d\n", sum);
}
return 0;
}