hdu 2433
好像是Dijkstra算法的变形，最短路生成树。
题意：我老是看不懂题目说什么，N个城镇，M条边，每条边的距离都是1（当然两个城镇之间可能有多条边，也可能没有边），求城镇i到城镇j的最短路之和，即，如果有两个城镇之间不连通就输出。要注意的是每次删边只是临时的，不影响下一次计算，比如第一次删第一条边，第二次删第二条边的时候以前删的边都要还原。
思路：
先预处理出每个最短路生成树，标记每颗树上的边，然后枚举输入的每条边，看这条边是否有重边，有的话不改变最短路之和，没有重边就判断是否在某颗最短路生成树上，在的话就再重新构建这棵最短路生成树（只是临时的）。由于，最短路生成树，最多n-1条边，所以每个点，最多做n-1次，所以复杂度(n-1)nm。
code：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxm=3e3+5,maxn=105;
template <class T>
inline void read(T &res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
struct node{
int u,v;
}to[maxm];
int n,m,total,totalA;
int line[maxn][maxn], sum[maxn];
bool used[maxn][maxn][maxn];//uesd[这颗最短路生成树的根i][某条边的端点][某条边的端点]=1表示这条边在最短路生成树上
queue<int> q;
int vis[maxn], dis[maxn];
int bfs(int x, bool mark) {
memset(vis, 0, sizeof(vis));
memset(dis, 0, sizeof(dis));
q.push(x);
vis[x] = 1;
while(!q.empty()) {
int v=q.front(); q.pop();
for(int i=1;i<=n;++i) if( !vis[i] && (line[v][i] || line[i][v]) ) {
vis[i] = 1;
if(mark == 0){
used[x][i][v] = 1; used[x][v][i] = 1;
}//第一次dfs需要标记最短路生成树的边
dis[i] += dis[v]+1;
q.push(i);
}
}
int ans=0;
for(int i=1;i<=n;++i) {
if(!vis[i]) return -1;//本来就有不可达的点 无论有没拆路都是INF 直接返回-1
ans+=dis[i];
}
return ans;
}
int main() {
while(~scanf("%d %d", &n, &m)) {
totalA = 0;
memset(line, 0, sizeof line);
memset(used, 0, sizeof used);
for(int i=1;i<=m;++i) {
int u,v; read(u),read(v);
to[i].u=u,to[i].v=v;
++line[u][v];
++line[v][u];
}
for(int i=1;i<=n;++i) {
sum[i] = bfs(i, 0);
if(sum[i] == -1) {
totalA = -1; break;
}
else
totalA += sum[i];
}
if(totalA==-1) {
for(int i=1;i<=m;++i) puts("INF");
continue;
}
for(int i=1;i<=m;++i) {
total = totalA ; // 使用一个临时代替
--line[to[i].u][to[i].v];
--line[to[i].v][to[i].u];
if( line[to[i].u][to[i].v] )
printf("%d\n", total);
else {
bool f = 0;
for(int j=1; j<=n; ++j) if(used[j][to[i].u][to[i].v] == 1) {
total -= sum[j];
int tmp = bfs(j, 1); // 不能把bfs()直接赋给sum[x] 因为拆路只是暂时的
if(tmp == -1) { f=1; break;}
total += tmp;
}
if(f)
puts("INF");
else
printf("%d\n", total);
}
++line[to[i].u][to[i].v];
++line[to[i].v][to[i].u];
}
}
return 0;
}
hdu 2680
题意：n个车站编号，m条有向边，表示u到v有一条路，需要花val分钟，给你终点s，还有w个起点（不管你从那个起点出发），求到终点的最小花费，怎样都到不了就输出-1。
踩过的坑思路：首先这是一个有向图，不要两个方向的边都存了，起点有很多，但是终点就一个，存反向图，求终点到所有起点最短路的最小值就可以了，用到的数组不要忘记初始化，写了牛客后写航电老是忘记初始化，done[]忘记初始化wa了好久。
code：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005,maxm=1e4+7;
template <class T>
inline void read(T &res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
int head[maxn],Next[maxm<<1],to[maxm<<1],tot,val[maxm<<1];
void add(int x,int y,int c) {
to[++tot]=y;
val[tot]=c;
Next[tot]=head[x];
head[x]=tot;
}
struct node{
int v,dis;
bool operator<(const node&a) const{
return dis>a.dis;
}
};
int n,m,dis[maxn];
bool done[maxn];//done[i]=true表示到结点i的最短路径已经找到
void dijkstra(int s) {
fill(dis, dis + maxn, 0xfffffff);
fill(done,done+ maxn, 0);
dis[s]=0; //起点到自己的距离是0
priority_queue<node>q;//优先队列，存结点的信息
q.push(node{s,0});//起点进栈
while(!q.empty()) {
node u=q.top();
q.pop();
if(done[u.v]) continue;//丢弃已经找到最短路径的结点，即集合A中的结点
done[u.v]=true;
for(int i=head[u.v];i;i=Next[i]) {
int y=to[i];
if(done[y]) continue;
if(dis[y]>val[i]+u.dis) {
dis[y]=val[i]+u.dis;
q.push(node{y,dis[y]});
}
}
}
}
int main() {
int n,m,s,w;
while(~scanf("%d%d%d",&n,&m,&s)) {
fill(head,head+maxn,0); tot=0;
while(m--) {
int u,v,w;
read(u),read(v),read(w);
add(v,u,w);
}
dijkstra(s);
int ans=0xfffffff,qi; read(w);
while(w--) {
read(qi);
ans=min(ans,dis[qi]);
}
if(ans==0xfffffff)
puts("-1");
else
printf("%d\n",ans);
}
}
hdu 4889
题意：给出spfa_slf优化的代码，要你写示例使得代码坏掉，即使题中给出的程序按该图执行 最终变量doge大于输入的C跳出
这代码看不下去,不会写。
code：
#include<cstdio>
int main(){
int i,j;
int f[33]={-1};
for(i=1;i<=30;i++) f[i]=f[i-1]*2;
while(~scanf("%d",&i)){
puts("99 87");
for(i=1;i<30;i++){
printf("%d %d 0\n",i,i+30);
printf("%d %d %d\n",i,i+1,f[29-i]);
printf("%d %d %d\n",i+30,i+1,f[30-i]);
}
}
return 0;
}
hdu 4568
最短路算法+旅行商问题（dp状压），注意到k非常小，这样很显然需要状压。 题意：给定一个n*m的棋盘，每一个格子有一个值，代表经过这个格子的花费（-1表示不能走这个格子），给出k个宝藏点的坐标，求从棋盘的任意一个边界进入棋盘，经过所有的宝藏点后在再走出棋盘所需要的最小花费（终点和起点可以不同）。 解题思路：spfa处理处任意两个宝藏点之间的最短距离（最小花费）和每个宝藏点和边界的最短距离。然后状态压缩：dp[s][i]表示经过集合s到达点i的花费（s采用二进制存储的形式，表示集合中的元素，列如s=3，3的二进制是11，表示第0个和第1个宝藏在集合s里）。 状态转移方程见代码，不难理解，别用memset给数组初始化为无穷，虽然可以，但是会超时。 code：
#include<bits/stdc++.h>
using namespace std;
const int maxn=205;
int n,m;
struct node{
int x,y;
}pos[15];//存宝藏的坐标
int dx[4][2]= {1,0,0,1,-1,0,0,-1};
int dis[maxn][maxn],a[maxn][maxn],border[25],line[20][20];
bool vis[maxn][maxn];//vis[][]=1表示在队列里
int dp[1<<15][15];
void spfa(int s) {
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
dis[i][j]=0x3f3f3f3f;
memset(vis,0,sizeof vis);
queue<node>q;
q.push({pos[s].x,pos[s].y}) ;
//vis[point[s].x][point[s].y]=1;
dis[pos[s].x][pos[s].y]=0;
while(!q.empty()) {
int x=q.front().x,y=q.front().y;
q.pop();
vis[x][y]=0;
if( !x || x==n-1 || !y || y==m-1 )
border[s]=min(border[s],dis[x][y]);//求x到边界的最短路
for(int i=0;i<4;++i) {
int xx=x+dx[i][0],yy=y+dx[i][1];
if( xx<0 || xx>=n && yy<0 || yy>=m || a[xx][yy]==-1 )
continue;
if(dis[xx][yy]>dis[x][y]+a[xx][yy]) {
dis[xx][yy]=dis[x][y]+a[xx][yy];
if(!vis[xx][yy]) {
vis[xx][yy]=1;
q.push({xx,yy});
}
}
}
}
}
int main() {
int T,k;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
scanf("%d",&a[i][j]);
scanf("%d",&k);
for(int i=0;i<k;++i)
scanf("%d%d",&pos[i].x,&pos[i].y);
for(int i=0;i<k;++i) {
border[i]=0x3f3f3f3f;
line[i][i]=0;
for(int j=i+1;j<k;++j)
line[i][j]=line[j][i]=0x3f3f3f3f;
}
for(int i=0;i<(1<<k);++i)
for(int j=0;j<k;j++)
dp[i][j]=0x3f3f3f3f;
for(int i=0;i<k;++i){
spfa(i);
for(int j=0; j<k; ++j) {
if(j==i)continue;
line[i][j]=min(dis[pos[j].x][pos[j].y],line[i][j]);
}
dp[1<<i][i]=border[i]+a[pos[i].x][pos[i].y];
}
for(int s=0;s<(1<<k);++s)
for(int i=0;i<k;i++) {
if(s&(1<<i)==0) continue;//s的集合里没有i
for(int j=0;j<k;j++) {
if(s&(1<<j))continue;
dp[s|(1<<j)][j]=min(dp[s|(1<<j)][j],dp[s][i]+line[i][j]);
}
}
int ans=0x3f3f3f3f;
for(int i=0;i<k;++i)
ans=min(ans,dp[(1<<k)-1][i]+border[i]);
printf("%d\n",ans);
}
return 0;
}
京公网安备 11010502036488号