題意：求1->n的兩條不相交的最短路（兩條路徑可以共頂點(diǎn)但是不能共邊)
心得：看了AC的博客學(xué)的，呵呵，這題充分展示了一切皆是網(wǎng)絡(luò)流的核心思想。做法：首先找出以1為頂點(diǎn)的最短路徑樹，1到樹中任意一點(diǎn)的連線都是最短路徑，首先把這些邊加到網(wǎng)絡(luò)流的邊集中，容量為1。
然后再枚舉下邊，將不在最短路徑樹上但是在最短路上的邊也加到網(wǎng)絡(luò)流的邊集中，容量為1。跑一遍1到n的最大流，如果流量>=2則有解，再從原點(diǎn)深搜路徑即可。
確切的來說，只要在后來建的圖中隨便找一條路徑均是原點(diǎn)到該點(diǎn)的最短路（注意邊是單向的），又因?yàn)橄拗屏肆髁渴?，所以一條邊只能選取一次，這樣跑出來的流量就一定是不相交最短路的條數(shù)。
int mat[maxn][maxn];
int n,m;
int dis[maxn];
int use[maxn];
void SPFA(int n,int s)
{
fill(dis,dis+n,INF);
fill(use,use+n,0);
queue<int>Q;
dis[s]=0;
use[s]=1;
Q.push(s);
while(!Q.empty())
{
int x=Q.front();Q.pop();
use[x]=0;
for(int i=0;i<n;i++)
{
if(dis[x]+mat[x][i]<dis[i])
{
dis[i]=dis[x]+mat[x][i];
if(!use[i])
{
use[i]=1;
Q.push(i);
}
}
}
}
}
int flag=0;
void dfs(int x)
{
if(flag==1)return;
if(x==n-1)
{
flag=1;
printf("%d\n",x+1);
return;
}
else printf("%d ",x+1);
for(node *p=adj[x];p;p=p->next)
{
if((p-edge)&1)continue;
if(p->flow==0) {
p->flow=-1;
dfs(p->v);
if(flag==1)
return;
}
}
}
int main()
{
scanf("%d %d",&n,&m);
int a,b,c;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==j)mat[i][j]=0;
else mat[i][j]=INF;
}
}
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
a--;b--;
if(c<mat[a][b])
mat[a][b]=mat[b][a]=c;
}
SPFA(n,0);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(i==j)continue;
if(dis[i]+mat[i][j]==dis[j])
insert(i,j,1);
}
int ans=sap(n,0,n-1);
if(ans<2){
printf("No solution\n");
return 0;
}
flag=0;
dfs(0);
flag=0;
dfs(0);
return 0;
}
很難得的一次寫對(duì)了SPFA...
參考了AC大神的代碼，遞歸刪除邊的時(shí)候?qū)⒘髁恐脼?1,不錯(cuò)的想法。另外我用p-edge的奇偶性判斷正反邊，但是一直沒弄明白p和edge都是地址而且地址相差并不是1的時(shí)候減出來卻是1。。。