hdu 3416 最短路+最大流
2010年9月06日 04:04
求源点到终点的不共享边的最短路有多少条.
先求一次单源最短路，得到距离数组d，考虑某条边，它的起点是k1，终点是k2，边的权是c，如果d[k2]-d[k1]=c就说明这条边是最短路上的---wr大牛
原来我的想法是求一次单源最短路得到最短路长度,然后再一次求一次单源最短路并回溯来构造流网络,实在是太菜了而且流网络方面也没有想清楚......
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define maxn 1050
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
struct Edge{int w,wt,next;}e[1000000];
int start[maxn];
int d[maxn];//单源距离
void spfa(int s)
{
int i,v,N=0;
deque<int> dq;
for(v=0;v<n;v++)
d[v]=inf;
d[s]=0;
dq.push_back(s);dq.push_back(n);
while(!dq.empty())
{
v=dq.front();dq.pop_front();
if(v==n)
{if(N++>n) return;dq.push_back(n);}
else
for(i=start[v];i!=-1;i=e[i].next)
{
if(d[e[i].w]>d[v]+e[i].wt)
{
d[e[i].w]=d[v]+e[i].wt;
dq.push_back(e[i].w);
}
}
}
}
int flow[maxn][maxn],maxflow[maxn],father[maxn];
int Maxflow,visit[maxn];
void ford_fulkerson(int s,int t)
{
queue<int>Q;
int i,u,v;
while(1)
{
//memset(maxflow,0,sizeof(maxflow));//每次寻找增广路径都将每个点的流入容量置为0
//memset(visit,0,sizeof(visit));//标记一个点是否已经压入队列
for(i=0;i<n;i++) maxflow[i]=visit[i]=0;
maxflow[s]=inf;//源点的容量置为正无穷
Q.push(s);// 将源点压入队列
while(!Q.empty())
{
u=Q.front();
Q.pop();
for(v=0;v<n;v++) if(!visit[v]&&flow[u][v]>0)
{
visit[v]=1;
father[v]=u;//记录下他的父亲方便往后的正反向更新
Q.push(v);
maxflow[v]=(maxflow[u]<flow[u][v]?maxflow[u]:flow[u][v]);//当前点的容量为父亲点容量与边流量的较小者
}
if(maxflow[t]>0)//如果找到了汇点并且汇点容量不为0则清空队列
{
while(!Q.empty())
Q.pop();
break;
}
}
if(maxflow[t]==0)//已经找不到到汇点的增广路经了，就退出整个循环
break;
for(i=t;i!=s;i=father[i])
{
flow[father[i]][i]-=maxflow[t];//正向更新
flow[i][father[i]]+=maxflow[t];//反向更新
}
Maxflow+=maxflow[t];//更新最大流
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
int i,v,w,wt,s,t,cnt;
int cas;scanf("%d",&cas);
while(cas--)
{
scanf("%d%d",&n,&m);
cnt=0; for(v=0;v<n;v++) start[v]=-1;
for(i=0;i<m;i++)
{
scanf("%d%d%d",&v,&w,&wt);
v--;w--;
e[cnt].w=w;e[cnt].wt=wt;
e[cnt].next=start[v];start[v]=cnt++;
}
scanf("%d%d",&s,&t);
s--;t--;
spfa(s);
//for(v=0;v<n;v++)
//cout<<v<<":"<<d[v]<<" ";
//cout<<endl;
Maxflow=0;
for(v=0;v<n;v++) for(w=0;w<n;w++) flow[v][w]=0;
for(v=0;v<n;v++)
for(i=start[v];i!=-1;i=e[i].next)
{
w=e[i].w;
if(d[w]-d[v]==e[i].wt)
flow[v][w]+=1;
}
ford_fulkerson(s,t);
printf("%d\n",Maxflow);
}
}
