hdu2433 spfa+mark[x][u][v]优化
题意:
删除每一条边求最短路的和,每删除一个就输出一个和.
思路:
直接暴力可定TLE了,自己SB的尝试过,就要剪纸,当每次输出一个答案的时候我们没有必要再从新暴力全跑一边最短路,我们可以开一个数组mark[s][u][v]来标记,当s为起点是边u,v是否被用过(其实是可能,记录的时候是更新就假设被用过,但也能达到剪纸的目的),开个sum[i]数组记录已i为起点时的和,如果被用过那么以s为起点的就得从新跑,否则不用(跑sum[s]也不会变化,所以没必要跑).这样能节省很多时间,但自己想想,如果管理员精心设计各种数据,让你每一条边都可能被用过那么就TLE了,但估计不会那么变态,卡数据可以,不能变态的卡,不然题目的答案岂不是要唯一化了..
#include<stdio.h>
#include<string.h>
#include<queue>
#define N_node 105
#define N_edge 6100
#define inf 1000000000
using namespace std;
typedef struct
{
int to ,cost ,next;
}STAR;
STAR E[N_edge];
int list[N_node] ,tot;
int s_x[N_node];
int mark[N_node][N_node][N_node];
int map[N_node][N_node];
int sum[N_node];
int Q[N_edge>>1][2];
void add(int a ,int b ,int c)
{
E[++tot].to = b;
E[tot].cost = c;
E[tot].next = list[a];
list[a] = tot;
}
void spfa(int s ,int n ,int key ,int u ,int v)
{
int mark_q[N_node] = {0};
mark_q[s] = 1;
for(int i = 0 ;i <= n ;i ++)
s_x[i] = inf;
s_x[s] = 0;
queue<int>q;
q.push(s);
while(!q.empty())
{
int xin ,tou;
tou = q.front();
q.pop();
mark_q[tou] = 0;
for(int k = list[tou] ;k ;k = E[k].next)
{
xin = E[k].to;
if(u == tou && v == xin || u == xin && v == tou)
continue;
if(s_x[xin] > s_x[tou] + E[k].cost)
{
s_x[xin] = s_x[tou] + E[k].cost;
if(key == 1)
mark[s][tou][xin] = mark[s][xin][tou] = 1;
if(!mark_q[xin])
{
mark_q[xin] = 1;
q.push(xin);
}
}
}
}
return ;
}
int main ()
{
int n ,m ,i ,a ,b ,ii ,jj;
while(~scanf("%d %d" ,&n ,&m))
{
memset(list ,0 ,sizeof(list));
memset(map ,0 ,sizeof(map));
tot = 1;
for(i = 1 ;i <= m ;i ++)
{
scanf("%d %d" ,&a ,&b);
map[a][b] ++;
map[b][a] ++;
add(a ,b ,1);
add(b ,a ,1);
Q[i][0] = a;
Q[i][1] = b;
}
int first = 0;
memset(sum ,0 ,sizeof(sum));
memset(mark ,0 ,sizeof(mark));
for(i = 1 ;i <= n ;i ++)
{
spfa(i ,n ,1 ,0 ,0);
for(ii = 1 ;ii <= n ;ii ++)
{
sum[i] += s_x[ii];
if(s_x[ii] == inf)
break;
}
first += sum[i];
if(ii != n + 1)
break;
}
if(i != n + 1)
{
for(i = 1 ;i <= m ;i ++)
printf("INF\n");
continue;
}
for(i = 1 ;i <= m ;i ++)
{
a = Q[i][0];
b = Q[i][1];
if(map[a][b] > 1)
{
printf("%d\n" ,first);
continue;
}
int now = first;
int kk = 0;
for(ii = 1 ;ii <= n ;ii ++)
{
if(mark[ii][a][b])
{
spfa(ii ,n ,0 ,a ,b);
int s = 0;
for(jj = 1 ;jj <= n ;jj ++)
{
s += s_x[jj];
if(s_x[jj] == inf)
break;
}
now = now - sum[ii] + s;
if(jj != n + 1)
break;
}
}
if(ii != n + 1)
{
printf("INF\n");
continue;
}
printf("%d\n" ,now);
}
}
return 0;
}
最新文章
- link与@import的区别
- python generator: next , sent(msg)区别
- ldap配置记录
- web浏览器兼容简要整理
- Java面向对象的封装
- 树形菜单复选框级联选择HTML
- [Silverlight] Visual Studio2010不能安装Silverlight4_Tools,提示语言不一致
- C# MessageBox 用法大全(转)
- CenOS6.4 系统升级内核
- xml学习篇(一)
- <; welcome >; 一起学习,进步,分享。
- 正則表達式 取出img标签 保存于指定路径
- 手动搭建SSI框架
- 10个带源码的充满活力的Web设计教程
- 弹出框插件layer使用
- php会话(session)实现原理
- 【BZOJ3931】【CQOI2015】网络吞吐量(最短路,网络流)
- 1-51单片机WIFI学习(开发板介绍)
- 小程序----选择地理位置 ( wx.chooseLocation ) 和 获取地理位置 (wx.getSetting)
- debian 安装libreoffice6.1 转换pdf