点击打开链接hdu 2923
思路:最短路+SPFA / 最短路+floyd
分析:
1 题目要求的是有n个点,然后有c个破车,这个c个破车可能在同一城市里面,现在要把这些破车统一拉到中心点1.
2 这题的中心在1点,那么所求 ans = 1->所有破车的距离之和 + 所有破车->1的之和。所以这里涉及到1->所有破车的距离 和 所有破车->1的距离,那么我们可以使用SPFA和floyd。如果使用的是floyd那么最后的ans = dis[1][i]+dis[i][1];如果是SPFA就要先求一下1->所有破车的距离之和,然后在重新建图就是把边反向然后对1点SPFA ,在加上1->所有破车的和即可。
4 点的表示,利用map映射。
3 这一题给的n虽然才100,但是利用SPFA的时候要数组记得开1010,因为c最大为1000.这个地方杭电是WA,不给RE,所以我WA了40+。
代码:
/*floyd*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
#define MAXN 110
#define INF 0xFFFFFFF
int n , m , r , cnt;
int value[MAXN][MAXN];
int num[1010];
char ch[1010][20];
map<string , int>mp;
void init(){
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++)
value[i][j] = INF;
value[i][i] = 0;
}
}
void input(){
int a , b , v;
cnt = 0;
char str1[MAXN] , str2[MAXN] , ch1 , ch2;
mp.clear();
for(int i = 1 ; i <= m+1 ; i++){
scanf("%s" , ch[i]);
a = mp[ch[i]];
if(!a)
a = mp[ch[i]] = ++cnt;
num[i] = a;
}
for(int i = 0 ; i < r ; i++){
scanf("%s" , str1);
while((ch1 = getchar()) == ' ');
scanf("-%d-%c %s" , &v , &ch2 , str2);
a = mp[str1];
b = mp[str2];
if(!a)
a = mp[str1] = ++cnt;
if(!b)
b = mp[str2] = ++cnt;
if(ch1 == '<' && ch2 == '>'){
if(value[a][b] > v)
value[a][b] = v;
if(value[b][a] > v)
value[b][a] = v;
}
else if(ch1 == '<' && ch2 == '-'){
if(value[b][a] > v)
value[b][a] = v;
}
else{
if(value[a][b] > v)
value[a][b] = v;
}
}
}
void floyd(){
for(int k = 1 ; k <= n ; k++){
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++){
if(value[i][j] > value[i][k] + value[k][j])
value[i][j] = value[i][k] + value[k][j];
}
}
}
}
int main(){
int ans , Case = 1;
while(scanf("%d%d%d" , &n , &m , &r) && n+m+r){
init();
input();
floyd();
ans = 0;
for(int i = 2 ; i <= m+1 ; i++)
ans += value[1][num[i]] + value[num[i]][1];
printf("%d. %d\n" , Case++ , ans);
}
return 0;
}
/*SPFA*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
#define MAXN 1010
#define INF 0xFFFFFFF
int n , m , r , cnt;
int value[MAXN][MAXN];
int tmpValue[MAXN][MAXN];
char ch[MAXN][20];
int dis[MAXN];
int vis[MAXN];
int num[MAXN];
queue<int>q;
map<string , int>mp;
void init(){
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++)
value[i][j] = INF;
value[i][i] = 0;
}
}
void input(){
int a , b , v;
cnt = 0;
char str1[MAXN] , str2[MAXN] , ch1 , ch2;
mp.clear();
for(int i = 1 ; i <= m+1 ; i++){
scanf("%s" , ch[i]);
a = mp[ch[i]];
if(!a)
a = mp[ch[i]] = ++cnt;
num[i] = a;
}
for(int i = 0 ; i < r ; i++){
scanf("%s" , str1);
while((ch1 = getchar()) == ' ');
scanf("-%d-%c %s" , &v , &ch2 , str2);
a = mp[str1];
b = mp[str2];
if(!a)
a = mp[str1] = ++cnt;
if(!b)
b = mp[str2] = ++cnt;
if(ch1 == '<' && ch2 == '>'){
if(value[a][b] > v)
value[a][b] = v;
if(value[b][a] > v)
value[b][a] = v;
}
else if(ch1 == '<' && ch2 == '-'){
if(value[b][a] > v)
value[b][a] = v;
}
else{
if(value[a][b] > v)
value[a][b] = v;
}
}
}
/*重新建图*/
void rebuild(){
memcpy(tmpValue , value , sizeof(value));
init();
for(int i = 1 ; i <= cnt ; i++){
for(int j = 1 ; j <= cnt ; j++){
if(tmpValue[i][j]){
value[j][i] = tmpValue[i][j];
}
}
}
}
/*SPFA算法*/
void SPFA(){
memset(vis , 0 , sizeof(vis));
for(int i = 2 ; i <= cnt ; i++)
dis[i] = INF;
dis[1] = 0;
vis[1] = 1;
q.push(1);
while(!q.empty()){
int x = q.front();
q.pop();
vis[x] = 0;
for(int i = 1 ; i <= cnt ; i++){
if(value[x][i] && dis[i] > dis[x] + value[x][i]){
dis[i] = dis[x] + value[x][i];
if(!vis[i]){
vis[i] = 1;
q.push(i);
}
}
}
}
}
int main(){
int ans , Case = 1;
while(scanf("%d%d%d" , &n , &m , &r) && n+m+r){
init();
input();
SPFA();/*第一次SPFA*/
ans = 0;
for(int i = 2 ; i <= m+1 ; i++)
ans += dis[num[i]];
rebuild();/*图重建*/
SPFA();/*第二次SPFA*/
for(int i = 2 ; i <= m+1 ; i++)
ans += dis[num[i]];
printf("%d. %d\n" , Case++ , ans);
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
HDU的一题........HDU DP动态规
hdu1001解题报告
hdu 1574 passed sorce
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
HDU最全ac代码
hdu动态规划算法集锦
hdu 1166线段树代码
hdu 1005.比较简单的一道题,有兴趣的可以看看。
hdu题目分类
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
HDU图论题目分类