加载中…HDU 3832 Earth Hour Multi-University_Training_Contest Host_By_HNU
(2011-07-13 11:28:36)
标签：
hdu3832earthhour最短路it |
分类： 图论 |
题目描述：
模型为：告诉你n个点，和一些无向边，问你最多能够删掉多少个点，保证1,2,3号点是互相可达的。
解题报告：
无向边的边权设置为1，用3遍spfa或者什么，求出3个数组d[3][n]，d[i][j]表示i(1 <= i <= 3）到n的最短路。
枚举点i，找一个d[0][i] + d[1][i] + d[2][i] + 1最小的值，这个就是能够剩下的最少的点。用n减去之就是答案。
代码如下：
double
x, y, r;
memset(vst, 0, sizeof(vst));
vst[st]
= 1;
int
head = 0, tail = 0, tmp;
d[st] =
0;
que[tail++] = st;
while(head < tail)
{
vst[que[head]] = 0;
for(int i = 0; i
< n; i++)
if (g[que[head]][i] != -1
&& (d[i] == -1 || d[que[head]] + 1
< d[i]))
{
d[i] =
d[que[head]] + 1;
if
(!vst[i])
{
vst[i] = 1;
que[tail++] = i;
}
}
head++;
}
scanf("%d", &t);
while(t--)
{
scanf("%d",
&n);
memset(g, -1,
sizeof(g));
for(int i = 0; i
< n; i++)
scanf("%lf%lf%lf", &jeo[i].x,
&jeo[i].y, &jeo[i].r);
for(int i = 0; i
< n; i++)
for(int j = 0; j < n; j++)
if (i !=
j)
{
double dis = sqrt((jeo[i].x -
jeo[j].x) * (jeo[i].x - jeo[j].x) + (jeo[i].y - jeo[j].y) *
(jeo[i].y - jeo[j].y));
if (dis - jeo[i].r - jeo[j].r
<= 0)
g[i][j] = 1;
}
memset(d1, -1,
sizeof(d1));
memset(d2, -1,
sizeof(d2));
memset(d3, -1,
sizeof(d3));
spfa(d1, 0); spfa(d2, 1);
spfa(d3, 2);
int ans = -1;
for(int i = 0; i
< n; i++)
if (d1[i] != -1
&& d2[i] != -1
&& d3[i] != -1)
{
int tmp =
d1[i] + d2[i] + d3[i];
if (ans ==
-1 || tmp < ans) ans = tmp;
}
if (ans == -1)
printf("-1\n");
else printf("%d\n", n - ans -
1);
}
return
0;
模型为：告诉你n个点，和一些无向边，问你最多能够删掉多少个点，保证1,2,3号点是互相可达的。
解题报告：
无向边的边权设置为1，用3遍spfa或者什么，求出3个数组d[3][n]，d[i][j]表示i(1 <= i <= 3）到n的最短路。
枚举点i，找一个d[0][i] + d[1][i] + d[2][i] + 1最小的值，这个就是能够剩下的最少的点。用n减去之就是答案。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int g[200][200];
struct pint
{
}jeo[200];
int t, n ,que[100000], d1[200], d2[200], d3[200],
vst[200];
void spfa(int d[], int st)
{
}
int main()
{
}
喜欢
0
赠金笔