29/7/2012 ICPC培训 第十四天
又来喽
嗯，昨天给自己放了一天假哈，所以也就没啥好些的了。
今天呢，上午刷了一题，外加写了SPFA算法的代码实现，包括打印最短路径。下午呢，
刷了一题。并且，这两题都是SPFA求解最短路径相关的。晚上，就是大神来上课了，
不过几乎听不懂的说，所以也就没听了。。。
第一题（HDU1385），也就是上次做了一天没A的。
最后在建图的时候采用了反向建图，莫名奇妙就A了。为什么反向建图，我也没搞懂。
#include<iostream>#include<vector>#include<queue>#include<cstring>using namespace std;const int maxn=1001;const int INF=0x7fffffff;struct edge{ int to; int cost;};int mat[maxn][maxn];int waste[maxn];int source[maxn]; vector<edge> myV[maxn]; //利用临界表存储图 int numNode; //点数int minPath[maxn]; //最短路int start,end; //起点、终点 bool inQ[maxn]; //是否入队 void inputItial(){ int i,j; for(i=1;i<=numNode;i++) //输入距离矩阵,反向的 { for(j=1;j<=numNode;j++) { scanf("%d",&mat[j][i]); } } for(i=1;i<=numNode;i++) //输入中转站的费用 { scanf("%d",&waste[i]); } for(i=0;i<maxn;i++) //清空再使用 { myV[i].clear(); } for(i=1;i<=numNode;i++) //建图 { for(j=1;j<=numNode;j++) { if(i==j || mat[i][j]==-1) continue; edge e; e.cost=mat[i][j]+waste[i]; e.to=j; myV[i].push_back(e); } }}void output(int start,int end){ printf("From %d to %d :\n",end,start); printf("Path: %d",end); while(source[end]!=0) { printf("-->%d",source[end]); end=source[end]; } printf("\n");} void SPFA(int start,int end) //最短路径快速算法 Shortest Path Faster Algorithm{ memset(inQ,false,sizeof(inQ)); inQ[start]=true; for(int j=0;j<maxn;j++) minPath[j]=INF; minPath[start]=0; queue<int> myQ; myQ.push(start); int now,to,cost; while(!myQ.empty()) { now=myQ.front(); myQ.pop(); source[start]=0; for(int k=0;k<myV[now].size();k++) { to=myV[now][k].to; cost=myV[now][k].cost+minPath[now]; if(minPath[to]>cost) { source[to]=now; //记录下to的来源为now minPath[to]=cost; if(!inQ[to]) { inQ[to]=true; myQ.push(to); } } else if(minPath[to]==cost) { if(now<source[to]) { source[to]=now; } } } inQ[now]=false; } if(start==end) { printf("From %d to %d :\n",start,end); printf("Path: %d\n",start); printf("Total cost : 0\n\n"); } else { output(start,end); printf("Total cost : %d\n\n",minPath[end]-waste[start]); }} int main(){ while(scanf("%d",&numNode)==1,numNode) { inputItial(); while(scanf("%d%d",&start,&end)==2,start!=-1&&end!=-1) { SPFA(end,start); } } system("pause"); return 0;}
第二题（HDU1595）
这题如果暴力枚举每一条路径就会超时的。
可以这样来设计算法：
记录下一条最短路径，依次破坏最短路径上的一条路。SPFA求解此时的最短路径。取最大的。
为什么这样设计算法是正确的？
1、如果破坏的而不是最短路径上的路，求解最短路径的值时得到的任是此前的最短路径。也就是说
破坏不是最短路径上的路毫无意义。
2、如果最短路径有多条。
①如果各个最短路径毫不相关，出起点、终点外没有相关的点和边。破坏任意最短路径上的路，SPFA
时都会得到其他最短路径的值。各个最短路径价值一样，取一条破坏即可。
②如果各个最短路径间有相关部分，也有不相关部分。取不想管部分破坏原理同①一样；取相关部分破坏
不论取那条最短路径都是一样的。
3、从以上的分析可以看出，只要首先找到一条最短路径，然后依次破坏其中的一条路，求解当下
最短路径，取其中最大值即可。
代码：
#include<iostream>#include<queue>#include<cstring>#include<vector> using namespace std;const int maxn=1001;const int INF=0x3f3f3f3f;struct edge{ int to; int cost;}; int numNode,numEdge;bool inQ[maxn];int source[maxn],anotherSource[maxn];int minPath[maxn];vector<edge> myV[maxn]; void input(){ for(int j=0;j<maxn;j++) //清空 { myV[j].clear(); } int from,to,cost; for(int i=0;i<numEdge;i++) { scanf("%d%d%d",&from,&to,&cost); edge e; e.cost=cost; e.to=to; myV[from].push_back(e); e.to=from; myV[to].push_back(e); }}void SPFA(){ memset(inQ,false,sizeof(inQ)); inQ[1]=true; for(int i=0;i<=numNode;i++) minPath[i]=INF; minPath[1]=0; memset(source,-1,sizeof(source)); queue<int> myQ; myQ.push(1); int now,to,cost; while(!myQ.empty()) { now=myQ.front(); myQ.pop(); inQ[now]=false; for(int j=0;j<myV[now].size();j++) { to=myV[now][j].to; cost=minPath[now]+myV[now][j].cost; if(minPath[to]>cost) { minPath[to]=cost; source[to]=now; if(!inQ[to]) { inQ[to]=true; myQ.push(to); } } } } //printf("%d\n",minPath[numNode]); }void getMinPath(){ int from=anotherSource[numNode],to=numNode,minCost=-1,temp,i,j; bool flag=false; //加flag保证起点为1的路也会被处理 while(from!=1 || !flag) { if(from==1) flag=true; for(i=0;i<myV[from].size();i++) { if(myV[from][i].to==to) { temp=myV[from][i].cost; myV[from][i].cost=INF; break; } } for(j=0;j<myV[to].size();j++) { if(myV[to][j].to==from) { myV[to][j].cost=INF; break; } } SPFA(); if(minPath[numNode]!=INF) minCost=minCost>minPath[numNode]?minCost:minPath[numNode]; myV[from][i].cost=myV[to][j].cost=temp; to=from; from=anotherSource[from]; } printf("%d\n",minCost);} void keepSource() //getMinPath()不能用source[]直接找最短路径 { for(int i=0;i<maxn;i++) { anotherSource[i]=source[i]; anotherSource[1]=1; }} int main(){ while(scanf("%d%d",&numNode,&numEdge)!=EOF) { input(); SPFA(); keepSource(); getMinPath(); } system("pause"); return 0;}
晚上的话，那些大神们讲了博弈论、树状数组云云。。。
不懂，也就不吐糟了。